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 Answer 1

  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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.