7 : 03 強擬素数

ミラーテストと強擬素数（きょうぎそすう）

2003年 1月29日
記事ID d30129

「RSA暗号と擬素数（ぎそすう） - JavaScript」では、 巨大な整数が素数であるかどうか調べる「確率的」検査法、フェルマーテストを強引に JavaScript 上にもちこんだ。 先に進む前に、関連する話題として、ミラー（Miller）の素数判定法と強擬素数（きょうぎそすう）に触れておく。

ミラーのテスト

巨大な整数が素数か素数でないかを知るのに、 フェルマーテストは実用上それなりに有効だ。 素数でない数（合成数）のほとんどはフェルマーテストでふるい落とされる。 しかし素数でないにもかかわらずフェルマーテストに合格する「擬素数」がわずかながら存在する。

ミラーテストはフェルマーテストの改良版のようなもので、 フェルマーテストより多少計算量は増えるかわりに、 「ニセ素数」に対する耐性がかなり向上する。

n-1を2で割って……

ミラーテストの原理は単純だ。 たとえば、n = 12377 を例に考えてみる。 この数は素数だ。 ミラーテストでは検査したい数 n より1小さい数 n-1 に注目する。 いま考えている例では、n-1 = 12376。 これを2で割れるだけ割る。
12376 ÷ 2 = 6188
6188 ÷ 2 = 3094
3094 ÷ 2 = 1547
ここで商が奇数になって、もうこれ以上2では割れない。要するに、
12377 = 2³×1547

この計算で出てきた４つの数――
1547, 3094, 6188, 12376
のうち、初めの数は n-1 を2で割れるだけ割って残った奇数、 最後の数は n-1 そのもので、となりあう項は次々と2倍、2倍の関係になってる。 これらをある自然数 b 例えば2の肩に乗せてみると――
2¹⁵⁴⁷, 2³⁰⁹⁴, 2⁶¹⁸⁸, 2¹²³⁷⁶
――この最後の数 2¹²³⁷⁶ は n が素数のときの n-1 乗なので、 フェルマーの定理から ≡1 (mod n) だ。
2¹²³⁷⁶ ≡ 1 (mod 12377)

さて、いま考えている数列、
2¹⁵⁴⁷, 2³⁰⁹⁴, 2⁶¹⁸⁸, 2¹²³⁷⁶
は、指数（肩の数）が2倍2倍に増えていく列なので、全体としては前の数の2乗が次の数になっている。例えば
(2¹⁵⁴⁷)² = 2^1547×2 = 2³⁰⁹⁴

これを mod 12377 で考えると、最後の項 2¹²³⁷⁶ は ≡1 なのだから、 そのひとつ前の項は二乗して ≡1 になるような数でなければならない。 つまりひとつ前の数も ≡1 であるか、または ≡ -1 つまり ≡12376 (mod 12377) ではないかと思いつく。 もしひとつ前の数が ≡1 であるとしたら、同じ理屈から、そのさらにひとつ前は ≡±1 ではないか？　この推測は、ある意味で正しく、ある意味で正しくない。 詳しく考える前にとりあえず実際の数値例で調べてみよう。

<script type="text/javascript">
_debug( Bigint.powmod( 2, 1547, 12377 ) );
_debug( Bigint.powmod( 2, 1547*2, 12377 ) );
_debug( Bigint.powmod( 2, 1547*4, 12377 ) );
_debug( Bigint.powmod( 2, 1547*8, 12377 ) );
</script>

結果
Debug: 12376.
Debug: 1.
Debug: 1.
Debug: 1.

次々に前の数の二乗になってゆく列
2¹⁵⁴⁷, 2³⁰⁹⁴, 2⁶¹⁸⁸, 2¹²³⁷⁶
は、mod 12377 においては、
-1, 1, 1, 1
と合同であることが分かった。最初の-1を二乗すると1、あとは何度二乗しても1の二乗は1、という関係になっている。底を3にして、
3¹⁵⁴⁷, 3³⁰⁹⁴, 3⁶¹⁸⁸, 3¹²³⁷⁶
で同じ実験をしてみる。

