ショアのアルゴリズムの証明
アルゴリズム 1
単位元が$e$であるグループ$G$の元$g$が、オーダー$N$とする。それならば、離散対数問題$g^{x} = h$は次のアルゴリズムに従って、多くても$O \left( \sqrt{N} \log N \right)$ステップ以内に解ける。
ステップ 1.
$n: = 1 + \lfloor \sqrt{N} \rfloor $
ステップ 2.
二つのリスト$A := \left\{ e , g , g^{2} , \cdots , g^{n} \right\}$と$B := \left\{ h , hg^{-n} , hg^{-2n} , \cdots , hg^{-n^2} \right\}$を作る。
ステップ 3.
$g^{i} = h g^{-jn} \in A \cap B$を見つける。
ステップ 4.
$x = i + jn$は$g^{x} = h$の解である。
説明
基本的にグループ$G$の元$g$がオーダー$N$である場合、離散対数問題$g^{x} = h$は多くても$O (N) $ステップ以内に解ける。$g$がオーダー$N$であるとは、少なくとも$g^{N} = e$が成り立つことを意味する。したがって、$ 0, 1, \cdots , N-1$の中には$g^{x} = h$を満たす$x$が存在することが簡単に確認できる。
シャンクスのアルゴリズムは、この計算量を$O \left( \sqrt{N} \log N \right)$まで落としてくれる。暗号に適用される離散対数問題であれば、$N$はかなり大きな数であろうから、半分以上計算を減らすことができるので、大きな意味がある。
ベビーステップとジャイアントステップは、$g$を掛けて作られるリスト$A$と、$g^{-n}$を掛けて作られるリスト$B$から出た言葉だ。
証明
パート 1. 存在性
$\left( A \cap B \right) \ne \emptyset$であることを示さなければならない。
$x$を$n$で割った商を$q$、余りを$r$とすると、$x = nq + r$のように表せる。
すると$\sqrt{N} < n$なので $$ q = {{ x - r } \over { n }} < {{ N } \over { n }} < n $$ そして $$ \begin{align*} & g^{x} = h \\ \implies & g^{ nq + r } = h \\ \implies & g^{ r } = h g^{ - nq } \end{align*} $$ である。$r < n$なので$g^{r} \in A$であり、$q < n$なので$h g^{ - nq } \in B$である。
パート 2. 時間複雑性
$A \cap B$を見つけるためにはリストをソートする必要があり、最適な比較ソートアルゴリズムを使用すると$O ( n \log n )$回の計算が必要である。
$n \approx \sqrt{N}$であるため、 $$ \begin{align*} O \left( n \log n \right) =& O \left( \sqrt{N} \log \sqrt{N} \right) \\ =& O \left( {{1} \over {2}} \sqrt{N} \log N \right) \\ =& O \left( \sqrt{N} \log N \right) \end{align*} $$
■
コード
以下は、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)
}
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))
}
shanks(11,21,71)
FPM(11,37,71)
shanks(156,116,593)
FPM(156,59,593)
shanks(650,2213,3571)
FPM(650,319,3571)
上記コードを実行した結果は以下の通りであり、連続べき乗法で検算して、正しく動作していることを確認した。
も参照
離散対数問題の難しさを利用したセキュリティアルゴリズム
離散対数問題に対する攻撃アルゴリズム
Hoffstein. (2008). 「数学的暗号化への導入」: p80。 ↩︎