# How to build an example of Shor's algorithm for the discrete log?

I have been trying to build myself an example of Shor's computations for the discrete log. I started out with this objective and I realized I should understand the factorization first, which I did and did. Having a clue about the factorization, perhaps now I can tackle the discrete log, but it's still not that easy.

Problem. Find $$a$$ such that $$2^a = 7 \bmod 29$$. (We know $$2$$ is a generator of $$Z_{29}$$.)

Peter Shor tells us to find $$q$$, a power of $$2$$ that is close to $$29$$, that is, $$29 < q < 2\times29$$. So $$q = 32 = 2^5$$ suffices. Next he tells us to put two register |$$a$$> and |$$b$$> in uniform superposition $$\bmod 28$$. (Why $$\kern-0.4em\bmod 28$$? Why not $$\kern-0.4em\bmod 29$$?) Then in a third register compute |$$2^a 7^{-b} \bmod 29$$>.

This will produce a periodic sequence in superposition. Applying the QFT to this register, we should be able to extract this period. When I look at the sequence for this concrete case (which is $$2^a 7^{-b} \bmod 29$$), I find $$[1, 25, 16, 23, 24, 20, 7, 1, 25, 16, 23, 24, 20, 7, 1, ...]$$ So, I can see the period is $$7$$.

What is the calculation that I must do now to extract the solution $$a = 12$$?

1. Fermat's little theorem says that for a prime $$p$$, $$a^{p-1}\equiv 1\mod p$$ for all $$a$$ co-prime to $$p$$. This means the order of the group of powers of $$a$$ will divide $$p-1$$, rather than $$p$$, hence why the algorithm uses $$28$$.

2. The "input" is two-dimensional here; it should be all pairs $$(a,b)$$ for $$0\leq a\leq 27$$ and $$0\leq b\leq 27$$. The period you're looking for is a pair of integers $$(r_1,r_2)$$ such that $$2^a7^{-b}\equiv 2^{a+r_1}7^{-b-r_2}\mod p$$.

Let $$x$$ be the discrete log, i.e., $$7\equiv 2^x\mod p$$. Then we can re-write this as

$$2^a2^{-bx}\equiv 2^{a+r_1}2^{-x(b+r_2)}\mod p$$ Since we know that $$2^{28}\equiv 1\mod p$$, we can treat the exponents as integers modulo $$28$$, i.e.,

$$a-bx \equiv a+r_1-x(b+r_2)\mod 28$$ We can cancel out terms with $$a$$ and $$b$$:

\begin{align}0\equiv &r_1-xr_2\mod 28\\ -r_1r_2^{-1}\equiv &x\mod 28\end{align}

So the discrete log is $$-r_1r_2^{-1}\mod 28$$.

This means what you really want to do is take a two-dimensional array of results for different values of $$a$$ and $$b$$, and find a period in that.

It looks like what you've actually found is that the order of $$7$$ is $$7$$, i.e., $$7^7\equiv 1\mod p$$. I don't think this has any impact on Shor's algorithm, but I'm not sure. Usually you would only apply Shor's algorithm to a prime-order group, since you can use the Pohlig-Hellman algorithm to reduce composite-order discrete logs to smaller prime-order discrete logs.

• Your answer looks very interesting. I might take some time digesting that. More to follow! Dec 9, 2020 at 0:18