• 追加された行はこの色です。
  • 削除された行はこの色です。
*目次 [#lb190190]

#contents


*はじめに [#e618acfa]

 数学において素数は重要な存在である。数学と密接な関係にある暗号の世界においても、[[素数]]は重要な存在である。公開鍵暗号系のアルゴリズムの仕様を確認してもらえれば、多くの場合において素数をランダムに選択する必要があることがわかると思う。例えば、[[RSA暗号]]の鍵生成アルゴリズムでは大きな素数を2つ生成しなければならない。この部分できちんとした素数が作られなければ、暗号の安全性が脆弱になってしまうのである。つまり、素数をランダムに生成するということは暗号の世界において重要と言える。

 今回の記事では、素数をランダムに生成するアルゴリズム(以降、素数生成アルゴリズムと呼ぶことにする)を単に紹介するだけでは面白くないので、試行錯誤しながら素数生成アルゴリズムを考えていくことにする。その後、いくつかの素数生成アルゴリズムを紹介し、コストの面(必要となる速度・メモリ)の観点で比較する。最後に、指定されたビット数の素数の生成について言及する。


*素数生成アルゴリズム=ランダム値生成アルゴリズム+素数テスト [#r0aab747]

 [[原始元生成アルゴリズム:http://akademeia.info/index.php?%B8%B6%BB%CF%B8%B5#fbac66ed]]では、確定的に(100%の確率で)[[原始元]]を生成するアルゴリズムを作るよりも、ある程度大きな確率で原始元を生成するアルゴリズムを作る方が効率がよいという話をした。このある程度大きな確率で原始元を生成するアルゴリズムというのは、ランダムな値を生成するアルゴリズムと、原始元判定アルゴリズムの組み合わせであった。

 今回の素数生成アルゴリズムも、同様のアプローチで考えた方が高速であることがわかっている。つまり、素数生成アルゴリズムを考える上で重要な部分は、優秀な素数判定アルゴリズムを考えるという点に帰着される。素数生成アルゴリズムの一部として利用できるぐらい優秀な素数判定アルゴリズムのことを素数テストを呼ぶことにする。


*素数テスト [#z6405cb7]

#divid(s,thorem)
[定義]Primes={bin(n)|n:素数}
#divid(e,thorem)

 つまり、Primesは素数nの2進表現を意味する。

#divid(s,thorem)
[定義]アルゴリズムMが素数テストとは、MがPrimes⊂coRPを証言するアルゴリズムであるときである。
#divid(e,thorem)

 これは次を意味する。

-入力が&mimetex("x \not{\in} Primes");のとき
--Mの出力:M(x)はaccept or rejectされる。
---ただし、acceptする確率は1/2以下。
-入力が&mimetex("x \in Primes");のとき
--Mの出力:M(x)は必ずacceptされる。

 つまり、素数テストは次の2つの条件を同時に満たしている。

-入力が合成数(素数でない値)だった場合、acceptまたはrejectを出力する。
--ただし、acceptする確率は1/2以下とする。
-入力が素数だった場合、必ずacceptを出力する。

 つまり、素数テストに素数でない値が入力されれば1/2以上の確率でrejectされ、素数が入力されれば必ずacceptされるということである。

 理想的なアルゴリズムはaccept(素数と判定)されたものは必ず素数で、reject(素数でない)と判定されたものは必ず素数でないものである。しかし、この理想的なものがないとしても、上記の定義のような素数テストさえ存在すれば、このアルゴリズムを何度も繰り返すことで素数でないのにaccpet(素数と判定)される可能性はどんどん低くすることができる。つまり、実質的に素数テストを多段で使ってaccpet(素数と判定)されたものはほとんど素数と考えてよいといえる。


*素数判定アルゴリズムの種類 [#qad7064a]

 素数判定アルゴリズムには他の方式も存在する。

-確率的
--[[フェルマーテスト]](完全な素数判定アルゴリズムではない)
--[[Miller-Rabinテスト]]
--[[Solovay-Strassenテスト]]
-確定的
--[[エラトステネスの篩]]
--[[AKS素数判定法]]
--[[Millerテスト]]
--[[Adleman-Rumelyテスト]]
--[[Cohen-Lenstraテスト]]
--[[AKSテスト]]
--[[Lucasテスト]]


*フェルマーテスト [#k30409a1]

 まず素朴に考えると、素数テストのアルゴリズムとして、[[フェルマーの小定理]]が使えるかもしれないと思うはずである。それでは本当に使えるのかどうかを確認してみよう。

 フェルマーの小定理とは「pが素数ならば、任意のa(∈{1,…,p})に対して&mimetex("a^{p-1} \equiv 1 \pmod{p}");が成り立つ」というものであった。つまり、pが素数ならば、p-1乗すればどの値でもmod pの世界で1に一致するということである。

 これを素数pの代わりに、一般の整数n(素数と合成数の混合)に対して考えてみる。ここで、aはn以下の整数なら何でもよいので、a=4としておく。

-[1]n=5のとき
--4SUP{n-1};=4SUP{5-1};=4SUP{4};=16×16≡1×1 (mod 5)=1
-[2]n=6のとき
--4SUP{n-1};=4SUP{6-1};=4SUP{5};≡4 (mod 6)
-[3]n=7のとき
--4SUP{n-1};=4SUP{7-1};=4SUP{6};≡1 (mod 7)
-[4]n=8のとき
--4SUP{n-1};=4SUP{8-1};=4SUP{7};≡0 (mod 8)
-[5]n=9のとき
--4SUP{n-1};=4SUP{9-1};=4SUP{8};≡7 (mod 9)
-[6]n=10のとき
--4SUP{n-1};=4SUP{10-1};=4SUP{9};≡4 (mod 10)
-[7]n=11のとき
--4SUP{n-1};=4SUP{11-1};=4SUP{10};≡1 (mod 11)
-[8]n=12のとき
--4SUP{n-1};=4SUP{12-1};=4SUP{11};≡4 (mod 12)

 以上の結果を表にすると次のようになる。

|n|5|6|7|8|9|10|11|12|
|4SUP{n-1}; (mod n)|1|4|1|0|7|4|1|4|

 nが素数のときに&mimetex("4^{n-1} \pmod{n}");が1になることは、フェルマーの小定理から当然である。この表から、逆に&mimetex("4^{n-1} \pmod{n}");が1のときに、nは素数に対応していることがわかる。例えば、n=5,7,11(すべて素数)のときに&mimetex("4^{n-1} \pmod{n}");が1に一致しているからである。即ち、フェルマーの小定理の逆が成り立つことが期待できそうである(対偶が成り立つのは自明。ここではさらに逆が成り立つことを期待している)。このフェルマーの小定理の逆の方法で、素数判定アルゴリズムをフェルマーテストと呼び、フェルマーテストのアルゴリズム名をFermatとする。このFermatの入出力と内部のアルゴリズムは次のようになる。

-入力
--n:整数(ただし、n≧3)
-出力
--"reject" or "accept"

#code(lisp){{
a←{2,3,…,n-2}からランダムに選択した値
if a^{n-1} ≠ 1 (mod n) then
    return "reject"
else return "accept"
}}

 ここで、nが素数ならば、即ち&mimetex("n \in Primes");ならば、「Fermat(n)="reject"」(この表記法は「Fermatにnを代入したときの出力結果が"reject"」ということを意味する)となる確率は0が当然成り立つ。

 一方、nが合成数ならば、即ち&mimetex("n \not{\in} Primes");ならば「Fermat(n)="reject"」がどんな値になるかが不明である。

 1になるのが理想的だが、それは難しそうである。しかし何らかの確率が具体的に出て欲しい。できれば1/2以上だと嬉しい(1/2以上なら素数テストとして活用可能であることが確定するから)。それでは、「nが合成数」かつ「Fermat(n)="reject"」が成り立つときの確率を調べてみる。

 フェルマーテストのアルゴリズムFermatの入出力は次の通りである。

#img(http://security2600.sakura.ne.jp/main2/image3/Fermat_alg.jpg)
#img(,clear)

 入力されるnは別のランダムな整数を生成するアルゴリズムを利用する。それをフェルマーテストのアルゴリズムFermatに入力すると、"accept"あるいは"reject"が出力される。

-"accept"が出力されたとき
--nは素数あるいはカーマイケル数
---なぜならば、&mimetex("\exists a; a^{n-1} \not{\equiv} 1 \pmod{n}");であるから。ただし、(a,n)=1である。
-"reject"が出力されたとき
--nは必ず合成数
---なぜならば、&mimetex("\forall a; a^{n-1} \equiv 1 \pmod{n}");であるから。ただし、(a,n)=1である。


 ここで主張を明確にするために、次の2つの言葉を定義する。

#divid(s,thorem)
-「n≧2」かつ「&mimetex("a^{n-1} {\not}{\equiv} 1 \pmod{n}");」が成り立つとき、a(ただし1≦a<n)を''nに対するFermat witness''と呼ぶ。
-「n(≧3):合成数」かつ「&mimetex("a^{n-1} {\equiv} 1 \pmod{n}");」が成り立つとき、a(ただし1≦a<n)を''nに対するFermat liar''と呼ぶ。
#divid(e,thorem)

 この定義より、指定されたnに対してひとつでもFermat witnessが存在したら、nは合成数と確定できる。なぜならば、Fermat witnessということは「&mimetex("a^{n-1} {\not}{\equiv} 1 \pmod{n}");」が成り立つことを意味し、Fermatのアルゴリズムのif文の条件文に対応している。つまり、if文の条件がTrueになり、"reject"が出力されることに対応する。ところが、nが素数のときに"reject"が出力されることは皆無である。これはフェルマーの小定理から明らかである。つまり、"reject"が出力されたときのFermatの入力は必ず合成数ということになる。

 また、「nが合成数」かつ「Fermat(n)="reject"」が成り立つときの確率を調べるには、aの総数のうちで、「nに対するFermat witness」であるようなaの個数がどれぐらいあるかを知ることができればよい。まず、aの総数はn-3個である。これはaは3≦a<nを満たすから明らかである。次に、「nに対するFermat witness」のときは、定義より「&mimetex("a^{n-1} {\not}{\equiv} 1 \pmod{n}");」という条件が満たされたときである。

 そして、nが素数か否か、aが指定されたnにおいて&mimetex("a^{n-1} {\equiv} 1 \pmod{n}");を満たすか否かによって分類すると、次の4つのパターンが存在する。

||nは素数|nは合成数|
|aが&mimetex("a^{n-1} {\not}{\equiv} 1 \pmod{n}");を満たす|(1)|(2)|
|aが&mimetex("a^{n-1} {\equiv} 1 \pmod{n}");を満たす|(3)|(4)|

 フェルマーの小定理より、(1)の場合はありえないので、0個。そして、aが「nに対するFermat witness」であるときの個数は(2)、aが「nに対するFermat liar」であるときの個数は(3)+(4)に対応している。つまり、「nに対するFermat witness」+「nに対するFermat liar」=n-3が成り立つ。先ほど、「nが合成数」かつ「Fermat(n)="reject"」が成り立つときのaの個数が、nに対するFermat witnessの個数と一致するとすでに述べた。よって、「nが合成数」かつ「Fermat(n)="reject"」が成り立つときのaの個数は、「aの総数」-「nに対するFermat liar」と言い換えることもできる。

 以上のことをまとめると、目的であった「nが合成数」かつ「Fermat(n)="reject"」が成り立つときの確率は(nに対するFermat witnessの個数)/(n-3)、即ち1-(nに対するFermat liarの個数)/(n-3)である。

#divid(s,notice)
例1:ランダム値生成アルゴリズムでnを生成するわけだが、例えばn=143を生成して、これを素数判定アルゴリズムFermatに入力したときの動きを見ていく。

 そもそもn=143は11×13のように素因数分解できるので、合成数である。しかし、我々はまだ合成数かどうかわからない、これを調べるためにFermatを使うのである。n=143のときの「nに対するFermat liar」、即ちaSUP{n-1};≡1 (mod n)を満たすようなaを知りたい。ここでは結論を述べると、a=1,12,131,142の4つだけである。例えば、143は合成数なので、12SUP{142}; (mod 143)は1に一致するとは限らない。ところが計算すると1に一致する。131も同様に131SUP{142};≡1 (mod 143)が成り立つので、143に対するFermat liarのひとつである。特にa=1(なぜならば1^142≡1 (mod 143)),142(なぜならば142SUP{142};≡-1SUP{142}; (mod 143)≡1 (mod 143))は自明なものなので、除外して考えると、a=12,131だけになる。

 このとき「Fermat(143)="reject"」が成り立つ確率が1/2以上かどうかを調べる。まず、「Fermat(143)="accept"が成り立つ確率」=2/(143-3)=2/140=1/70<1/2が成り立つ。よって、「Fermat(143)="reject"が成り立つ確率」>1/2になる。つまり、n=143のときはFermatを多段にすることで、合成数を判断できてうまくはじくことができるわけだ。 ◇
例2:次に、n=561のときを考えてみる。このn=561も3×11×17と素因数分解できるので合成数である。

 このとき「Fermat(561)="reject"」が成り立つ確率が1/2以上かどうかを調べる。n=561のときにGCD(a,n)=1を満たすaは「nに対するFermat liar」になってしまう。つまり、「Fermat(143)="accept"が成り立つ確率」=φ(n)/(n-3)≒φ(n)/nになる(φという記号は[[久留島・オイラー関数]]を意味する)。なぜφ(n)が出てくるのかというと、GCD(a,n)=1であるようなaの個数、即ちZ_n^*の個数だからである。よって、「Fermat(143)="reject"が成り立つ確率」=(1-φ(n))/nになる。ここで、nが大きいとき、n-φ(n)<<nが成り立つので、「Fermat(143)="reject"が成り立つ確率」<<1/2になってしまう。つまり、n=561のときはFermatを多段にしても、合成数を判断できずうまくはじくことができない。つまり、n=561に対してはFermatは、素数テストとしてうまく動かないということである。 ◇
#divid(e,notice)

 このようなnは''カーマイケル数''と呼ばれ、無限に存在することが証明されている。

 よって、例外となるのはn=561だけでなく、ランダム値生成アルゴリズムの出力であるnでたまたまカーマイケル数が選ばれてしまえばFermatは素数テストとして有効ではないということになる。しかも、カーマイケル数は無限に存在するので、nがカーマイケル数かどうかをチェックしてから、Fermatの入力にするというアプローチも無理である。したがって、フェルマーテストは素数テストとして活用はできないという結論になる。

#divid(s,thorem)
[定理]n≧3:奇数の合成数とする。このとき、nは少なくともひとつFermat witness(∈&mimetex("\mathbb{Z}_n^*");)を持つならば、Pr[Fermat(n)=reject]>1/2が成り立つ。
#divid(e,thorem)

 この定理の条件が、nはカーマイケル数以外という意味である。そして結論が成り立つとき、素数テストとしてうまく動く。


#divid(s,proof)
[証明]nに対してのFermat liarの集合をF-LiarSUB{n};と表記することにする。つまり、次のように定義される。

&mimetex("F-Liars_n := \{a|1 \le a < n \bigwedge (a,n)=1 \bigwedge a^{n-1} \equiv 1 \pmod{n} \} \subset \mathbb{Z}_n^*");

 このとき、&mimetex("F-Liars_n < \mathbb{Z}_n^*");が成り立つことを示す。

[1]単位元1∈F-LiarsSUB{n};が成り立つ。

[2]積について閉じていることを示す。

「a,b∈F-LiarsSUB{n};」⇒「ab∈F-LiarsSUB{n};」

 なぜならば、&mimetex("(ab)^{n-1}=a^{n-1} b^{n-1} \equiv 1 \cdot 1 \pmod{n} \equiv 1 \pmod{n}");が成り立つから。

 よって、[定理]「「G:有限群」かつ「G⊃H∋e」かつ「Hは群演算について閉じている」(a,b∈H⇒ab∈H)⇒「G>H」(HはGの部分群)」が成り立つという事実があるため、[1][2]より、&mimetex("F-Liars_n < \mathbb{Z}_n^*");が成り立つ。

 また、[定理]「G:有限アーベル群とする。このとき「G>H」⇒「#H|#G」」が成り立つので、&mimetex("\sharp F-Liars_n | \sharp \mathbb{Z}_n^*");が成り立つ。よって、φ(n)=n-1より、&mimetex("F-Liars_n \le \frac{n-2}{2}");が成り立つT。

 従って、次のように計算できる。

Pr[Fermant(n)=reject]~
&mimetex("1-\frac{\frac{n-2}{2} -2}{n-3}"); (分子の(n-2)/2は#F-LiarsSUB{n};、2は自明なFermat-liarを意味する)~
&mimetex("=\frac{n}{2(n-1)}");~
&mimetex(">\frac{1}{2}"); □
#divid(e,proof)


**擬素数とカーマイケル数 [#m31e8435]

 この節では擬素数とカーマイケル数についてもう少し見てみる。素数生成アルゴリズムの話からは少しはずれるので、飛ばしてもらってもよい。

#divid(s,thorem)
[定義]擬素数(pseudoprime)~
「n:(底aについての)擬素数」~
⇔SUP{def};「&mimetex("a^{n-1} \equiv 1 \pmod{n}");」
#divid(e,thorem)

#divid(s,thorem)
[定義]カーマイケル数(Carmichael number)~
「n:カーマイケル数」~
⇔SUP{def};「∀a(ただし、(n,a)=1);&mimetex("a^{n-1} \equiv 1 \pmod{n}");」
#divid(e,thorem)

 つまり、カーマイケル数は、GCD(a,n)=1であるようなすべての整数aに対して、nが底aについての擬素数であるときを指す。

***擬素数の性質 [#q2b4a94d]

#divid(s,thorem)
[定理]擬素数は無限個存在する。
#divid(e,thorem)

***カーマイケル数の性質 [#ob2cfc37]

 カーマイケル数は次のような性質を持つ。

#divid(s,thorem)
[定理](Alford, Graville and Pomerance (1992))~
カーマイケル数は無限個存在する。
#divid(e,thorem)

#divid(s,thorem)
[定理]「n(≧3):奇数のカーマイケル数」~
⇔「&mimetex("(\frac{n}{2})=-1 \wedge (\forall n,p)=1 \wedge p-1|n-1");」
#divid(e,thorem)

 nが奇数のカーマイケル数なら、3つの結論が導けることを意味する。第1の結論はnは平行数を持たないということ、第2の結論は任意のnがpと素であるということ、第3の結論はp-1がn-1の約数ということである。

#divid(s,proof)
[証明]⇔を示すので、必要条件と十分条件に場合分けして証明する。

[1]⇒を示す

 カーマイケル数の定義より、∀a(ただし、(n,a)=1);&mimetex("a^{n-1} \equiv 1 \pmod{n}");が成り立つ。

 また、pをnの約数の素数とし、aをnと素なmod pの原始元とする。このaは、[[中国人剰余定理]]より存在が保証される。すると、原始元の定義より、&mimetex("a^{p-1} \equiv 1 \pmod{p}");が成り立つ。よって、&mimetex("a^{n-1} \equiv 1 \pmod{p}");が成り立つ。

 次に、[定理]「g∈Gであり、e∈Zであるとする。このとき、gSUP{e};=1となるのは、eがgの位数で割り切れるときに限る」より、aの位数p-1はn-1の約数である。

 さらに、pSUP{2};がnの約数でないことを示す。背理法を用いるため、pSUP{2};がnを割り切ると仮定する。このとき、&mimetex("\phi(p^{2})(=(p-1)p)");はφ(n)の約数である。また、mod nの既約剰余群で位数pの元が存在する。よって、pはn-1の約数である。これはpがnの約数であることに矛盾する。

[2]←を示す

 nは平方数を含まないとし、nのすべての素の約数pに対して、p-1をn-1の約数とする。ただし、aとnは互いに素とする。

 このとき、[[フェルマーの小定理]]より、&mimetex("a^{p-1} \equiv 1 \pmod{p}");が成り立つ。n-1はp-1の倍数であるから、&mimetex("a^{n-1} \equiv 1 \pmod{p}");が成り立つ(nと素である値pごとに、このリレーションが成り立つ)。よって、nの素因数は互いに異なっているから、&mimetex("a^{n-1} \equiv 1 \pmod{n}");が成り立つ(複数のリレーションをひとつのリレーションにまとめた)。 □
#divid(e,proof)

#divid(s,thorem)
[定理]カーマイケル数は少なくとも3つの異なる素因数を持つ。
#divid(e,thorem)

#divid(s,proof)
[証明]nをカーマイケル数とすると、定義よりnは素数ではない。また、上記の定理より、nは平方数を持たない。よって、nは素数のべき乗にはならない。つまり、nは少なくとも2つの素因数を持つことがいえる。

 次に、p,q(p>qとしても一般性を失わない)をnの素因数とし、n=pqが成り立つと仮定する。上記の定理より、p-1はn-1=pq-1=(p-1)q+(q-1)の約数になる。よって、p-1はq-1の約数となる。しかし、p>qより、p-1>q-1(>0)が成り立つので、q-1の最小性より矛盾が生じる。よって、n=pqと仮定したことが間違いということになる。したがって、nの素因数は少なくとも3つ以上であることがいえる。 □
#divid(e,proof)

*Miller-Rabinテスト [#dbf4aa6a]

 Millerの定理と呼ばれる次の定理が存在する。

#divid(s,thorem)
[定理]pを素数とし、rはp-1={2^s}×rを満たす奇数とする(奇数が出るまで2で割っている)。このとき、1≦a≦p-1なる任意の整数aに対して、次が成り立つ。「&mimetex("a^r \equiv 1 \pmod{p}");」あるいは「&mimetex("a^{{2^j} \times r} \equiv 1 \pmod{p}");」を満たすような&mimetex("j \in \{0 , \cdots, s-1\}");が存在する。←(*)
#divid(e,thorem)

 ここではMillerの定理の証明はせずに、何を意味しているのか、そしてなぜ成り立つのかという点と直観的に述べる。

 pが素数のとき、「xSUP{2};≡1 (mod p)」⇒「x≡-1 or 1」が成り立つ。pが合成数のときはこれが成り立つとは限らない。よって、素数を法とする世界で2乗して1だったら、元の数は1 or -1である。つまり、aSUP{r};を2乗ずつしていき、1に初めてなったとき、その直前の数は-1でなければならないということである。

#img(http://security2600.sakura.ne.jp/main2/image3/miller1.jpg)
#img(,clear)

#divid(s,proof)
[略証]s=2のときを証明する。即ち、&mimetex("p-1=2^{2} \times r");で考える。ただし、rは奇数と仮定する。

 このとき、フェルマーの小定理より、1≦a≦p-1なる任意のaに対して、pを法として次が成り立つ。

&mimetex("1 \equiv a^{p-1} \pmod{p}");~
&mimetex("0 \equiv a^{p-1} -1 \pmod{p}");~
&mimetex("0 \equiv a^{2^2 r} -1 \pmod{p}"); (∵p-1=2SUP{2};×r)~
&mimetex("0 \equiv (a^{2r})^2 -1 \pmod{p}"); (∵&mimetex("a^{2^2 r}=a^{4r}=a^{2r}a^{2r}=(a^{2r})^2");)~
&mimetex("0 \equiv (a^{2r} +1)(a^{2r} -1) \pmod{p}");~
&mimetex("0 \equiv (a^{2r} +1)(a^r +1)(a^r -1) \pmod{p}");~
∴&mimetex("a^r \equiv 1, a^4 \equiv -1, a^{2r} \equiv -1 \pmod{p}"); □
#divid(e,proof)

 Millarの定理を利用した素数テストであるMiller-Rabinテスト(MRテスト)を紹介する。このMiller-Rabinテストの入出力とアルゴリズムMRは次のようになる。

-入力
--n(n≧3の奇数)
-出力
--"prime" or "composite"

#code(lisp){{
s,rはn-1=2^{s}×rを満たすようにセットされる(ただし、rは奇数)
i=0
i←i+1
a:{1,2,…,n-1}からランダムに選択
y[0]←a^r mod n
if(y[0]==1 || y[0] == n-1)
    output "prime"
else
    for(j=1;j≦s-1;j=j+1){
        y[j]←y[j-1]^2 mod n
        if(y[j]==n-1)
            output "prime"
    }
output "composite"
}}

 MRのアルゴリズムの中身について解説する。

-6行目のif文の条件式の前半はMillerの定理の「a^r≡1」に対応し、後半はj=0
のときの「&mimetex("a^{{2^j} \times r} \equiv 1");」に対応する。y[0]==n-1はmod nでy[0]=-1であるこ
とに注意。
-11行目のif文の条件式はj≠0のときの&mimetex("a^{{2^j} \times r} \equiv 1");に対応する。

 このMiller-Rabinテストの問題は次の2点である。

-入力nが素数なのに、"composite"と出力されること→[1]
-入力nが合成数なのに、"prime"と出力されること→[2]

[1]nが素数の場合

 Millerの定理より、MRは"composite"を出力しない。なぜならば、いきなり1になるか、途中で-1が出てくるかのどちらかである。よって、必ず「output "prime"」の命令にひっかかる。

[2]nが偶数の場合

 Miller-Rabinテストで、"prime"を出力する確率は(1/4)^tになる。ただし、tは繰り返し回数とする。

 以上でMiller-Rabinテストの仕様についての解説は終えた。

 Miller-Rabinテストでは、「nが合成数」かつ「MR(n)="reject"」が成り立つときの確率が1/2以上であることを期待したい。ここで主張を明確にするために、次の2つの言葉を定義する。

#divid(s,thorem)
-「&mimetex("a^r \not{\equiv} 1 \pmod{n}");」かつ「任意のj∈{0,…,k-1}において、&mimetex("a^{{2^s} \times r} \not{\equiv} -1 \pmod{n}");」が成り立つとき、aを''nに対するMR-witness''と呼ぶ。
-「n:合成数」かつ「a:nのMR-witnessでない」が成り立つとき、aを''nに対するMR-liar''と呼ぶ。
#divid(e,thorem)

 Fermat-wintess/liarのときの議論と同様に、「nに対するMR-witness」と「nに対するMR-liar」も次の関係式が成り立つ。

#divid(s,thorem)
「nに対するMR-witness」+「nに対するMR-liar」=n-1
#divid(e,thorem)

#divid(s,notice)
例1:意味と使い方に慣れることを目的として、Miller-Rabinテストを用いることによって、n=105が素数かどうかを判定してみる(n=105=3・5・7が成り立つので本当は素数ではないのだが、それは気にせずアルゴリズム的にどう動くか調べる)。

 &mimetex("n-1=104={2^{3}} \times 13");が成り立つから、まずs=3,r=13とセットされる。次に、ランダムに選んだ整数値がa=8であったとする。すると、y[0]=8SUP{13};≡8 (mod 105)になる。このy[0]はmod 105の世界で1 or 104(=n-1)ではないので、else以下のfor文が実行される。

-y[1]←y[0]^2≡8SUP{2};≡64 (mod 105)
-y[2]←y[1]^2≡64SUP{2};≡1 (mod 105)

 後は、ずっとy[j]は1 (mod 105)になる。そのため「output "prime"」が実行されずに、最終的に「output "composite"」が実行される。よって、n=105は素数ではない。 ◇
#divid(e,notice)

#divid(s,notice)
例2:次にカーマイケル数が入力されても、Miller-Rabinテストがうまく動作することを確認する。ここでは例として最小のカーマイケル数であるn=561=3×11×17を考える。先ほどのフェルマーテストではこのときに問題があった。Miller-Rabinテストではこの問題が解決されていることを確認しておかなければならない。

 n-1=560=2SUP{4};×35が成り立つので、s=4,r=35とセットされる。

-a=2
-aSUP{35};=2SUP{35}; (mod 561)≡263
-aSUP{70};=166
-aSUP{140};=67 ←aSUP{280};=1となる直前だが、mod nの世界では-1ではない
-aSUP{280};=1
-aSUP{560};=1

 a=2のとき、aSUP{r};の2乗ずつしていくと、aSUP{n-1};までに法nの世界で-1は一度も登場しない。つまり、a=2はMR-witnessになる(n=561にはMR-witnessが少なくともひとつ存在することが確認できた)。

 同様に、a=3,…,560まで調べていくと、例えばa=5のときは「nに対するMR-witness」になるし、a=50のときは「nに対するMR-liar」になる。よって、n=561のときにMR-witnessとMR-liarがあることがわかった。実際には、(MR-witnessの数)>(MR-liarの数)であることがわかっている。よって、「MR(561)="reject"」が成り立つ確率は1/2以上になる。以上により、カーマイケル数の一種であるn=561であっても、Miller-Rabinテストは素数テストとしてうまく働くことが確認できた。
#divid(e,notice)

 最後に気になるのは、どのような整数nを選んだとしても、「nが合成数」かつ「MR(n)="reject"」が成り立つ確率が1/2以上であるかどうかという点である。この疑問に関しては肯定的な意味で解決されている。それを定理としてまとめると次のようになる。

#divid(s,thorem)
[定理]Miller-Rabinテストは、Primes∈coRPを証言する。即ち、Pr[MR(合成数)=accept]<1/2が成り立つ(=1/2にはならない)。
#divid(e,thorem)

#divid(s,thorem)
[定理]「nが合成数」かつ「MR(n)="reject"」が成り立つ確率が1/2以上である。言い換えると、「nが合成数」かつ「MR(n)="accept"」が成り立つ確率は1/2より小さい。
#divid(e,thorem)

#divid(s,proof)
[証明]nを合成数とする。「nに対するMR-liar」であるようなaの個数が、全体の半分以下であることを示すことができればよい。ここで、全体とは&mimetex("\mathbb{Z}_n^*");なので、その個数はφ(n)である。

 まず、nがカーマイケル数か否かによって場合分けして考える。

[1]nがカーマイケル数でないとき

 nがカーマイケル数でなければフェルマーテストであっても問題なかった。Miller-Rabinテストはフェルマーテストの改良版なので、アルゴリズム的に問題なく、次の関係(集合の包含関係)が成り立つ。

(「nに対するMR-liar」であるようなaの集まり)~
⊆(「nに対するFermat-liar」であるようなaの集まり)~
<&mimetex("\mathbb{Z}_n^*");

 よって、「nに対するMR-liar」であるようなaの集まりの要素の個数は1/2×φ(n)以下である。

[2]nがカーマイケル数であるとき

 問題はこちらの場合である。「nに対するMR-liar」(mimetex("a^{{2^s} \times r} \equiv -1 \pmod{n}");)であるようなaの集まりのままでは考えにくいので、これを包括するような集合を新たに考え、その集合であっても&mimetex("\mathbb{Z}_n^*");の真部分群であることを示すことができればよい。mimetex("a^{{2^s} \times r} \equiv -1 \pmod{n}");を満たすようなaの集まりをAとする。

 また、tをmimetex("a^{{2^s} \times r} \equiv 1 \pmod{n}");を満たすようなaが存在するときにおける、sの最大値とする。このtを使って、新しい集合を、&mimetex("a^{{2^t} \times r} \equiv \pm 1 \pmod{n}");を満たすようなaの集まりと定義できる。この集合をBとする。A⊆Bであることに注意。目的はB<&mimetex("\mathbb{Z}_n^*");を示すことである。真部分群であることを示すには、部分群であることと真の部分群であることの2つを示せばよい。この2つを順を追って証明していく。

(i)Bが&mimetex("\mathbb{Z}_n^*");の部分群であることを示す

 部分群であることを示すためには逆元の存在と演算が閉じていることをいえればよい。

-Bは逆元が存在する。なぜならば、&mimetex("b^{{2^t} \times r} \equiv \pm 1 \pmod{n}");を満たす値であるbは、2乗すれば必ず1に一致する。つまり、逆元は必ず存在するからである(自分自身)。
-c,d∈Bならば、cd∈Bが成り立つ。なぜならば、c,d∈Bより、cは&mimetex("c^{{2^t} \time r} \equiv \pm 1 \pmod{n}");を満たす値、dは&mimetex("d^{{2^t} \times r} \equiv \pm 1 \pmod{n}");を満たす値である。よって、&mimetex("cd^{{2^t} \times r} \equiv \pm 1 \pmod{n}");が成り立つので、cd∈Bが成り立つ。一言で言えば、±1をを掛ければ、結局±1になるからである。

 よって、B≦&mimetex("\mathbb{Z}_n^*");が成り立つ。

(i)Bが&mimetex("\mathbb{Z}_n^*");の真部分群であることを示す

 これを示せば、&mimetex("\mathbb{Z}_n^*");からBを除いた集合が空集合であればよい。そこで背理法を用いる。そこで、&mimetex("\mathbb{Z}_n^*");からBを除いた集合が空集合でないと仮定する。

 カーマイケル数は3つ以上の素因子を持つので、少なくともn=nSUB{1};×nSUB{2};と記述される。ただし、nSUB{1};,nSUB{2};とも奇数かつGCD(nSUB{1};,nSUB{2};)=1である。

 また、{{2SUP{t};}×r}乗するとmod nの世界で-1に一致するような値がAの要素に存在する(これはAの定義から明らか)。この値をeとする。つまり、e^{{2^t}×r}≡-1 (mod n)が成り立つ。

 ここで、a:=e (mod n_1)と定義する。すると、中国人の剰余定理より、次の連立合同式を満たすようなa∈Zが存在する。

-a≡e (mod nSUB{1};)
-a≡1 (mod nSUB{2};)
-ただし、GCD(nSUB{1};,nSUB{2};)=1

 まず、&mimetex("a^{{2^t} \times r} \equiv e^{{2^t} \times r} \pmod{n_1} \equiv -1 \pmod{n_1}");(この結果を,箸垢襦砲成り立つ。また、「&mimetex("a^{{2^t} \times r} \equiv 1 \pmod{n_1}");」(この結果を△箸垢襦砲眄り立つ。

 よって、&mimetex("a^{{2^t} \times r} \equiv 1");と考えると△鉾燭掘&mimetex("a^{{2^t} \times r} \equiv -1");と考えると,鉾燭垢襪里如&mimetex("a^{{2^t} \times r} \not{\equiv} \pm 1 \pmod{n}");になる(modがnになっていることに注意)。よって、&mimetex("a( \in \mathbb{Z}_n^*)");はBに属しない。

 そもそもA⊆Bのように設定したはずなのに、aはAに含まれ、Bに含まれないということはありえない。よって、矛盾が生じた。 □
#divid(e,proof)

 これでMiller-Rabinテストが素数テストとして有効であることが示された。

 後は、「nが合成数」かつ「MR(n)="accept"」が成り立つ確率がどのくらいの値以下であるかどうかを評価できれば嬉しい。これがわかれば、どのくらい多段にすれば十分かどうかを正確にわかる。

 証明は省くが、確率として次のような結果が知られている。

#divid(s,thorem)
[定理]「nが合成数」かつ「MR(n)="accept"」が成り立つ確率は1/4以下である。
#divid(e,thorem)

 MR(n)をk回独立に繰り返した全体をMR_k(n)とする。MRSUB{k};(n)は内部でk回MR(n)をサブルーチンとして呼び出す。MR(n)がすべて"accept"ならばMRSUB{k};(n)も"accept"、MR(n)がひとつでも"reject"ならばMRSUB{k};(n)は"reject"とする。つまり、1回でも"reject"が出力されたら、MRSUB{k};(n)も"accept"ということになる。

 よって、次の定理が得られる。

#divid(s,thorem)
[定理]「nが合成数」かつ「MRSUB{k};(n)="accept"」が成り立つ確率は(1/4)SUP{k};以下である。
#divid(e,thorem)

#divid(s,proof)
[証明]MRSUB{k};(n)は内部でシーケンシャル、しかもk個それぞれが独立にMR(n)をサブルーチンとして呼び出すので、全体の確立は(1/4)SUP{k};以下となる。 □
#divid(e,proof)

#divid(s,notice)
例1:k=10(10回繰り返す)であれば、nが合成数なのにacceptされてしまう確率は1/2SUP{20};(≒1/10SUP{6};)になる。 ◇
#divid(e,notice)

#divid(s,notice)
例2:1,000ビットより大きい素数を探すときは、誤差が(1/2)SUP{80};より小さな確率となるようにk=3を選べば十分である。 ◇
#divid(e,notice)

#divid(s,thorem)
[定理]n≧3が奇数の合成数であるとき、集合{1,…,n-1}の中にはnと素であるような、nのMR-liarの数が高々(n-1)/4個しか存在しない。
#divid(e,thorem)

 この定理は「nがPrimesに含まれない」⇒「Pr[MR(n)=accept]≦1/4」を意味する。

#divid(s,proof)
[証明]n(≧3)を奇数の合成数とする。

 このとき、「GCD(a,n)=1かつ&mimetex("a^r \equiv 1 \pmod{n}");…(*)」または「&mimetex("r \in \{0,1,…,k-1\}");に対して、&mimetex("a^{2^s r} \equiv -1 \pmod{n}");…(**)」が成立するa∈{1,…,n-1}の総数を評価したい。そのようなaが存在しなければ評価は終了する。

 まず、そのようなMR-liarであるaが存在すると仮定する。このとき、(**)が成立しないMR-liarであるaも存在する。aが(*)を満たせば、-aは(**)を満たす。

 ここで、GCD(a,n)=1かつ(**)を満たすaが存在するsの最大値をtとする。そして、mをm:=2SUP{t};r、nの素因巣分解を&mimetex("\prod_{p|n} p^{e(p)}");と定義する。さらに、次の4つの&mimetex("\mathbb{Z}_n^*");の部分群を定義する。

-&mimetex("J=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{n-1} \equiv 1 \pmod{n} \}");
-&mimetex("K=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{m} \equiv \pm 1 \pmod{p^{e(p)}(\forall p|n) \}");
-&mimetex("L=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{m} \equiv \pm 1 \pmod{n} \}");
-&mimetex("M=\{ a+n \mathbb{Z}: GCD(a,n)=1, a^{m} \equiv 1 \pmod{n} \}");

 このとき、&mimetex("M \subset L \subset K \subset J \subset \mathbb{Z}_n^*");が成り立つ。よって、nのMR-witnessが存在しない、nに素な∀のaに対して剰余類a+nZはLに属する。

 後は、Lの指数&mimetex("\mathbb{Z}_n^*");が少なくとも4であることを示せばればよい。

 Kの任意の元の平方がMに含まれるので、MのKでの指数は2のべき乗である。LのKにおける指数は、2のベキである。これを例えば2SUP{j};とする。j≧2のときはLの指数&mimetex("\mathbb{Z}_n^*");が少なくとも4である。後は、j=0,1のときにLの指数&mimetex("\mathbb{Z}_n^*");が少なくとも4であることかどうかを確認する。

[1]j=1のときを考える

 nは2つの素因数を持つ。よって、nはカーマイケル数ではない(∵カーマイケル数の素因数は3個ある)。よって、Jは&mimetex("\mathbb{Z}_n^*");の真部分群であり、Jの&mimetex("\mathbb{Z}_n^*");での指数は少なくとも2である。LのKでの指数もmの定義により2であるので、Lの&mimetex("\mathbb{Z}_n^*");での指数は少なくとも4である。

[2]j=0のときを考える

 nは素数ベキである。この場合、Jがちょうどp-1この元を持つ、即ち巡回群&mimetex("\mathbb{Z}_{p^e}^*");の位数p-1の部分群の元であることを証明することができる。よって、Jの&mimetex("\mathbb{Z}_n^*");での指数はn=9を除いて少なくとも4である。n=9に対しては命題が直接示される。 □
#divid(e,proof)


*素数のランダムな選択 [#q1f87006]

 Miller-Rabinテストなどで効率的に素数を生成できることは示されたが、まだ固定されたビット長の素数の生成についてはまだ言及していない。実際に多くの暗号スキームの鍵生成アルゴリズムなどでは、固定されたビット長のランダムな素数を生成する必要が生じる。

 ここではkビットの素数を生成したいとする。そのとき、次の手順で実行すればよい。

1:kビットの奇数nをランダムに生成する。ただし、nの最初と最後のビットを1とおき、残りのk-2ビットの数をそれぞれ独立でランダムに生成する。

2:このnが素数かどうかを調べる。

 最初に素数表を使用して、nがある一定の値であるBよりも小さい素数で割り切れるかどうかを調べる。利用するハードウェアやソフトウェアがMiller-Rabinテストでの割り算をどのくらい速いかによって、このBの値は決定される。Miller-Rabinテストより、試行割算法の方がずっと効率的な場合は、より大きなBを選ぶとよい。一般的な例として、B=106と選ばれる。nの約数が見つからなければ、以降を実行する。

 次に、k回の繰り返しのMiller-RabinテストのアルゴリズムMR_kにnを入力する。ここでnのMR-witnessが見つからなければ、nは素数である。見つからなければ、nは合成数であるので、ステップ1に戻ってやり直す。

3:最終的に得られたnはkビットの素数とみなせる。


*参考文献 [#ed1f0be4]

-ゼミノート
-講義ノート
-『現代暗号の基礎数理』
-『暗号理論入門』
-『応用代数学入門』
-『Introduction to Algorithms』