*目次 [#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テスト]]
-確定的
--[[エラトステネスの篩]]
--[[Millerテスト]]
--[[Adleman-Rumelyテスト]]
--[[Cohen-Lenstraテスト]]
--[[AKSテスト]]
--[[Lucasテスト]]



*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』