[Cryptography] Factoring safe semiprimes

[Stephan Neuhaus]

On 10/15/25 08:04, Pierre Abbat wrote:
> a quantum computer faster than Shor's algorithm. However, their algorithm uses
> the same quantum order-finding algorithm as Shor's algorithm, which Cài Jìn-Yī
> showed cannot factor products of large Fouvry primes in the presence of noise.

Is it really true that Shor can't factor large semiprimes in the 
presence of noise? Like, at all? As I read their result, it meant that 
in the presence of noise (i.e., always), Shor's Algorithm will "almost 
certainly fail" for large semiprimes, but all that means is that one 
needs ever greater numbers of qubits for error correction.

> prime. What's the largest Cài semiprime that has been factored with a quantum
> computer?

That's a trick question. Depending on the amount of sleight-of-hand that 
you can tolerate, the answer ranges from "none" to "21" to "very many".

Cheers

Stephan