📂Number Theory

Shor's Algorithm Proof

Algorithm ¹

Let us say the element $g$ of the group $G$, with an identity element of $e$, has an order of $N$. Then, the discrete logarithm problem $g^{x} = h$ can be solved in at most $O \left( \sqrt{N} \log N \right)$ steps according to the following algorithm.

---

Step 1.

$n: = 1 + \lfloor \sqrt{N} \rfloor$

---

Step 2.

Create two lists $A := \left\{ e , g , g^{2} , \cdots , g^{n} \right\}$ and $B := \left\{ h , hg^{-n} , hg^{-2n} , \cdots , hg^{-n^2} \right\}$.

---

Step 3.

Find $g^{i} = h g^{-jn} \in A \cap B$.

---

Step 4.

$x = i + jn$ is the solution to $g^{x} = h$.

Explanation

Fundamentally, if the element $g$ of the group $G$ has an order of $N$, then the discrete logarithm problem $g^{x} = h$ can be solved in at most $O (N)$ steps. That $g$ has an order of $N$ means that at least $g^{N} = e$ holds true. Hence, it is easy to verify that among $0, 1, \cdots , N-1$, there exists a $x$ that satisfies $g^{x} = h$.

The Shanks’ algorithm reduces this computational load down to $O \left( \sqrt{N} \log N \right)$. If it’s a discrete logarithm problem applied to cryptography, since $N$ would be a significantly large number, reducing the computation by more than half has a significant meaning.

The terms baby steps and giant steps come from the lists of $A$ made by multiplying $g$ and the lists of $B$ made by multiplying $g^{-n}$.

Proof

Part 1. Existence

We must show that $\left( A \cap B \right) \ne \emptyset$ holds true.

When $x$ is divided by $n$, let the quotient be $q$, and the remainder be $r$. Then, it can be represented as $x = nq + r$.

Then, since $\sqrt{N} < n$, $$q = {{ x - r } \over { n }} < {{ N } \over { n }} < n$$ and $$\begin{align*} & g^{x} = h \\ \implies & g^{ nq + r } = h \\ \implies & g^{ r } = h g^{ - nq } \end{align*}$$ it follows. Because of $r < n$, $g^{r} \in A$, and because of $q < n$, $h g^{ - nq } \in B$.

---

Part 2. Time Complexity

To find $A \cap B$, the list must be sorted, and using the most appropriate comparison sorting algorithm, $O ( n \log n )$ calculations are necessary.

Since $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*}$$

■

Code

Below is the implementation of Shank’s algorithm in R language. Prime factorization code and Order finding code were used.

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)

The result of running the above code is as follows, and it was verified to work correctly through checking with exponentiation by squaring.

See also

• Discrete logarithm problem

Security algorithms utilizing the difficulty of the discrete logarithm problem

• Diffie-Hellman key exchange algorithm
• ElGamal public key cryptosystem

Attack algorithms for the discrete logarithm problem

• Shanks’ algorithm
• Pollard’s rho algorithm
• Conditions under which the discrete logarithm problem is easily solved