暗号の数理要綱

暗号の数理要綱

4.4 素数判定

 RSA暗号においては，100〜200桁程度の(ランダムな)素数を2つ用意する必要がある。RSA 暗号の安全性は，大きな数を素因数分解することは非常に難しい，という事実に基づいているが，

大きな素数を用意するためには，その数が素数であることを確かめなければならず，そのためには，

その数が素因数分解できない，ということを示さなければならない，という矛盾が生じてしまう。

この，一見，致命的とも思えるような矛盾を巧妙に回避する方法が素数判定である。素数判定 とは，

• 「ある数が素数ではない」ということを示す方法 のことである。

「ある数が素数である」ことを示すような，どの数にでも使える効率的な方法は知られていな い。「素数ではない」ことを示すような判定法を何回適用しても「素数ではない」ということを示 すことができなかったとしたら，その数は，かなり高い確率で素数らしい，ということになる。

RSA暗号においては，そのような数を素数であると見なして，素数であるとして使う。万が一，

それが素数ではなかったとしたら，復号化の過程で問題が発生し，元の平文に復号化できなくなる かもしれないが，その確率が非常に小さければ問題なかろう，という発想である。

4.4.1 フェルマー・テスト

nという自然数を一つ固定し，これが素数であるかどうかを判定することを考える。

nの倍数ではない自然数aがあって

aⁿ⁻¹̸≡1 mod n (∗)

となったとしよう。もし nが素数なら，フェルマーの小定理より，このようなことは起こり得な い。従って，もしこのようなことが成立するならば，「 nは素数ではない 」 ということの証明に なる。

特に，1< a < nという自然数aは nの倍数となることはないから，このようなある aで(∗)

のようなことになれば，因数分解をすることなく，nは合成数であることが証明できることになる。

任意の自然数bは，ある自然数kと，0<=r <=n−1 となる自然数rがあってb=kn+rと書 ける。2項展開すると，ある自然数qがあって，

bⁿ⁻¹= (kn+r)ⁿ⁻¹=rⁿ⁻¹+ (n−1

1 )

rⁿ⁻²kn+· · ·+ (kn)ⁿ⁻¹=rⁿ⁻¹+nq となることがわかるから，

bⁿ⁻¹≡rⁿ⁻¹ mod n

である。従って，このフェルマーの小定理を使って，nが素数ではないことを示そうとした場合，

aとして，2<=a <=n−1 となるものだけを考えれば十分であることがわかる。

また，2<=a <=n−1 となるaに対してGCD(a, n)̸= 1であるなら，nは素数ではあり得ない。

GCD(a, n)はユークリッド互除法で短時間で計算できるから，フェルマーの小定理を適用する前

に，まず，この判定法行ってみることは時間の節約になる。

定義 4.1 nを合成数とする。1< a < nかつGCD(a, n) = 1となるあるaに対して aⁿ⁻¹≡1 mod n

となる時，nは aを底とする擬素数であるという。

これは，nは合成数であるにも関わらず，aを使う限りにおいて，合成数であることを示すこと はできない，という意味である。

このように，1< a < nとなるaに対して

(1) GCD(a, n)を計算し，

(2) aⁿ⁻¹≡1 mod nとなるのかどうかを試す ことをフェルマー・テストという。

このフェルマー・テストは，実は意外なほど強力である。

例えば，1〜1,000 までの中に素数は168個 ある。これは，残りの832個 は合成数で あるということを意味する。この中で，2を底とする擬素数は，

341, 561, 645

の3個しかない。すなわち，この3個以外の829 個 の合成数は全て，a= 2 だけを 使うことにより，フェルマー・テストで合成数であることを証明できる，ということに なる。

なお，この3個の合成数は，3を底とする擬素数ではないので，2と3だけを使えば，

1,000までの全ての合成数を，フェルマー・テストで判定できる。

また，10,000までの全ての合成数は，2，3，5，7 だけを使って，フェルマー・テスト により，合成数であることを判定できる。100,000 までの合成数で，この4個で判定 できないものは，

29341, 46657, 75361

の3個だけである。

実際にこのフェルマー・テストの対象となるnは非常に大きな数なので，小さなaから順に試 して行く，という方法を取ることはできない。1 < a < nを満たすaをランダムにとり，何回か 試して，合成数であることを証明できなければ，素数である確率が高い，と見なすわけである。

定義 4.2 nを奇数の自然数で，さらに合成数であるとする。2<=a <=n−1となるn と互いに素 な aに対してaⁿ⁻¹≡1 ( mod n)となる時，nをカーマイケル数と言う。

nがカーマイケル数なら，ランダムに選ばれた 1< a < n が GCD(a, n) = 1 なら（そうなる 確率は高い），そのaでは，フェルマーの小定理でnが合成数であることを示すことはできない，

