5
$\begingroup$

I know that Shor's algorithm can factor semi-primes ($N = p \times q \space, \{p, \space q \in \Bbb{P} \space \vert \space p, \space q \gt 0 \} $).

Assuming that all prime numbers are so large that it's infeasible to compute with any known classical algorithm, can Shor's algorithm also factor multi-primes, meaning where $N$ has more than two prime-factors?

$\endgroup$
  • 1
    $\begingroup$ I wrote an answer that explained how but I deleted it because I began to doubt that my explanation was correct. However yes, Shor's can factor multi-prime RSA. In fact, you'd need a modulus composed of about $2^{31}$ prime factors of 4096 bits each to resist any possible physical realization of Shor's algorithm (see DJB's pqRSA). $\endgroup$ – forest Apr 23 at 10:20
  • $\begingroup$ Also, see crypto.stackexchange.com/q/3932/54184. $\endgroup$ – forest Apr 23 at 10:22
3
$\begingroup$

Yes, it can. Quoting the document of DJB: "Post-quantum RSA" by Daniel J. Bernstein, Nadia Heninger, Paul Lou and Luke Valenta, which forest has linked to:

If $n$ is a product of more primes, say $k \ge 3$ primes, then the same speedup becomes even more effective, using $k$ exponentiations with ($1/k$)-size exponents and ($1/k$)-size moduli. Prime generation also becomes much easier since the primes are smaller. Of course, if primes are too small then the attacker can find them using the ring algorithms discussed in the previous section|specifically EECM before quantum computers, and GEECM after quantum computers.

As we don't know how to factor multi-prime RSA, with e.g. 3 exponents of 1024 bits using classical computing, we can surmise that Shor can factor multi-primes that would be out of reach otherwise.

The article then goes on to exploring how many primes and how large a modulus size would be sufficient to ward off attacks by a full quantum computer, and comes out at 1-terabyte key, 4096-bit primes and $2^{31}$ multiplications to create the modulus.

Probably we should look at other alternatives before turning to RSA for Post Quantum Cryptography, another one of the conclusions of the paper.

$\endgroup$
  • $\begingroup$ Is there an estimation of how long an exchange of a secret between two parties would take with a key of size 1 terabyte? $\endgroup$ – AleksanderRas Apr 23 at 14:21
  • 2
    $\begingroup$ Yes, see chapter 4 of the paper: "Concrete parameters and initial implementation" - although the full 1 TB has N/A (actually, it's not even present in the table as previous sizes already have N/A), so you would have to extrapolate (to "not funny anymore"). $\endgroup$ – Maarten - reinstate Monica Apr 23 at 14:32
  • $\begingroup$ @MaartenBodewes It might be worth noting that those benchmarks were done on a supercomputing cluster, not an average home computer. It would take far longer to even multiply $2^{31}$ integers on a PC. $\endgroup$ – forest Apr 23 at 19:05
3
$\begingroup$
  • Shor's algorithm works by using quantum magic to compute a period of $f\colon x \mapsto a^x \bmod n$ for random $a$; if it gives $2t$ so that $a^{2t} \equiv 1 \pmod n$, and if $a^t \not\equiv -1 \pmod n$, then $\gcd(a^t \pm 1, n)$ is a nontrivial factor of $n$. (Otherwise, repeat with another $a$.) If $n = p q r$ and $\gcd(a^t \pm 1, n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

    The cost is dominated by $(\lg n)^{2 + o(1)}$ qubit operations to compute $f$—that is, it is quadratic in the size of the modulus $n$.

Post-quantum RSA chooses $n$ so large that this quadratic gap is infeasible for an attacker (of course, merely using pqRSA is also only barely feasible as a joke for well-funded users), but that's not the only avenue for attack:

  • If a prime factor is bounded by $y$, then $\gcd(f(n, u), n)$ may be a nontrivial factor of $n$, where $f(n, u)$ is a product of many distinct primes below $y$ modulo $n$, randomized by $u$e.g., trial division, Pollard's $\rho$, ECM, etc. If $n = p q r$ and you find $u$ so that $\gcd(f(n, u), n) = p$, then you can lather, rinse, and repeat for $n' = n/p = q r$.

    Grover's algorithm finds a preimage of 0 under $u \mapsto [\gcd(n, f(n, u)) = 1]$ in the time for about $\sqrt{y}$ quantum evaluations of $f$. For the best $f$, ECM, where $u$ is a random curve choice, the combined cost of Grover-ECM is $L^{1 + o(1)}$ where $L = e^{\sqrt{\log y \log \log y}}$—that is, it is superpolynomial but subexponential in the size of the factors $p$, $q$, and $r$.

Consequently, post-quantum RSA chooses $p$, $q$, $r$, and millions of other factors, to be 4096 bits apiece so that this superpolynomial/subexponential gap is infeasible for an attacker while the user can still compute arithmetic modulo $p$, $q$, $r$, and the other factors individually at reasonable cost.

$\endgroup$
  • $\begingroup$ Actually, in Shor's algorithm, $a$ is not random; instead, it's the value that the attacker picks. $\endgroup$ – poncho Apr 23 at 16:57
  • $\begingroup$ @poncho What happens if the attacker picks an element of small order? The standard approach, as far as I know, is to choose $a$ at random (maybe from a distribution that favors small values) and confirm it neither shares factors with $n$ nor has small order first, classically; and then use it in a QFT circuit. Am I missing something? $\endgroup$ – Squeamish Ossifrage Apr 23 at 17:13
  • $\begingroup$ No, you're not (except that there really isn't any 'standard approach', as no one can actually do it yet); if $a$ is selected at random, the probability that it has tiny order is actually neglectable (and a nontiny order of an element can be used to factor, even if $t$ is odd or if $a^{t/2}$ happens to be -1). $\endgroup$ – poncho Apr 23 at 17:36
  • $\begingroup$ Would the downvoter care to explain what you disagree with here? $\endgroup$ – Squeamish Ossifrage Apr 24 at 0:09
  • $\begingroup$ @SqueamishOssifrage Someone simultaneously upvoted my answer and downvoted both existing answers. I take that to mean that they are not voting based on the quality of the answers (after all, mine is not nearly as good as yours or Maarten's), but on who answered them. I have no idea why, but I doubt they'll comment. $\endgroup$ – forest Apr 24 at 6:39
3
$\begingroup$

Shor's algorithm finds the prime factors of any integer, regardless of the number of primes. This is explained in the Wikipedia article, which describes how the algorithm takes an odd integer and finds another integer which divides it. If the composite number is not a semiprime, then you just run Shor's algorithm on the result again to get another integer which divides it. Repeat until only primes remain.

$\endgroup$

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.