If suitably powerful quantum computers can one day be built, many cryptosystems in common use today could be vulnerable due to something called quantum factorisation. Dr Stephan Neuhaus, senior lecturer at InIT, and Dr Peter Gutmann of the University of Auckland show in a new paper that all currently published records in quantum factorisation were only achieved through trickery. In order to demonstrate that these do not pose a threat to currently used cryptosystems, they replicate those records with an 8-bit home computer from 1981, an abacus, and a dog.
The paper.
It’s worth a read. Lotta sarcasm going on.
16 pages. Dogs. Cards. Odds. Lies. Tariffs.
eprint.iacr.org/2025/1237.pdf
dbtng@eviltoast.org 6 days ago
Technocrit buried the lead when they posted this. Here it is with the actual paper highlighted.
CombatWombatEsq@lemmy.world 6 days ago
dbtng@eviltoast.org 5 days ago
Yes. Exactly.
Also, heres those two numbers in binary.
15 = 11111
21 = 10101
So, those are special numbers. Its straight up cheating.
dbtng@eviltoast.org 5 days ago
I’ve chewed on Gidney’s ‘Falling with Style’ paper.
I recommend reading it if you would like to understand Shor’s Algorithm.
I’m somewhat unclear if the following applies to Shor’s Algorithm in general, or just the modified version used for the experiment.
But I’ve come to understand that the algorithm is a recursive series of steps, structured such that it will eventually factor anything.
Like … it could take longer than the age of the universe for some numbers, but the algorithm will do the job if you got enough cycles to spare.
What we are looking for here is quantum supremacy, and once Gidney has explained this much, its obvious from the graph above that we are not seeing it. Pure random noise outperformed the quantum computer.
I guess the thing I’ve not absorbed yet is, why was the quantum computer expected to not work? I know it was much too complex a system, and internal noise would overwhelm any processing. Gidney described being amazed that the IBM quantum system even let him configure his experiment and run it. Why did it lose so completely to a random noise generator, as in how could you possibly get worse than random noise?