ということである。

561 = 3·11·17はカーマイケル数であることが知られている。また，カーマイケル数は無限に 存在することも知られている。カーマイケル数がどのようなものであるのかは，以下の定理によっ て，良くわかっている。

定理 4.3 奇数の合成数n >= 3がカーマイケル数であるための必要十分条件は，次の2つの条件が 成り立つことである。

(1) n の素因数は平方以上を含まない。すなわち，p が n の素因数なら，p² は n の約数では ない。

(2) pが nの素因数なら，p−1は n−1 の約数である。

4.4.2 Miller-Rabin 法

素数判定を行うためのフェルマー・テストは，カーマイケル数が存在するという理由から，もち ろん完全な判定法ではないが，それ以上に，実際に試してみると，許容できる計算時間の範囲内で は，無視できない割合で判定ミスが起こることがわかる。

実際に使用するためには，より効率的で，かつ精度の高い判定法が必要となる。ここでは，実際 に素数判定に使われているMiller-Rabin法について述べる。

素数判定法とは，

「素数が必ず持っていなければならない性質Ａ」

というものを一つ選ぶことである。そして，ある数がこの「性質Ａ」を持っていない，というこ とを示すことができれば，その数は素数ではない，ということを決定できることになる。

例えばフェルマー・テストでは，「フェルマーの小定理が成り立つ」というのが，ここでの「性質 Ａ」ということになり，フェルマーの小定理が成立しない数は合成数である，と判定できる。

素数が満たすべき性質というのは無数にあり，どれが判定法として適切か，というのは，非常に 難しい問題である。

1976年，G.L.Millerが提案したのは次のような性質である。

n >= 3 を素数であると仮定する。

n−1 は偶数なので，2で割り切れる。2 の素因数を全て抜き出すことにより，q を奇数として n−1 = 2^kqと書ける。ここでk≥1 である。

nは素数と仮定したので，フェルマーの小定理より0< b < nとなる任意のbに対して b^2kq=bⁿ⁻¹≡1 modn

である。そこで，

b^q, b^2q, b^22q, · · · b^2k−1q, b^2kq

というk+ 1個の数を modnで考える。右端のものは1となるので，この中に1 があること は保障されている。そこでj≥0を，b^2jq modn= 1 となる最小の非負整数とする。

( b^2iq

)2

=b^2iq·2 =b^2i+1q なので，どこかで1 が現れたら，その右側は全て 1 であることに注 意。特にj= 0ならば，全てが1である。

さて，j≥1とする。b^2jq−1≡0 modnであるが，

b^2jq−1 = (

b^2j−1q−1 ) (

b^2j−1q+ 1

)≡0 modn

と因数分解してみると，j は b^2jq−1 modn= 0 となる最小のものだったので，b^2j−1q−1̸= 0 modnである。従ってb^2j−1q+ 1 = 0 modnでなければならない。すなわち，

b^2j−1q≡ −1 modn

である。このときnが素数であるという性質を使っていることに注意すること。nが素数でなけれ ば，b^2jq−1≡0とb^2j−1q−1̸≡0 modnからb^2j−1q+ 1≡0はでてこない。

これが意味することをまとめると次のようになる。

命題 4.4 n≥3を素数とし1< b < nとする。また，qを奇数としてn−1 = 2^kq であるとする (k≥1)。この時，b^q = 1 modnであるかまたは，b^2rq ≡ −1 modnとなる 0≤r≤k−1が存 在する。

これが，素数が満たさなければならない一つの性質であり，これを満足しないn は「素数では ない」と判定できることになる。具体的な判定手続きは次のようになる。

（なおここで，−1 ≡n−1 modnであることに注意。すなわち，実際の計算では−1 ではな く n−1が現れることが普通である。）

(1) 奇数n≥3 を一つとる。これが素数であるかどうか判定したい。

(2) qを奇数，k≥1としてn−1 = 2^kqとする。

(3) 1< b < nとなる bを一つ選ぶ。

(4) もし(b, n)̸= 1 ならばnは素数ではないと判定できる。以下，(b, n) = 1であったとする。

(5) b^q modn =±1 ならば，n は b を使う限りにおいては「素数ではない」と判定できない。

すなわち，素数である可能性がある。別のbを選ぶために (3)に戻る。

(6) b^q modn ̸=±1 の場合，j ≥1 に対して b^2jq modnを計算して行くのだが，

( b^2iq

)2

= b^2i+1q なので，b^q modn=m0 として，mj+1= (mj)² modnを計算して行けば良い。

(7) ある1≤j≤k−1で mj=−1となったら，nはbを使う限りにおいては「素数ではない」

