logo

ポラード・ロー アルゴリズムの証明 📂整数論

ポラード・ロー アルゴリズムの証明

アルゴリズム

GG の元 gg がオーダー N=q1r1q2r2qtrtN = q_{1}^{r_{1}} q_{2}^{r_{2}} \cdots q_{t}^{r_{t}} だとしよう。そうすると、離散対数問題 gx=hg^{x} = h は、以下のアルゴリズムに従って、多くても O(i=1tSqiri+logN)\displaystyle O \left( \sum_{i=1}^{t} S_{q_{i}^{r_{i}}} + \log N \right) ステップで解かれる。


ステップ 1.

gi:=gN/qiri\displaystyle g_{i} : = g^{N / q_{i}^{r_{i}}}hi:=hN/qiri\displaystyle h_{i} := h^{N / q_{i}^{r_{i}}} を計算する。


ステップ 2.

シャンクスのアルゴリズムを使って、離散対数問題 giy=hig_{i}^{y} = h_{i} の解 yiy_{i} を求める。


ステップ 3.

中国剰余定理を使って、{xy1(modq1r1)xyt(modqtrt)\begin{cases} x \equiv y_{1} \pmod{ q_{1}^{r_{1}} } \\ \qquad \vdots \\ x \equiv y_{t} \pmod{ q_{t}^{r_{t}} } \end{cases} を満たす 1xN1 \le x \le N を求める。


  • SqiriS_{q_{i}^{r_{i}}} は、シャンクスのアルゴリズムがかかる時間で、O(Sqiri)O(qiri/2)\displaystyle O \left( S_{q_{i}^{r_{i}}} \right) \approx O \left( q_{i}^{r_{i} / 2} \right) 程度だと考えればいい。

シャンクスのアルゴリズムは、オーダーがわかっているときに使用できる攻撃方法だ。ポラード・ロー アルゴリズムは、ppスムーズであれば、(p1)(p-1) の素因数分解が容易になり、その結果 gi=gN/qiri\displaystyle g_{i} = g^{N / q_{i}^{r_{i}}} を見つけやすくなるという事実を利用する。こうして作られた gig^{i} のオーダーは自明に qiriq_{i}^{r_{i}} なので、シャンクスのアルゴリズムを使う制約がなくなる。これはもとの問題を小さな問題に分けて個別に解決した後、中国剰余定理で答えを得るというものだ。

証明

パート 1. 存在性

xxgx=hg^{x} = h の解であるということは、全ての i=1,,ti = 1, \cdots , t に対して、x=yi+qirizix = y_{i} + q_{i}^{r_{i}} z_{i} を満たす ziz_{i} が存在するという意味だ。

  • パート 1-1. NqirixNqirilogg(h)(modN)\displaystyle {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N}
    NNgi,yi,hig_{i} , y_{i} , h_{i} の定義により、 (gx)N/qiri=(gyi+qirizi)N/qiri=(gN/qiri)yigNzi=(gN/qiri)yi=giyi=hi=hN/qiri \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*} である。整理すると、 (gx)N/qiri=hN/qiri \left( g^{x} \right)^{N / q_{i}^{r_{i}} } = h^{N / q_{i}^{r_{i}} } となり、対数を取ると、以下を得る。 NqirixNqirilogg(h)(modN) {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N}
  • パート 1-2. i=1tNqirici=1\displaystyle \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} = 1
    NN の定義に従い、gcd(Nq1r1,,Nqtrt)=1\displaystyle \gcd \left( {{N} \over { q_{1}^{r_{1}} } } , \cdots , {{N} \over { q_{t}^{r_{t}} } } \right) = 1 が成立するのは自明であり、拡張ユークリッド定理 により、 Nq1r1c1++Nqtrtct=1 {{N} \over { q_{1}^{r_{1}} } } c_{1} + \cdots + {{N} \over { q_{t}^{r_{t}} } } c_{t} = 1 c1,,ctZc_{1} , \cdots , c_{t} \in \mathbb{Z} が存在する。
  • パート 1-3. x=logg(h)(modN)x = \log_{g} (h) \pmod{N}
    パート 1-1で得た、 NqirixNqirilogg(h)(modN) {{N} \over { q_{i}^{r_{i}} } } x \equiv {{N} \over { q_{i}^{r_{i}} } } \log_{g} ( h ) \pmod{N} の両辺に cic_{i} を掛けると、 NqiricixNqiricilogg(h)(modN) {{N} \over { q_{i}^{r_{i}} } } c_{i} x \equiv {{N} \over { q_{i}^{r_{i}} } } c_{i} \log_{g} ( h ) \pmod{N} i=1i=1 から tt まで全てを加えると、 i=1tNqiricixi=1tNqiricilogg(h)(modN) \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} xxlogg(h)log_{g} (h) はインデックス ii に対して独立なので、 xi=1tNqiricilogg(h)i=1tNqirici(modN) 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で i=1tNqirici=1\displaystyle \sum_{i=1}^{t} {{N} \over { q_{i}^{r_{i}} } } c_{i} = 1 だから、次を得る。 xlogg(h)(modN) x \equiv \log_{g} (h) \pmod{N}

パート 2. 時間計算量

i=1,,ti = 1, \cdots , t ごとにステップ 2が繰り返されるので、O(Sqiri)\displaystyle O \left( S_{q_{i}^{r_{i}}} \right) かかる。さらに、ステップ 3で中国剰余定理を使うと、O(logN)O ( \log N ) かかるので、O(i=1tSqiri+logN)\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)

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

20190306_094545.png

併せて読みたい

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

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