Miller-Rabinアルゴリズム
3727 ワード
Miller−Rabinアルゴリズムは、1つの数nが素数であるか否かを検出するために使用される.その時間的複雑さの境界はO(klog 2(n))であり,ここでkは検出されたホイール数である.kを大きくするとMiller‐Rabinアルゴリズムの精度が向上する.
1つの数が素数であるか否かを検出するには,単純なアルゴリズムが2つあり,1つ目は2~√nの間の数に対してnの因子であるか否かを調べ,その時間複雑度はO(√n)である.2つ目は打表法であり,オーラふるいによりO(N)の時空複雑度内に1~N間のすべての素数を取得して記憶することができる.いずれの場合も、超大きなnに対しては、恐ろしい時間を費やして判断しなければならない.例えば、nを1 e 18とすると、両アルゴリズムは現代のコンピュータでは終わらない(後者は直接メモリ不足になる).
数論におけるFerma小定理では,任意の素数pに対しても,モジュールpの残りのクラスリング{1,2,...,p−1}の任意の数xに対してもx^p=x(mod p)を満たすことが指摘されている.そのため、この小さなテクニックで大量の合数を排除することができます.例えば素数5では2^5(mod 5)=2,6では2^6(mod 6)=4であることが分かった.
しかし,フェルマ小定理ではpは素数がx^p=x(mod p)の十分な条件であり,必要条件ではなく,例えば4^6=4(mod 6)であるが,6は素数とは言えない.従って,x^p=x(mod p)を満たさない数xが存在する限り,pは素数ではないという結果の信頼性を向上させるために,モジュールpの残りのクラスリングからより多くの数を選択して試験する必要がある.しかし、任意の1に対して、..p−1のxはいずれもx^p=x(mod p)を満たし,これらの合数をCarmichael数と呼び,一例として561である.このような数の存在により,一つの数が素数であるか合数であるかをフェルマの小さな定理で完全に正確に断定することができなかった.
Miller‐Rabinアルゴリズムの登場は,Fermaの小さな定理を満たす相当クラスの合数が素数テストに合格できないことをもたらした.Miller−Rabinアルゴリズムは、x^2=1(mod p)の場合、pが素数であれば(x−1)(x+1)=0(mod p)であり、pが2でない限り(x−1)と(x+1)はモードpの性質で等しくなく、pが2であるかどうかにかかわらず(x−1)=0(mod p)または(x+1)=0(mod p)(モードpの残りのクラスリングが整環であるため)すなわちx=1またはx=1が保証されるという事実に基づいている.したがって、pがxを数えるフェルマテストに合格した後、x^p=p(mod p)と書くか、x^(p-1)=1(mod p)と書くか、p-1が偶数であれば、x^((p-1)/2)が1または(p-1)に等しいかどうかでテストを続けることができます.テストに合格すれば、x^2 k=1(mod p)を満たすか否かを判断し続け、判断を継続することもできる.一環判断が通らない限り、pは合数であることが保証される.
先ほどお話ししたCarmichael数561を見てMiller-Rabinテストを行います.
2^560=1(mod 561)満足
2^280=1(mod 561)満足
2^140=67(mod 561)は、以下に示す個人的なMRアルゴリズムのテンプレートを満たさない.
mr 0におけるべき乗演算は高速べき乗乗算の技術を用いて実現できるため、1回のべき乗演算の時間複雑度はO(log 2 n)であり、whileサイクルはlog 2(p)回まで最大であり、1回のサイクルごとにべき乗演算が1回実行されるため、総時間複雑度はO((log 2 p)^2)である.
1つの数が素数であるか否かを検出するには,単純なアルゴリズムが2つあり,1つ目は2~√nの間の数に対してnの因子であるか否かを調べ,その時間複雑度はO(√n)である.2つ目は打表法であり,オーラふるいによりO(N)の時空複雑度内に1~N間のすべての素数を取得して記憶することができる.いずれの場合も、超大きなnに対しては、恐ろしい時間を費やして判断しなければならない.例えば、nを1 e 18とすると、両アルゴリズムは現代のコンピュータでは終わらない(後者は直接メモリ不足になる).
数論におけるFerma小定理では,任意の素数pに対しても,モジュールpの残りのクラスリング{1,2,...,p−1}の任意の数xに対してもx^p=x(mod p)を満たすことが指摘されている.そのため、この小さなテクニックで大量の合数を排除することができます.例えば素数5では2^5(mod 5)=2,6では2^6(mod 6)=4であることが分かった.
しかし,フェルマ小定理ではpは素数がx^p=x(mod p)の十分な条件であり,必要条件ではなく,例えば4^6=4(mod 6)であるが,6は素数とは言えない.従って,x^p=x(mod p)を満たさない数xが存在する限り,pは素数ではないという結果の信頼性を向上させるために,モジュールpの残りのクラスリングからより多くの数を選択して試験する必要がある.しかし、任意の1に対して、..p−1のxはいずれもx^p=x(mod p)を満たし,これらの合数をCarmichael数と呼び,一例として561である.このような数の存在により,一つの数が素数であるか合数であるかをフェルマの小さな定理で完全に正確に断定することができなかった.
Miller‐Rabinアルゴリズムの登場は,Fermaの小さな定理を満たす相当クラスの合数が素数テストに合格できないことをもたらした.Miller−Rabinアルゴリズムは、x^2=1(mod p)の場合、pが素数であれば(x−1)(x+1)=0(mod p)であり、pが2でない限り(x−1)と(x+1)はモードpの性質で等しくなく、pが2であるかどうかにかかわらず(x−1)=0(mod p)または(x+1)=0(mod p)(モードpの残りのクラスリングが整環であるため)すなわちx=1またはx=1が保証されるという事実に基づいている.したがって、pがxを数えるフェルマテストに合格した後、x^p=p(mod p)と書くか、x^(p-1)=1(mod p)と書くか、p-1が偶数であれば、x^((p-1)/2)が1または(p-1)に等しいかどうかでテストを続けることができます.テストに合格すれば、x^2 k=1(mod p)を満たすか否かを判断し続け、判断を継続することもできる.一環判断が通らない限り、pは合数であることが保証される.
先ほどお話ししたCarmichael数561を見てMiller-Rabinテストを行います.
2^560=1(mod 561)満足
2^280=1(mod 561)満足
2^140=67(mod 561)は、以下に示す個人的なMRアルゴリズムのテンプレートを満たさない.
mr(p)
if(p == 2 || p == 3 || p == 5 || p == 7)
return true
return mr0(2, p) && mr0(3, p) && mr0(5, p) && mr0(7, p)
mr0(x, p)
if (x^(p-1)) % p != 1
return false
k = p - 1
while k % 2 == 0
k = k / 2
t = x^k
if(t != 1 && t != p - 1)
return false
if(t == p - 1)
return true
return truemr 0におけるべき乗演算は高速べき乗乗算の技術を用いて実現できるため、1回のべき乗演算の時間複雑度はO(log 2 n)であり、whileサイクルはlog 2(p)回まで最大であり、1回のサイクルごとにべき乗演算が1回実行されるため、総時間複雑度はO((log 2 p)^2)である.