5
$\begingroup$

Scott Aaronson likes to motivate the factoring-to-period-finding algorithm used inside Shor's algorithm as follows.

Now, I want you to step back and think about what this means. It means that, if we can find the period of the sequence

$$x \bmod N,\quad x^2 \bmod N, \quad x^3 \bmod N, \quad x^4 \bmod N, \quad \dots $$

then we can learn something about the prime factors of $N$! In particular, we can learn a divisor of $(p-1)(q-1)$. Now, I’ll admit that’s not as good as learning $p$ and $q$ themselves, but grant me that it’s something. Indeed, it’s more than something: it turns out that if we could learn several random divisors of $(p-1)(q-1)$ (for example, by trying different random values of $x$), then with high probability we could put those divisors together to learn $(p-1)(q-1)$ itself. And once we knew $(p-1)(q-1)$, we could then use some more little tricks to recover $p$ and $q$, the prime factors we wanted.

See also Section 19.2 (pp 156) of his Lecture notes where he expounds upon on the same idea. However, in both expositions he ends with a dismissal of the idea:

Unfortunately, this doesn’t quite work with Shor’s algorithm, because the period of $f \colon r \mapsto x^r \bmod N$ might not equal $\phi(N)$, the most we can say is that the period divides $\phi(N)$.

But why doesn't it work?

As Aaronson himself noted, by repeating the algorithm with different values of $x$ wouldn't there be a chance of finding all the factors of $\phi(N)$ (or at least sufficiently many to figure out the remaining factors somehow)?

$\endgroup$
5
$\begingroup$

Aaronson's notes discuss finding $p$ and $q$ if we know $\phi(N)$ by solving the quadratic equation $X^2-(N-\phi(N)+1)X+N=0$ whose roots are $p$ and $q$. This only works if $N$ is the product of two distinct primes (which is the case in most applications of interest) and if we know $\phi(N)$ exactly.

What doesn't often get mentioned about RSA and multiplicative orders is that although the multiplicative order divides $\phi(N)$, it is never equal to it. In fact it always divides the smaller quantity $\lambda(N)$, the Carmichael function of $N$ and sometimes is equal to it. In the case of two distinct prime factors $p$ and $q$, $\lambda(N)=\mathrm{LCM}(p-1,q-1)$. Shor's algorithm has a pretty good chance of delivering $\lambda(N)$ and the LCM of multiple runs should give the exact value. One then knows (in the two prime case) that $\phi(N)=\mathrm{GCD}(p-1,q-1)\lambda(N)$ and might hope to exhaust over possible values of the GCD in order to use the quadratic equation.

People could start to build $p$ and $q$ to make this GCD large (which is not a good use of time) specifically to block the quadratic equation recovery. Instead we prefer to teach the ``random square root of unity'' recovery of the factors which only needs $\lambda(N)$, which works for moduli with more than 2 prime factors and is not effectively blocked by trying to choose $p$ and $q$ in strange ways.

ETA: On further reflection, rather than exhaust over possible values of $\mathrm{GCD}(p-1,q-1)$ on could take the GCD of $N-1$ and $\lambda(N)$ and mess around. This would probably lead to $\phi(N)$ in short order in the two prime case, but the details begin to get more involved than the square root of unity description.

$\endgroup$
2
  • $\begingroup$ So if I understand you correctly, the approach can technically work? (At least for the common RSA-case?). I created a short Sage script creating many random p and q around 1024 bit, and the factor between $\phi(N)$ and $\lambda(N)$ was seldom more than 100 (usually just 2, 4, 6, ...). $\endgroup$
    – panto
    Apr 21 at 12:31
  • $\begingroup$ Yes, it can work in the two prime case, it's just that keeping track of the precise details makes the full argument lengthy. The square root of unity calculation is also essentially the same as congruent squares methods and so is already familiar to people who have studied classical factoring methods. This may be another reason for the preference. $\endgroup$
    – Daniel S
    Apr 21 at 12:44

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.