と判定できない。すなわち，素数である可能性がある。別のbを選ぶために (3)に戻る。

(8) 全ての1≤j ≤k−1 で m_j ̸=−1 ならば，命題4.4 より，そのようなことは素数では起こ り得ないことなので，nは合成数であると判定できる。

カーマイケル数はフェルマー・テストでは合成数であることを判定できなかった。最小のカーマ イケル数561 = 3·11·17に関して，このMiller法を試してみよう。

561−1 = 560 = 2⁴·35であるから，1< b <560 であり(b,561) = 1となるb に関して，

b³⁵ mod 561, b^2·35 mod 561, b^22·35 mod 561, b^23·35 mod 561

を計算してみる。

b= 2 を採用してみよう。35 = 32 + 3 = 2⁵+ 3であるから，2³⁵= 2²⁵⁺³= 2²⁵·2³である。高 速指数計算法より，

2² mod 561 = 4, 4²= 2²² mod 561 = 16, 16²= 2²³ mod 561 = 256, 256²= 2²⁴ mod 561 = 460, 460²= 2²⁵ mod 561 = 103, 103·2³= mod 561 = 263

であるから，2³⁵ mod 561 = 263 である。

263² mod 561 = 2^2·35 mod 561 = 166 166² mod 561 = 2^22·35 mod 561 = 67

67² mod 561 = 2^23·35 mod 561 = 1

となり−1は出てこない。従って，底として2を使うだけで，561は合成数であると判定できる。

定義 4.5 bを固定した時に，このテストをパスしてしまう合成数nを，bを底とする強擬素数と いう。

強擬素数はいくらでも存在する。例えば25は，25−1 = 24 = 2³·3 であり，(7,25) = 1なの で，7 を底としてMillerテストを行ってみると，

7³ mod 25 = 18, 18²= 7^2·3 mod 25 = 24 =−1 mod 25 となり強擬素数となる。

しかし，今度は2 を底としてMillerテストを行ってみると，

2³ mod 25 = 8, 8²= 2^2·3 mod 25 = 14, 14²= 2^22·3 mod 25 = 21

となり −1 は出てこないので，合成数であると判定できる。

このMillerテストがフェルマー・テストと根本的に異なる点は，「カーマイケル数的」な数が存

在しない，ということである。これは，1980年にM.O.Rabinによって示された。

定理 4.6 n≥3 を奇数とする。n/4 個よりも多い1< b < nに対してnが Millerテストをパス するならば，nは素数である。

すなわち，全ての底について，テストをすり抜けてしまうような合成数は存在しない，というこ とである。これは実に素晴らしい結果ではあるが，現実的には，10¹⁰⁰ 程度の大きな nに関して n/4 個の底についてMillerテストを行うことは不可能なので，完全な判定はできない。(例えば

n= 10¹⁰⁰ の場合，n/4 は10⁹⁹ よりも大きいことに注意。n/4≈10²⁵ などと錯覚しないように。

10²⁵=n/10⁷⁵ である。もちろん10²⁵ でさえ，手に負えないほど大きな数である。) しかしながら，定理4.6の対偶をとると，

「nが合成数ならば，n/4個よりも多いb を底として強擬素数となることはない。」

ということであるから，nが合成数であるとすると，ランダムに選んだ1< b < nと(b, n) = 1 を満たすb に関して，nが強擬素数となる確率は1/4 以下である。さらに，r 個のランダムに選 んだb 全てに関して強擬素数となる確率は(1/4)^r以下である。

例えばr= 20なら，(1/4)²⁰≈1/10¹²であるから，合成数が，20個のランダムに選んだ底に対 して強擬素数となる確率は「1兆分の一」ということになる。ということは，20個のランダムに選 んだ底に対してMillerテストをパスするような数については，「素数である確率が非常に高い」と 言えることになる。

ただしこれはあくまで確率であって，いくら小さくても0 にはならない。完全に素数であるこ とを保障するためには，n/4個よりも多いbに関して Millerテストをパスすることを示さなけれ ばならないことを注意しなければならない。

4.4.3 Miller-Rabin 法の計算量

Miller-Rabin法は，上記の判定確率が評価できるという優れた点を持っていると同時に，計算

量が少ない，大きな利点も持ち合わせている。

n−1 = 2^kqとした時，kという数の大きさが問題となるが，このkは最大でn≈2^k となるく らいの数であり，およそ log₂n程度である。

例えばn= 10²⁰⁰ならばlog₂10²⁰⁰≈664程度の数である。1回の計算は，2乗して modnを とるというものであり，それを最大で 600回程度行うだけなので，それほど計算時間を必要とせ ず，十分に実用可能である。