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
  • $\begingroup$ How can you be sure that r2 has an inverse mod 28? That's only true if r2 and 28 are coprime. $\endgroup$
    – Omeglac
    Nov 14, 2023 at 10:24
  • $\begingroup$ You're right, but notice that if $r_1$ has an inverse mod 28 and so does $x$, then necessarily $r_2$ does as well. For real-world cryptography we also work only in prime-order subgroups, so the issue doesn't come up. $\endgroup$
    – Sam Jaques
    Nov 15, 2023 at 19:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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