# Why doesn't this factoring to order-finding reduction work?

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)?

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.
• 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, ...). Apr 21 at 12:31