0
$\begingroup$

Would it be technically possible to use hundreds of computer processors together to work on an algorithm like the Shor's algorithm and break RSA?

I've been reading about the crazy amount of qubits required to break RSA but what if hundreds of 64 bit processors work together towards the same goal? I would assume, if possible, it would be a very complex system and would require other algorithms to split the work evenly and some powerful centralized software for so many parallel processing's taking place.

$\endgroup$
2
  • $\begingroup$ The question is not stating clearly if the "hundreds of computer processors" that it envisions are classical (as in the reading made in this answer) or quantum. That's the crux of the issue: classical computers can't run an "algorithm like the Shor's algorithm". $\endgroup$
    – fgrieu
    Commented Mar 5, 2023 at 9:30
  • 1
    $\begingroup$ @fgrieu: actually, a classical computer (or a group of them) can simulate any Quantum algorithm, including Shor's. Of course, the problem with that is, in this case, the simulation will take exponential time... $\endgroup$
    – poncho
    Commented Mar 5, 2023 at 18:57

1 Answer 1

3
$\begingroup$

This is routinely done for the largest factorization records of RSA-type moduli (two primes of roughly the same size), although using a classical algorithm called the Number Field Sieve.

Out of its four main steps, the first two (polynomial selection and sieving) are very amenable to distributing among many different computers, even if they're not connected together.

The last two steps (linear algebra and square root) need to be performed on conventional HPC hardware, such as a cluster of computers with very fast interconnects. However, the majority of computing power is spent on the sieving step, and it parallelizes very well.

Here are two examples of such large computations, taken from the linked Wikipedia article: a 795-bit integer and an 829-bit integer. However, as you can see, these are very far away from moduli sizes used in practice: 2048-bit and 4096-bit integers.

Note that NFS has superpolynomial (indeed, subexponential) computational complexity, so moduli used in practice are completely, absolutely out of reach of NFS, even with very large budgets. A 1024-bit integer factorization would make for a seminal paper, given that it was a size used in the real world not too long ago, yet you don't see anyone publishing that paper yet because it would take simply too many resources.

And so that’s the lure of quantum computers: Shor’s algorithm can factor in polynomial time on a quantum computer, while the best we can do on a classical computer is superpolynomial time. Very roughly speaking, it’s about as easy to factor an RSA modulus in a quantum computer than it is to generate an RSA key, or encrypt/sign/decrypt/verify using RSA on a classical computer.

$\endgroup$
2
  • 2
    $\begingroup$ I'm not sure this address the actual question, which seems to be whether Shor's algorithm could be parallelized on small quantum computers. $\endgroup$
    – Maeher
    Commented Mar 5, 2023 at 9:17
  • $\begingroup$ @Maeher rereading this question, perhaps both of us interpreted this incorrectly. Looks like he's asking about simulating Shor's algorithm on classical computers. $\endgroup$
    – swineone
    Commented Mar 5, 2023 at 13:29

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.