<script type="text/javascript">
_debug( Bigint.powmod( 3, 1547, 12377 ) );
_debug( Bigint.powmod( 3, 1547*2, 12377 ) );
_debug( Bigint.powmod( 3, 1547*4, 12377 ) );
_debug( Bigint.powmod( 3, 1547*8, 12377 ) );
</script>

結果
Debug: 11703.
Debug: 8704.
Debug: 12376.
Debug: 1.

今度は3項めで 12376≡-1 が現れた。そのひとつ前は「2乗すると≡12376 になる数」だが、さしあたって、この数には興味ない。 この例では、1547×8乗 つまり 12376乗、言い換えれば n-1 乗して初めて≡1になる。 いずれにしても n が素数なら初めて≡1になる場所の一個前の項は、≡-1 だ。 ただし最初の項からすでにいきなり ≡1 になっている場合は「一個手前」がそもそも存在しないので、例外。 まとめると、n が素数である限りにおいて、 上の形の数列を mod n で考えると、
1, 1, 1, ... , 1
のようにぜんぶ ≡1 か、あるいは、
... , -1, 1, 1, ... , 1
のように、どこか途中（最初でもいい）で ≡ -1 が現れて、そこ以降はぜんぶ ≡1 になるか、のいずれかだ。 以下でこのことをきちんと証明しよう。

x²≡1 が x≡±1 以外の解を持ちうるか？

何をきちんとしたいかというと、いま、「ある数 x を平方したら≡1になるとき、x ≡±1 であろう」と考えているのだが、 このことは本当は一般には正しくない。例えば、3の2乗は9だから、mod 8 で考えると、
3² ≡ 1 (mod 8)
であって、±1以外の数（ここでは3）を二乗したら≡1ということが実際ありうる。 このように、剰余類の上での算術では、 通常の数体（例えば有理数）の上での算術ではあり得ないような「変なこと」（1でも-1でもないくせに、二乗すると1になる）が起きて話がややこしくなるようだが、 ミラーテストはむしろこのことを逆用する。簡単にいうと、n が素数なら「変なこと」は起こらず、二乗して1になるものは±1なのだが、 n が素数でない場合には上に見たように一般にこのことは成り立たず「変なこと」が起きてくるので、 「変なこと」が起きていたら n は素数であり得ない、と判定できる。 抽象的にいうと、n が素数の場合の剰余類 Z_n はいろいろな意味で n が合成数の場合とは異なる特別な構造を持っている。 かたい話はともかく、2以上の自然数 b を二乗して ≡1 (mod n) になるということは、
b² を n で割ると1余る
ということだから、1引いたら余りが出ないできっかり割り切れる:
b²-1 は n で割り切れる
ということだ。ここで a²-b² = (a+b)(a-b) という公式を使うと、
b²-1 = (b+1)(b-1)
となるが、左辺は n で割り切れるので、もし n が素数ならば左辺を素因数分解したら必ず n という因数が出る。 また b は自然数なので、 右辺にある (b+1) と (b-1) はどちらも自然数であり、この積を素因数分解したらもちろん左辺と同じ結果になるのだから、 (b+1) か (b-1) かのどっちかかから素因数 n が出ることになる。 ということは、b+1 か b-1 の一方は n の倍数で、言い換えれば
b+1 ≡ 0 または b-1 ≡ 0 (mod n)
b ≡ -1 または b ≡ 1 (mod n)
まとめると、n が素数なら、mod n で「二乗して≡1」になる数は≡±1だ。 ここで n が素数ならという仮定が効いていることに注意してほしい。 n が素数でない場合、例えば n=6 のとき、
b²-1 = (b+1)(b-1)
が6で割り切れるからといって、(b+1) または (b-1) のどちらかは6の倍数だとは言い切れない。 b+1、b-1のどちらも6の倍数でないにもかかわらず、例えばb+1が2の倍数でb-1が3の倍数だと(b+1)(b-1)は6の倍数になれる。 6という因数を2と3に分解して格納できるのだ。 しかし例えば n=7（素数）のときは、7はこれ以上分解できないので、 b+1、 b-1 のどちらか一方が必ず7という素因数を持たざるを得ない。 そんなわけで法が素数であるかどうかで違う代数構造になる。

