ikautak.log

C/C++, Python, CUDA, Android, Linux kernel, Network, etc.

暗号理論入門　2.7〜2.8

Python 暗号

暗号理論入門 原書第3版

暗号理論入門 原書第3版

2.7 最大公約数

少なくとも一方が0でない二つの整数 a と b のすべての公約数の中には、ただ一つ最大のものが存在し、これを a と b の最大公約数(greatest common divisor)といい gcd(a, b) で表す。
0と0の最大公約数は0（gcd(0, 0) = 0）。

\alpha_1, \ ...,\ \alpha_k が実数とし、
　\alpha_1 \mathbb{Z}\ +\ \cdot \cdot \cdot \ + \ \alpha_k \mathbb{Z} = \{\alpha_1 z_1 \ + \ \cdot \cdot \cdot \ + \ \alpha_k z_k \ \ : \ \ z_i \in \mathbb{Z},\ 1 \le i \le k\}
と表すものを \alpha_i のすべての整数値線形結合(integer linear combnation)の集合という。

a と b のすべての整数値の線形結合の集合は gcd(a, b) のすべての整数の倍数の集合。
よって a \mathbb{Z}\ +\ b \mathbb{Z}\ =\ gcd(a, b) \mathbb{Z} である。

ax\ +\ by\ =\ gcd(a,\ b) である整数 x と y が存在する。

2.8 ユークリッドのアルゴリズム

最古のアルゴリズムと言われる、ユークリッドの互除法。
２つの自然数の最大公約数を効率よく計算できる。

  1. b = 0 であれば、gcd(a, b) = |a| である。
  2. b \ne 0 であれば、gcd(a, b) = gcd(|b|, a\ mod\ |b|)

pythonで再帰を使わない実装。

def gcd(a, b):
    a = abs(a)
    b = abs(b)
    while b:
        r = a%b
        a = b
        b = r
    return a

　r_0 = |a|,\ \ r_1 = |b|
とおき、 k \ge 1 と r_k \ne 0 に対して

　r_{k+1}=r_{k-1} \ mod\ r_k

とする。

ここで、 r_2,\ r_3 はアルゴリズムのwhileループで計算される剰余の数列。
whileループによる k 回の計算の後、ユークリッドのアルゴリズムでは
　a = r_k,\ \ b = r_{k+1}
が成立する。

r_n が剰余の数列 (r_k) の最後の0でない項であるとすると、n はユークリッドのアルゴリズムがgcd(a, b) を計算するために必要とする反復の総数になる。

q_k = \lfloor r_{k-1}/r_k \rfloor \ \ ,\ \ \ 1 \le k \le n
とすると、q_k は r_{k-\1} の r_k による除法の商であり、
r_{k-1} = q_k r_k + r_{k+1}
が成立する。

a = 100 かつ b = 35 の場合は以下のようになる。

k 0 1 2 3 4
r_k 100 35 30 5 0
q_k 2 1 6

この本は非常に解説が丁寧だな。綺麗に論理建てて書かれているし。