ポラード・ロー アルゴリズムの証明
アルゴリズム
群 $G$ の元 $g$ がオーダー $N = q_{1}^{r_{1}} q_{2}^{r_{2}} \cdots q_{t}^{r_{t}}$ だとしよう。そうすると、離散対数問題 $g^{x} = h$ は、以下のアルゴリズムに従って、多くても $\displaystyle O \left( \sum_{i=1}^{t} S_{q_{i}^{r_{i}}} + \log N \right)$ ステップで解かれる。
ステップ 1.
$\displaystyle g_{i} : = g^{N / q_{i}^{r_{i}}}$ と $\displaystyle h_{i} := h^{N / q_{i}^{r_{i}}}$ を計算する。
ステップ 2.
シャンクスのアルゴリズムを使って、離散対数問題 $g_{i}^{y} = h_{i}$ の解 $y_{i}$ を求める。
ステップ 3.
中国剰余定理を使って、$\begin{cases} x \equiv y_{1} \pmod{ q_{1}^{r_{1}} } \\ \qquad \vdots \\ x \equiv y_{t} \pmod{ q_{t}^{r_{t}} } \end{cases}$ を満たす $1 \le x \le N$ を求める。
- $S_{q_{i}^{r_{i}}}$ は、シャンクスのアルゴリズムがかかる時間で、$\displaystyle O \left( S_{q_{i}^{r_{i}}} \right) \approx O \left( q_{i}^{r_{i} / 2} \right) $ 程度だと考えればいい。
シャンクスのアルゴリズムは、オーダーがわかっているときに使用できる攻撃方法だ。ポラード・ロー アルゴリズムは、$p$ がスムーズであれば、$(p-1)$ の素因数分解が容易になり、その結果 $\displaystyle g_{i} = g^{N / q_{i}^{r_{i}}}$ を見つけやすくなるという事実を利用する。こうして作られた $g^{i}$ のオーダーは自明に $q_{i}^{r_{i}}$ なので、シャンクスのアルゴリズムを使う制約がなくなる。これはもとの問題を小さな問題に分けて個別に解決した後、中国剰余定理で答えを得るというものだ。
証明
パート 1. 存在性
$x$ が $g^{x} = h$ の解であるということは、全ての $i = 1, \cdots , t$ に対して、$x = y_{i} + q_{i}^{r_{i}} z_{i}$ を満たす $z_{i}$ が存在するという意味だ。
- パート 1-1. $\displaystyle {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N} $
$N$ と $g_{i} , y_{i} , h_{i}$ の定義により、 $$ \begin{align*} \left( g^{x} \right)^{N / q_{i}^{r_{i}} } =& \left( g^{y_{i} + q_{i}^{r_{i}} z_{i}} \right)^{N / q_{i}^{r_{i}} } \\ =& \left( g^{ N / q_{i}^{r_{i}} } \right)^{ y_{i} } \cdot g^{N z_{i} } \\ =& \left( g^{ N / q_{i}^{r_{i}} } \right)^{ y_{i} } \\ =& g_{i}^{ y_{i} } \\ =& h_{i} \\ =& h^{N / q_{i}^{r_{i}} } \end{align*} $$ である。整理すると、 $$ \left( g^{x} \right)^{N / q_{i}^{r_{i}} } = h^{N / q_{i}^{r_{i}} } $$ となり、対数を取ると、以下を得る。 $$ {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N} $$ - パート 1-2. $\displaystyle \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} = 1$
$N$ の定義に従い、$\displaystyle \gcd \left( {{N} \over { q_{1}^{r_{1}} } } , \cdots , {{N} \over { q_{t}^{r_{t}} } } \right) = 1$ が成立するのは自明であり、拡張ユークリッド定理 により、 $$ {{N} \over { q_{1}^{r_{1}} } } c_{1} + \cdots + {{N} \over { q_{t}^{r_{t}} } } c_{t} = 1 $$ $c_{1} , \cdots , c_{t} \in \mathbb{Z}$ が存在する。 - パート 1-3. $x = \log_{g} (h) \pmod{N}$
パート 1-1で得た、 $$ {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N} $$ の両辺に $c_{i}$ を掛けると、 $$ {{N} \over { q_{i}^{r_{i}} } } c_{i} x \equiv {{N} \over { q_{i}^{r_{i}} } } c_{i} \log_{g} ( h ) \pmod{N} $$ $i=1$ から $t$ まで全てを加えると、 $$ \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} x \equiv \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} \log_{g} ( h ) \pmod{N} $$ $x$ と $log_{g} (h)$ はインデックス $i$ に対して独立なので、 $$ x \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} \equiv \log_{g} ( h ) \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} \pmod{N} $$ パート 1-2で $\displaystyle \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} = 1$ だから、次を得る。 $$ x \equiv \log_{g} (h) \pmod{N} $$
パート 2. 時間計算量
$i = 1, \cdots , t$ ごとにステップ 2が繰り返されるので、$\displaystyle O \left( S_{q_{i}^{r_{i}}} \right) $ かかる。さらに、ステップ 3で中国剰余定理を使うと、$O ( \log N )$ かかるので、$\displaystyle O \left( \sum_{i=1}^{t} S_{q_{i}^{r_{i}}} + \log N \right)$
■
コード
以下は、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)
上のコードを実行した結果は次の通りであり、連続冪乗法で検算をし、正しく動作していることを確認した。
