Score:0

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?

do flag

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.

fgrieu avatar
ng flag
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](https://crypto.stackexchange.com/a/105495/555)) or quantum. That's the crux of the issue: classical computers can't run an "algorithm like the Shor's algorithm".
poncho avatar
my flag
@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...
Score:3
ru flag

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.

cn flag
I'm not sure this address the actual question, which seems to be whether Shor's algorithm could be parallelized on small quantum computers.
swineone avatar
ru flag
@Maeher rereading this question, perhaps both of us interpreted this incorrectly. Looks like he's asking about simulating Shor's algorithm on classical computers.
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.