ミラーの判定法の原理と証明

「n が素数のときミラーの数列には（初項が1でない限り） -1 が現れる」ということを証明しよう。まず問題をきちんと言い表しておく。

ミラーの判定法の原理

3以上のある奇数 n が与えられたとして、その数から1を引いた偶数 n-1 を2で割れるだけ割って次の形に書く:
n-1 = 2^ks （s は奇数）

このとき、次の数列を mod n で考えると、 もし n が素数なら、全部の項が≡1 であるか、さもなければ、最後の項より前のどれかの項が≡-1 でそれ以降の項は全部 ≡1 になる。
2^s, 2^2s, 2^22s, 2^23s, ... , 2^2k-1s, 2^2ks

指数部分にまた指数があってちょっと見づらいが、要は2の肩に
2⁰s, 2¹s, 2²s, ..., 2^k-1s, 2^ks が乗っている。

証明

n が素数ならフェルマーの定理によって
2^2ks = 2^n-1 ≡ 1 (mod n)
であることは分かっているから、最後の項は ≡1 になる。 最後の項はそのひとつ手前の項の二乗であるが、 すでに見たように法 n が素数のとき二乗した結果が≡1になるのは、もとの数が≡1または≡-1のときに限られる。 したがって最後の項よりひとつ手前の項は≡1または≡-1である。 もし≡-1なら証明は完了する。さもなければその項は≡1であり、そのまた前の項（もしあれば）の二乗であるから、 同じ議論によってそのまた前の項は≡1または-1である。 このようにしてどこかで≡-1になれば証明は完了する。 さもなければ、そのまた前そのまた前と進んでついにいちばん最初の項までぜんぶ≡1ということになる。 以上がまさに示したいことであった。

一般のミラーテスト

上の例では具体的に分かりやすく底 b を2に固定したが、 底は2以上で n と互いに素なら何でも良い。 実際、上の証明では b=2 という事実は使っていない。 例えば n が 3 でも 5 でも割り切れないことを確認したら、 3 や 5 を底にして良い。素数性判定をしたいのだから、n が 3 や 5 のような小さい素数で割り切れるなら、 そもそもテストの意味がない。 mod n で考えるので、b < n と仮定しても一般性は失われないが、 実際問題 n は大きな（例えば100桁の）整数なので、大きい底は計算量的にも現実的でもない。

ミラーテストの強さ

ある（大きな）奇数 n が与えられたときに上のような数列を作るとする。 で、最初の項が≡1になったら、以下計算するまでもなくぜんぶの項が≡1になるのでその数は合格。 また最初の項か途中の項で≡-1が出たら、それも合格で、そこで計算をやめていい。 他方、最後の項のひとつ手前まできても≡-1が一度も現れない場合、その時点でミラーテスト失格となる。

フェルマーテストでふるい落とされるような合成数は、 絶対にミラーテストに合格できない。 実際、ミラー数列のどこかに1が現れることはミラーテスト合格の必要条件であり、 しかもそれだけではまだ充分でない。 フェルマーテストで落ちる数に対してはミラー数列のどこにも1が現れないのだから、必要最低基準さえ満たさず、お話にならない。 もしミラー数列のどこかに1が現れるとすると数列のその項以降は1になって第k項（最後の項）が1になるが （法nが素数でなくても≡1の数を二乗すれば≡1なので）、 これはフェルマーテストに合格できることを意味している。 したがってフェルマーテストに合格できない数はミラー数列に1が現れず、当然にミラーテストにも合格できない。

