📂整数論

ショアのアルゴリズムの証明

アルゴリズム ¹

単位元が$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)

上記コードを実行した結果は以下の通りであり、連続べき乗法で検算して、正しく動作していることを確認した。

も参照

• 離散対数問題

離散対数問題の難しさを利用したセキュリティアルゴリズム

• ディフィー・ヘルマン鍵交換アルゴリズム
• エルガマル公開鍵暗号体系

離散対数問題に対する攻撃アルゴリズム

• シャンクスのアルゴリズム
• ポラードのロー・アルゴリズム
• 離散対数問題が簡単に解ける条件