PRIMES決定性アルゴリズム従来の代表的方法

PRIMES決定性アルゴリズム
従来の代表的方法
伴地慶介
a.試し割り算
● nP
 d 


1, n
p  P
n
s.t d | n
s.t p | n
を利用.
簡単かつ確実なアルゴリズムだが、計算量が指数時間O
 n で
あり小さな n でないと使い物にならない.
・割り算が最大  ( n  1) / 2  回. n 以下の整数の除算計算量はO(lg 2 n)BCで,
注意1.2.3(p16)の既知最速算法を用いればO(lg n lg lg n lg lg lg n)  O(lg n)BC.
よって試し割り算による PRIMESの入力 n に対する BCは,
O( n lg n lg lg n lg lg lg n)  O( n lg 2 n)  O( n ).
b.既約剰余類群の利用
● 定理 2. 2. 4 ModPPw と (2.11) による同値性
≪参考≫
n  P   / n  は位数 n  1 の巡回群 … (i)
・定理2. 2. 4( ModPPw)

p  P, e 
これを利用する.しかし制限があり , 条件を現実に計算可能な形に
言い直さなければならない.

 g
例えば, n  P  (n  1) !  1 mod n 
しかしこれは階上計算が指数時間 O(n)BC になる.
ここで n  1 の素因数全体 S : { p  P | p | n  1}
 {g1 g  /( p /21)p
● nP
s.t b n1  1 mod n  , b( n1)/ p  1 mod n   p  S  … (ⅱ)
※ (4.3) より b n1  1 mod n  の計算量は O(lg 2 n lg lg n lg lg lg n).
この計算を各 p に対し計算するので, 一つの b に対する計算量は
O( # S lg 2 n lg lg n lg lg lg n)    # S lg 2 n  である.

/p
e 1
  n  :
#

/ n

 1
  n   n 1  
p
pP 
p| n

( p  2またはe 2)
/2
( p  2, e3)
e2
・ p43( 2. 11)
がわかるときに注目し , (ⅱ) を次に言い替える .
 b 
s.t
e 
既約剰余類利用の問題点
● 問題①: どうやって b を探すか
 各種PsPTにより , 既に n  P の可能性が高い.
 n  P なら b は法 n の原始根PRP.
 算法 2.2.3(PRP)の手順で早く見つかる .
● 問題② : n  1の素因数の集合Sの計算
 整数分解問題は指数時間….

(n  1 の部分的 PF T : { p  P | p | m} (m  , m | n  1, m  n )

ができているときに, (4.8) を一般化した n-1テストというものが考え出されている . )
よって素因子がわかっている
次の特殊なケースを考えることにする .
・二の二べき乗+1（フェルマ数）の素数判定
●フェルマ数 Fm : 2 2  1  n ( m 
m
≪参考≫
)
・定理 2.2.2
もし nP

( n 1)(31)/ 4  n 
3
n
     1

     1 であり ,
n
 
3 3
また n  P  3 
 (n)
3
n  , a   / n   a ( n )  1 mod n 
n 1
3
/ n  に対し ,

3
22
m
・ (ⅱ)
3
n  P     3( n 1)/ 2  mod n 
n
 1  32
1
PR で (ⅱ) を満たす.

b
s.t
b n 1  1 mod n  , b ( n 1) / p  1 mod n 
 mod n 
つまり b  3 は位数 2 べきの巡回群
任意の奇数 m, n  , gcd( m, n)  1に対し ,
 m  n 
( m 1)( n 1)/ 4
     (1)
 n  m 
 1 mod n  .
2m
・定理 2.3.2(XQRL)

/ n の

 pS
算法4.3.1(Pepin,T.,1877)
● 入力 : m  .
● 出力「: Fm  P 」または「 Fm  P 」
● 手順 :もし 3( Fm 1)/2  1 mod Fm なら「 Fm  P 」
と判定して終了. さもなくば「 Fm  P 」と判定して終了.
n  Fm : 2  1 より
2m
S : { p  P | p | n  1}  {2}.
3( Fm 1)/2  1 mod Fm  
m
22 1
3
( n 1)/2
3
 1 mod n  , 3
よって n  P  b 
を満たす.
22
m
 3n 1  1 mod n 
s.t b n 1  1 mod n  , b ( n 1)/ p  1 mod n   p  S 
from amod import Amod as Amod
def Fm(m):
if m==0:
return '3 is Prime'
n=pow(2,pow(2,m))+1
if Amod(pow(3,(n-1)//2,n),n)==-1:
return '%d is Prime' %(n)
else:
return '%d is not Prime' %(n)
c.有限体の乗法群の利用
・ n  P のとき
Fn 
/ nに対し ,
Fn2  {a  bx | a, b  Fn , x は Fn 上既約二次多項式の解}
が考えられ,
 
乗法群 Fn2

は位数 n 2  1  (n  1)(n  1) の巡回群なので,
位数が n  1 や n  1 の元を持つ.
・この事実と線形回帰数列を組み合わせて
n  1テスト , n2  1テスト , さらに理論的には
有限体テストという広いアルゴリズムも考えられる .
•二の素べき乗-1(メルセンヌ数)の素数判定
● メルセンヌ数 M p : 2 p  1  n ( p  P )
q を M p の素因子とする .
数列 u1 : 4, ui 1 : ui 2  2 (i  )
y( q 1)/2 y( q 1)/2  0  mod q  .
を考える .

・ 2 3


n

: xn  3 yn , 2  3
 


n
w は 2 w  q  1.
: xn  3 yn
n
n
1
xn 
2 3  2 3
2
n
n
1
yn 
2 3  2 3
2 3
xn  m  xn xm  3 yn ym , xn  m  xn xm  3 yn ym

 

yn  m  xn ym  xm ym , yn  m   xn ym  xm ym
これより x2 n  2 xn  1.
2
帰納法により , ui  2 x2i1 .
x
2 p 2
 0  mod M p 
yw  0  mod q  となる最小の
yw  0  mod q   ykw  0  mod q  .
yn  0  mod q   yn  kw  0  mod q  .
よって n は w の倍数.
yn  0  mod q   w | n
M p | x2 p2 , q | M p  q | x2 p2 .
y2 p1  2 x2 p2 y2 p2  0  mod q 
w  2 p 1.
2  2 p 1  q  1  M p  1  2 p
 q  M p  M p  P.
算法4.3.2(Lucas-Lehmer)
● 入力 : p  P 2
● 出力 : 判定「 M p  P 」または判定「 M p  P 」
● 手順: もし u p 1  0  mod M p  なら「 M p  P 」
と判定して終了. さもなくば「 M p  P 」と判定して終了.
※この数の重要性と応用については, 最終の §7. 4参照.
そこでは p, M p  P となることを利用した, 高性能な
擬似乱数生成法が紹介されている.
def Mp(p):
def u_t(t):
u=4
for i in range(1,t):
u=pow(u,2)-2
return u
Mp=pow(2,p)-1
if u_t(p-1)%Mp==0:
return '%d is Prime' %(Mp)
else:
return '%d is not Prime' %(Mp)
d.指標和の利用
・計算量が極めて多項式時間に近い（ ln O(ln ln ln n ) n） ,
指数時間の PRIMES決定性アルゴリズムで, その
アルゴリズムは複雑になり ,実装の際に予見しない
バグを含む可能性が高い.
・絶対擬素数テスト
from gcd import gcd as gcd
import random
def APsPT(n,k):
kx=k
while k!=0:
b=random.choice(range(2,n-1))
if gcd(b,n)>1:
return '%d is not Prime' %(n)
elif pow(b,n-1,n)!=1:
return '%d is not Prime' %(n)
k=k-1
return(%d is APsP or %d is Prime( probability :1  2(  k )))%(n, n, kx )
・平方剰余基準テスト
from gcd import gcd as gcd
from amod import Amod as Amod
from xqrs import XQRS as XQRS
import random
def QRCT(n,k):
kx=k
while k!=0:
b=random.choice(range(2,n-1))
if gcd(b,n)>1:
return '%d is not Prime' %(n)
elif not Amod(pow(b,(n-1)//2),n)==XQRS(b,n):
return '%d is not Prime' %(n)
k=k-1
return%d is Prime( probability :1  2(  %d ))%(n, kx )
・強擬素数テスト
import random
from gcd import gcd as gcd
def SPsPT(n,k):
e=0
m=n-1
while 1:
if not m & 1:
e+=1
m=m//2
else:
break
kx=k
while k!=0:
else:
b=random.choice(range(2,n-1))
if gcd(b,n)>1:
return '%d is not Prime' %(n)
return '%d is not Prime' %(n)
k  k 1
return%d is Prime( probability :1  4(  %d ))%(n, kx)

Download Report