次に素数でないくせにフェルマーテストを合格してしまう数、いわゆる擬素数も、 ミラーテストにかけるとほとんどふるい落とされる。 ミラーテストは本質的に「素数 n に対する剰余類が持ち得ない性質」――±1でない類の平方が1になるという性質――を検出しようとする。 ミラーテストに合格するためには、ミラー数列のどこかに1が現れなければならないが、 最初に1が現れる項のひとつ前の項は≡-1であることを要求される。 ±1でないものを二乗して≡1になる、などというのは素数を法とする秩序正しい世界では起こり得ないからである。 ただし、初項からすでに1の場合、この性質についての検証を行うことができない。 また、法 n が素数でないにもかかわらずミラー数列で初めて1が現れる場所のひとつ手前がたまたま≡-1ということが考えられる。 というのも、法 n が素数でなくても、-1 と合同な数の二乗が 1 と合同になるのは確かだからだ。 ±1以外の数の二乗が≡1になれば法が素数でないと断定できるが、 逆に「法が素数でないならつねに二乗すると1になる±1以外の類が存在する」とは断定できないし、 そもそもミラー数列のような（ある剰余類における）ほんの少しの計算例だけでその剰余類の代数構造（「非自明な1の平方根」を持つかどうか） を確定できるわけではない。

そうは言っても、素数でないくせにミラーテストをあざむくのは相当に難しい。 単にフェルマーの小定理の逆を満たすだけでなく、 「Z_nに非自明な1の平方根がある」というしっぽを出さないようにしなければならないからだ。 理論上、いろいろな底に対してミラーテストを実行すると、 ニセ素数は必ずどこかで、テストに失敗するか、 またはフェルマーテストをあざむく擬素数であっても「非自明な1の平方根の存在」をさらけだし、化けの皮がはがれる。 これに対して、フェルマーテストの場合、底をいろいろ変えても素数のふりをし通せるような「とんでもないニセ素数」が存在するのである。 ただし、純粋数学を離れてRSA暗号への現実的応用を考えると、 n は100桁のような巨大な整数であるから、すべての可能な底に対して検査を行うどころか、 その一億分の一の検査すら非現実である。 また、ミラーテストまでしなくても、フェルマーテストでも、充分に実用的ではある。 フェルマーテストをあざむくような擬素数そのものがかなりまれだからだ。

ミラーのテストに合格する数は、強力な素数候補と呼ばれる。 強力な素数候補と認定される数のほとんどすべては実際に素数である。 実際には素数でないのに強力な素数候補にノミネートされてしまうようなずうずうしい数を強擬素数（きょうぎそすう）という。ホントは素数でないくせにあくまでシラをきりつづける強力なニセ素数である。 よっぽど素数に生まれたかったのであろう……。 強擬素数は、フェルマーテストは余裕で合格してしまう。 ミラーテストはフェルマーテストの強化版なので当然のことだ。 同様に、強力な素数候補は、フェルマーテストによっても素数候補となる。 強擬素数は擬素数でもあるが、もちろん逆にすべての擬素数が強擬素数であるわけではない。 10000以下の範囲に素数は1229個あるが、 擬素数（2を底とする）は22個しかない:
341, 561, 645, 1105, 1387, 1729, 1905, 2047, 2465, 2701, 2821, 3277, 4033, 4369, 4371, 4681, 5461, 6601, 7957, 8321, 8481, 8911
このうち強擬素数は 2047, 3277, 4033, 4681, 8321 の5個である。

1387 = 19×73 は素数ではないがフェルマーテストによって素数候補となる擬素数である。 しかしミラーテストは通過できない。

<script type="text/javascript">
// 1387-1 = 1386 = 2×693
_debug( Bigint.powmod( 2, 693, 1387 ) );
_debug( Bigint.powmod( 2, 693*2, 1387 ) );
</script>

結果
Debug: 512.
Debug: 1.

2行めは Bigint.powmod( 2, 1387-1, 1387 ) に相当し、フェルマーテストにあたる。 確かに剰余1を返し、素数候補だ。 しかし、その「平方根」が±1 でなく 512 という「変な」値になっているのでミラーテストで、はねられてしまう。
512×512 = 262144 ≡ 1 (mod 1387)

次に強擬素数 4033 = 37×109 に対するミラーテストを試してみよう。
4033-1 = 4032 = 64×63 だ。

