ポラード・ロー アルゴリズムの証明
アルゴリズム
群 の元 がオーダー だとしよう。そうすると、離散対数問題 は、以下のアルゴリズムに従って、多くても ステップで解かれる。
ステップ 1.
と を計算する。
ステップ 2.
シャンクスのアルゴリズムを使って、離散対数問題 の解 を求める。
ステップ 3.
中国剰余定理を使って、 を満たす を求める。
- は、シャンクスのアルゴリズムがかかる時間で、 程度だと考えればいい。
シャンクスのアルゴリズムは、オーダーがわかっているときに使用できる攻撃方法だ。ポラード・ロー アルゴリズムは、 がスムーズであれば、 の素因数分解が容易になり、その結果 を見つけやすくなるという事実を利用する。こうして作られた のオーダーは自明に なので、シャンクスのアルゴリズムを使う制約がなくなる。これはもとの問題を小さな問題に分けて個別に解決した後、中国剰余定理で答えを得るというものだ。
証明
パート 1. 存在性
が の解であるということは、全ての に対して、 を満たす が存在するという意味だ。
- パート 1-1.
と の定義により、 である。整理すると、 となり、対数を取ると、以下を得る。 - パート 1-2.
の定義に従い、 が成立するのは自明であり、拡張ユークリッド定理 により、 が存在する。 - パート 1-3.
パート 1-1で得た、 の両辺に を掛けると、 から まで全てを加えると、 と はインデックス に対して独立なので、 パート 1-2で だから、次を得る。
パート 2. 時間計算量
ごとにステップ 2が繰り返されるので、 かかる。さらに、ステップ 3で中国剰余定理を使うと、 かかるので、
■
コード
以下は、R言語で実装されたポラード・ロー アルゴリズムのコードだ。因数分解コード、オーダーを求めるコード、シャンクスのアルゴリズム、連続冪乗法、中国剰余定理を使うコードが使われた。
prime = read.table("../attachment
/cfile8.uf@25411C3C5968BBE322F0D4.txt"); prime = prime[,1]
factorize<-function(p)
{
q=p
factors<-numeric(0)
i=1; j=1
while(q!=1)
{
if(q%%prime[i]) {i=i+1}
else
{
q<-q/prime[i]
factors[j]<-prime[i]
i=1
j=j+1
}
}
return(factors)
}
order<-function(g,p,h=1) #Calculate a order of g in modulo p
{
qe<-table(factorize(p-1))
qe<-rbind(as.numeric(names(qe)),qe)
divisor<-qe[1,1]^(0:qe[2,1])
if((length(qe)/2)==1) {return(qe[1,1]^qe[2,1])}
for(i in 2:(length(qe)/2)) {divisor=c(divisor%*%t(qe[1,i]^(0:qe[2,i])))}
for(i in divisor) {if((FPM(g,i,p))%%p==1) break;}
return(i)
}
FPM<-function(base,power,mod) #It is equal to (base^power)%%mod
{
i<-0
if (power<0) {
while((base*i)%%mod != 1) {i=i+1}
base<-i
power<-(-power)}
if (power==0) {return(1)}
if (power==1) {return(base%%mod)}
n<-0
while(power>=2^n) {n=n+1}
A<-rep(1,n)
A[1]=base
for(i in 1:(n-1)) {A[i+1]=(A[i]^2)%%mod}
for(i in n:1) {
if(power>=2^(i-1)) {power=power-2^(i-1)}
else {A[i]=1} }
for(i in 2:n) {A[1]=(A[1]*A[i])%%mod}
return(A[1])
}
shanks<-function(g,h,p)
{
N<-order(g,p)
n<-1+floor(sqrt(N))
gn<-FPM(g,-n,p) #gn := g^{-n}
x<-p
List_1<-numeric(n+1)
List_1[1]=1
for(i in 1:n) {List_1[i+1]=(List_1[i]*g)%%p}
List_2<-numeric(n+1)
List_2[1]=h
for(i in 1:n) {List_2[i+1]=(List_2[i]*gn)%%p}
for(i in 0:n+1) {
for(j in 0:n+1) {
if (List_1[i]==List_2[j]) {x[length(x)+1]<-((i-1)+(j-1)*n)}
}
}
return(min(x))
}
CRA<-function(S) #Algorithm of chinese remainder theorem
{
r<-S[,1] # matrix S express below sysyem.
mod<-S[,2] # x = r[1] (mod mod[1])
n<-length(r) # x = r[2] (mod mod[2])
# x = r[3] (mod mod[3])
A<-seq(r[1],to=mod[1]*mod[2],by=mod[1])
for(i in 2:n)
{
B=seq(r[i],to=mod[1]*mod[i],by=mod[i])
r[1]=min(A[A %in% B])
mod[1]=mod[1]*mod[i]
if (i<n) {A=seq(r[1],to=mod[1]*mod[i+1],by=mod[1])}
}
return(r[1])
}
PHA<-function(g,h,p){
N<-order(g,p)
m_<-table(factorize(N))
m_<-rbind(as.numeric(names(m_)),m_)
m_<-c(data.frame(m_)[1,]^data.frame(m_)[2,])
y_<-numeric(0)
for(i in 1:length(m_)){
g_i<-FPM(g,N/m_[i],p)
h_i<-FPM(h,N/m_[i],p)
y_[i]<-shanks(g_i,h_i,p)
}
return(CRA(cbind(y_,m_)))
}
PHA(7,166,433)
FPM(7,47,433)
PHA(10,243278,746497)
FPM(10,223755,746497)
PHA(2,39183497,41022299)
FPM(2,33703314,41022299)
上のコードを実行した結果は次の通りであり、連続冪乗法で検算をし、正しく動作していることを確認した。