RSA暗号で必須である素数を高速に生成させるため、素数生成アルゴリズムについて調査した。
#Miller–Rabin素数判定法とは
与えられた整数を素数かどうか判定するアルゴリズムの1種。
確率的アルゴリズムであり、検定に通った数が素数であると高い確率で信じられるアルゴリズムである。
##Miller–Rabin素数判定法の定理
奇素数 $p = 2^st+1$ $(t$ は奇数$)$と、 $p$ と互いに素な自然数 $a\big(a\in\mathbb{Z}_p\big)$ について以下(1)(2)のいずれかが成り立つ。
(1) $a^t = 1 \bmod p$
(2) $a^{2^{0}t}, a^{2^{1}t}, a^{2^{2}t},..., a^{2^{s-1}t}$ の中に $p$ を法として $-1$ と合同になる数が存在
##フェルマーの小定理
Miller–Rabin素数判定法を理解するうえで必要な事前知識としてフェルマーの小定理を紹介する。
任意の素数 $p$ と $p$ と互いに素な自然数 $a$ について、
$a^{p-1}\equiv 1\bmod p$
が成り立つ。
##Miller–Rabin素数判定法の証明
$p-1=2^st$ よりフェルマーの小定理から $a^{2^st}\equiv 1\bmod p$ が成り立つ。
$a^t, a^{2t}, a^{2^2t},...,a^{2^{s-1}t}$
の中で $p$ を法として $1$ と合同でない ( $p$ で割って余りが $1$ と等しくない) ものが存在する場合、
その中で最大の数を $x$ とすると $x^2=1\bmod p$ が成り立つ。
つまり、$x^2-1=(x-1)(x+1)\equiv 0\bmod p$ が成り立ち、
$x\neq 1\bmod p$ より $x$ は $x=-1\bmod p$ を満たす。
この時 $x$ は(2)の条件を満たす。
このような $x$ が存在しない場合(1)の条件を満たす。
#Miller–Rabin素数判定法のアルゴリズム
入力：素数を判定する整数 $num$
出力：$num$ が素数の可能性があるとき$True$、素数でないとき$False$
- $num>2$ かつ $num$ が偶数であれば「$False$」を出力し終了
- $num-1=2^st$ となる整数 $s\geq0$ と奇数 $t\geq3$ を見つける
- $a\in\{1,2,3,...,num-1\}$ をランダムに選ぶ
- $a^t\equiv 1\bmod num$ の場合「$True$」を出力し終了
- $i=0$ とし、$i$ を $1$ ずつ増やしながら $i<s$ の間以下を繰り返す
1. $a^{2^it}\equiv-1\bmod num$ の場合「$True$」を出力し終了 - 「$False$」を出力し終了
上記のアルゴリズムをpythonで記述した例を以下に示す。(簡単のため引数は2以上の整数とする)
def Miller_Rabin_test(num):
if num == 2:
return True
if num > 2 and num & 1 == 0:
return False
s, t = 0, num-1
while t & 1 == 0:
s, t = s+1, t >> 1
a = random.randint(1, num-1)
if pow(a, t, num) == 1:
return True
for i in range(0, s):
if pow(a, pow(2, i) * t, num) == num-1:
return True
return False
#Miller–Rabin素数判定法の信頼性
Miller–Rabin素数判定法において合成数が素数の可能性があると判定されてしまう $a$ の数は多くても $\frac{n-1}{4}$ 個であることが知られている。(証明はまた今度にします)
つまりランダムに $k$ $(0<k<num)$ 個の $a$ を決めてテストを行う場合、全ての $a$ で合成数が素数の可能性があると判定されてしまう確率は $\bigg(\frac{\frac{n-1}{4}}{n-1}\bigg)^k=\frac{1}{4^k}$
$a$ の取る数が少なくても十分に信頼できることがわかる。
#参考文献
萩田真理子 (2010) 『暗号のための代数入門』 サイエンス社