<script type="text/javascript">
_debug( Bigint.powmod( 2, 63, 4033 ) );
_debug( Bigint.powmod( 2, 63*2, 4033 ) );
_debug( Bigint.powmod( 2, 63*4, 4033 ) );
_debug( Bigint.powmod( 2, 63*8, 4033 ) );
_debug( Bigint.powmod( 2, 63*16, 4033 ) );
_debug( Bigint.powmod( 2, 63*32, 4033 ) );
_debug( Bigint.powmod( 2, 63*64, 4033 ) );
</script>

結果
Debug: 3521.
Debug: 4032.
Debug: 1.
Debug: 1.
Debug: 1.
Debug: 1.
Debug: 1.

第2項で 4032≡-1 になり、-1の平方として第3項以降で「もっともらしく」≡1 になっている。 まったく素数にしか見えない。 腹が立つので底を3に変えて化けの皮をはがしてやろう。

<script type="text/javascript">
_debug( Bigint.powmod( 3, 63, 4033 ) );
_debug( Bigint.powmod( 3, 63*2, 4033 ) );
_debug( Bigint.powmod( 3, 63*4, 4033 ) );
_debug( Bigint.powmod( 3, 63*8, 4033 ) );
_debug( Bigint.powmod( 3, 63*16, 4033 ) );
_debug( Bigint.powmod( 3, 63*32, 4033 ) );
_debug( Bigint.powmod( 3, 63*64, 4033 ) );
</script>

結果
Debug: 3551.
Debug: 2443.
Debug: 3442.
Debug: 2443.
Debug: 3442.
Debug: 2443.
Debug: 3442.

底を3に変えるとフェルマーの（弱い）擬素数にすらならないことが分かる（最後の項まで来ても≡1にならない）。 複数の底に対して擬素数でありつづけることは非常に難しいのだ。 なお、この記事では分かりやすくベタでリストを書いたが、実際には大きな指数計算を何度もする必要ない。 「前の項の二乗」の剰余は、「前の項の剰余の二乗」の剰余に等しいので、次のように計算量を大幅に節約できる。

<script type="text/javascript">
var a0 = Bigint.powmod( 3, 63, 4033 );
var a1 = Bigint.powmod( a0, 2, 4033 );
var a2 = Bigint.powmod( a1, 2, 4033 );
var a3 = Bigint.powmod( a2, 2, 4033 );
var a4 = Bigint.powmod( a3, 2, 4033 );
var a5 = Bigint.powmod( a4, 2, 4033 );
</script>

実装上、最初の項で1になれば、その段階で合格となり、以下続けても結論は変わらないので、ただちに中止して良い。 そうでない場合、-1が出ればその段階で合格となり、以下続けても結論は変わらないので、そこで中止して良い。 最後の項のひとつ手前まで来ても-1にならないなら、その段階で不合格である。 最後の項のひとつ手前が ≡±1 でなくても最後の項が≡1になることはありうるが（フェルマーの擬素数の場合）、 この場合は絶対に本物の素数でないので どっちにしても最後の項は実際に計算する必要ない。 理論上、途中で1が出てその前の項が≡±1でなかったなら、本物の素数でないと判断できるので、そこで中止できる。 途中で1が出たらそのあとは1の二乗（つまり1）の剰余（つまり1）を求めるだけなので、 実装上、1が出た瞬間にやめても計算量を極端に減らせるわけではない。

異なる底に対してミラーのテストを反復することを、一般にラビン・ミラー（Rabin-Miller）のテストという。 ラビンによれば、ある底に対してミラーのテストが誤判定（素数でないものを合格させてしまうこと）をする確率は最大でも 1/4 であるという。 したがって、理論的には、ラビン・ミラーテストにより「素数性品質」を定量的に管理できる。 例えば、5つの異なる底に対して有効なミラーのテストをパスした数が「不良品」（実は素数でなかった）という確率は最悪でも
(1/4)⁵ ≒ 0.00098
となる。理論上、フェルマーテストの場合、すべての有効な底に対してどれでやっても擬素数になる可能性が極めてわずかながらある。 ミラーテストを使った巨大な整数の素数性判定では、底の数を増やせば失敗確率を望むだけ小さくできる。