素数判定 - Tools on Number Theory

素数判定法
東京都立大学理学部数学学科
中村研究室
0340465
市来信吾
目標
多項式時間素数判定法の紹介
 計算数論システムNZMATHへの
実装と実験

はじめに

試し割り
1/ 2
 計算量→ O(n lg lg n lg lg lg n)

多項式時間の計算量
 Miller-Rabinテスト
 AKS
準備（ランダウの記号）
f ( x)  O( g ( x)) 

x0 , c, s.t. x  x0  f ( x)  cg( x)
f ( x)  O ( g ( x)) 
~

1
  0, f ( x)  O( g ( x)
)
素数判定法の種類［1/2］

決定性素数判定法（deterministic primality
test）

自然数n が「素数」か「否」か判定する
• 試し割り
• APR （Adleman-Pomerance-Rumely）
• AKS (Agrawal,Kayal,Saxena)
素数判定法の種類［2/2］

確率的素数判定法（probabilistic primality
test）

自然数n が「合成数」か「判定不能」か判定す
る
• Fermat テスト
• Solovay-Strassen テスト
• Miller-Rabin テスト

多項式時間アルゴリズム
Fermat の小定理
素数 p と任意の整数 a に対し
a  a (mod p)
p
特に
p|a
a
ならば
p 1
 1 (mod p)
Miller-Rabin（概要）
n 1  2 q
s
(n, q  odd, s  Z0 )
2 s 1 q
b , b , . . . , b
n が素数 Fermatの小定理より
q
2q
n1
b  b  1 (mod n)
q

b  1 (mod n) , or
2s q
 1 (mod n) がある
Miller-Rabin（アルゴリズム）
［1/2］
入力：n  N , 2  b ( N )  n , k  N
出力：n は“合成数”
or“判定不能”
{St ep1}
n - 1  2 q ( s, q  N )
s
{St ep2}
i  0, r  b
{St ep3}
q
(mod n)
if (i  0 and r  1) or (i  0 and r  n  1)
nは判定不能 , t erminat e
Miller-Rabin（アルゴリズム）
［2/2］
{St ep4}
i  i  1, r  r
2
{St ep5}
if i  s
go t o St ep3
k回反復
nは合成数
(modn)
Miller-Rabin

拡張リーマン仮説（ERH）の下で決定
性素数判定法

計算量→

ERHの下で
4
O(lg n lg lg n lg lg lg n)
AKS（概要）
a  Z, n  N, n  2, gcd(a, n)  1とする.
n が素数 , またそのときに限り次式が成り立つ.
( X  a )  X  a (mod n)
n
n
この式を以下のように改良する.
( X  a )  X  a (mod X  1, n)
n
n
高々 r  1次の多項式になる.
r
AKS（準備）

n がperfectpower→
b

o r (n) は法 r での n の位数

na
(a, b  N2 )
オイラーの  関数  (n) →
以下の自然数で互いに素な数の個数
n
AKS（アルゴリズム）［1/2］
入力：n  N
出力：n は“
P RIME”or “
COMP OSIT E”
{St ep1}
if n is perfect pow
er
out put COMP OSIT E
{St ep2}
find t hesmallest r sut h t hato r (n)  lg 2 n
{St ep3}
if 1  gcd(a, n)  n for somea  r
out put COMP OSIT E
AKS（アルゴリズム）［2/2］
{St ep4}
if n  r
out put P RIME
{St ep5}
for a  1 t o

 (r ) lg n 
if ( X  a ) n  X n  a (mod X r  1, n)
out put COMP OSIT E
{St ep6}
out put P RIME
AKS（計算量）
St ep1：
p進Newt on法を用いるとO ~ (lg 3 n)
St ep2：
O ~ (lg 2 n lg r )だがr  lg 5 n なのでO ~ (lg 7 n)
St ep3：
Euclidの互除法を用いて
O (r lg n)  O (lg 6 n)
St ep4：
O (lg n)
St ep5：
FFTを使えば多項式の冪は O ~ (r lg 2 n)
O (r  (r )lg n)  O (lg
~
3
~
10.5
n)
 O ~ (lg10.5 n)
実際には r  O (lg 2 n) なので O ~ (lg 7.5 n)
実験

NZMATHをベースにMiller-RabinとAKS
を実装

各桁の素数１０個の計算時間の平均を
算出

Core2Duo2.66GHz, 2GB
結果［1/2］
桁
Miller
（秒）
APR
AKS
6077.856
10
0.003
0.059
20
0.012
0.212
-
30
0.025
0.918
-
40
0.034
1.238
-
50
0.047
6.675
-
100
0.159
26.978
-
300
2.052
-
-
500
8.369
-
-
1000
54.156
-
-
結果（AKS）［2/2］
（秒）
桁
2
3
4
5
6
7
8
9
10
11
Step5
0.09
0.88
6.40
64.11
176.02
474.38
1109.12
2675.04
6017.75
12270.60
Total
0.18
1.37
7.49
67.89
182.52
485.93
1130.96
2711.54
6077.86
12367.45
結論と今後の課題

ERHは通常は正しいとされているので実
用的にはMiller-Rabinが有用

AKSの多項式計算部分の改良

HPの更新
以上で発表を終わります
ご清聴ありがとうございました

Download Report