Shor's Algorithm Proof
Algorithm 1
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
Security algorithms utilizing the difficulty of the discrete logarithm problem
Attack algorithms for the discrete logarithm problem
- Shanks’ algorithm
- Pollard’s rho algorithm
- Conditions under which the discrete logarithm problem is easily solved
Hoffstein. (2008). An Introduction to Mathematical Cryptography: p80. ↩︎