Marcel Waldvogel

Earlier this week, Peter Gutmann and @sten published a bombshell paper: The looked at all the reported factorization "breakthroughs" in quantum computing. And found that all of them essentially were magician's tricks, "sleight of hand".

The two reconstructed the algorithms used on a 1981 home computer (a million times less powerful than what you hold in your hand now), an #Abacus and with a #dog.
#VIC20 #VC20
https://eprint.iacr.org/2025/1237

Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog

This paper presents implementations that match and, where possible, exceed current quantum factorisation records using a VIC-20 8-bit home computer from 1981, an abacus, and a dog. We hope that this work will inspire future efforts to match any further quantum factorisation records, should they arise.

IACR Cryptology ePrint Archive
Jul 17, 2025 at 6:13amWeb
Show threadMarcel WaldvogelJul 17, 2025

Of course, besides the critique, they also provide guidance on how a "real" #quantum factorization experiment should be designed.

The text is easy to read even without #QuantumComputing background.

And it is absolutely worthwhile to at least read the footnotes. Some of them definitely made my day!
@sten
https://eprint.iacr.org/2025/1237

Replication of Quantum Factorisation Records with an 8-bit Home Computer, an Abacus, and a Dog

This paper presents implementations that match and, where possible, exceed current quantum factorisation records using a VIC-20 8-bit home computer from 1981, an abacus, and a dog. We hope that this work will inspire future efforts to match any further quantum factorisation records, should they arise.

IACR Cryptology ePrint Archive
Show threadMarcel WaldvogelJul 17, 2025
If you want to learn more about the current state of #QuantumComputing especially with respect to #QuantumFactorisation, but not only, have a look at these recent slides by Samuel Jaques.
@sten
https://pqcrypto2025.iis.sinica.edu.tw/slides/Invited3.pdf
Show threadStephanJul 17, 2025

@marcel @sten The talk is on Youtube:

https://www.youtube.com/watch?v=nJxENYdsB6c

Expected and Unexpected Developments in Quantum Computing

YouTube
Show threadMax NordlundJul 19, 2025

@marcel @sten

"We use the UK form “factorise” here in place of the US variants “factorize” or “factor” in order to avoid the 40% tariff on the US term." 😂

Show threadStephanJul 17, 2025

@marcel @sten

That is not a bombshell for anyone outside the quantum bubble. Even Stack Exchange knew all along.
https://crypto.stackexchange.com/questions/59795/largest-integer-factored-by-shors-algorithm

Related 2013 paper:
“Pretending to factor large numbers on a quantum computer”
https://arxiv.org/abs/1301.7007

Largest integer factored by Shor's algorithm?

I'm studying Shor's quantum factoring algorithm. I was wondering what the largest integer is which they were able to factor with a small quantum computer. Does anybody have an idea about this?

Cryptography Stack Exchange
Show threadMarcel WaldvogelJul 17, 2025

@erlenmayr @sten
They do reference all the individual papers that identified these things on an individual basis. So, the basic research had already been done. But I've never seen it put together so nicely and completely.

(And including their explanations and "replication" studies is definitely helpful/fun/enlightening.)

Show threadStephanJul 17, 2025

@marcel @sten Yes, this writeup is really enjoyable.

Also note Peter Gutmann's slide deck:
https://www.cs.auckland.ac.nz/~pgut001/pubs/bollocks.pdf

Show threadStephan NeuhausJul 17, 2025
@erlenmayr @marcel That slide deck is from an earlier discussion and doesn't directly relate to the paper. I'll put up my slides for the paper once they're finished.
Show threadStephan NeuhausJul 17, 2025
@erlenmayr @marcel That is in fact one of the papers we cite. It relates to the "compiled" version of Shor's algorithm that allows one to factorise any N made up of two distinct prime factors with just 2 qubits.
Show threadMike SpoonerJul 17, 2025

@marcel @sten

Great footnote:

'We use the UK form “factorise” here in place of the US variants “factorize” or “factor” in order to avoid the 40%
tariff on the US term.'

Show threadStephan NeuhausJul 17, 2025
@marcel Hashtag dog, eh? Let's see what kind of answers you get for this 😋
Show threadchrysnJul 18, 2025
@marcel @sten I appreciat that there is a footnote elaborating on why the dog, Scribble, is not credited as an author (like F. D. C. Willard was).
I've seen the 2024 Bollocs presentation at #ITSNow, and am glad that there is now a paper to go with the claims.
Show threadStephan NeuhausJul 18, 2025

@chrysn @marcel There is a presentation just for this paper, but I haven't given it yet in front of an audience: https://codeberg.org/sten13/rsa6502/src/branch/main/rsa6502.pdf

Poor Scribble, enough contributions to not need IRB approval, yet not enough to warrant co-authorship. Maybe we can do something about that in a future edition of the paper, perhaps when it's submitted to something peer-reviewed.

rsa6502/rsa6502.pdf at main

rsa6502 - Code to factor the 2048-bit RSA "moduli" from C. Wang, J. Yu, Z. Pei, Q. Wang and C. Hong, "A First Successful Factorization of RSA-2048 Integer by D-Wave Quantum Computer," in Tsinghua Science and Technology, vol. 30, no. 3, pp. 1270-1282, June 2025, doi: 10.26599/TST.2024.9010028.

Codeberg.org
Show threadkætJul 18, 2025
@marcel @sten The paper underplays its results. It factors those numbers with a VIC-20, an abacus, OR a dog.
Show threadBruno GirinJul 18, 2025
@marcel @sten oh cool, they used a VIC-20! This was the first computer I ever used when my school got one thanks to one of the maths teachers. I got popular with the other kids when I learnt how to load and run the games.
Show threadStephan NeuhausJul 19, 2025
@brunogirin @marcel And now you can use it to break quantum factorisation records! How cool is that? 🙂
Show threadnoplasticshowerJul 18, 2025
@marcel @sten peter is so damn funny
Show threadOblomovJul 18, 2025

@marcel @sten

«We use the UK form “factorise” here in place of the US variants “factorize” or “factor” in order to avoid the 40% tariff on the US term.»

You can tell this paper is genius just from the footnotes.

Show threadDavid GerardJul 18, 2025
@marcel cc @hipsterelectron
Show threadd@nny disc@ mc²Jul 19, 2025
@davidgerard @marcel THANK YOU
Show threadjlapoutreJul 18, 2025
@marcel @sten This is so incredible funny and wise at the same time, I would award them an Ig-Nobel (or the field medal equivalent)
Show threadeuroplus Jul 19, 2025
@marcel @sten @sehugg 14/10 would factorise (and pat)
Show threadUr Ya'arJul 26, 2025

@marcel

I enjoyed reading very much, but, as someone not familiar with the previous papers, failed to understand why the "records" are merely tricks and not actually using Shor's algorithm or require an actual quantum computer.

As far as I understand the "record-breakings" did not attempt to replicate the algorithms used, but only showed that there are algorithms for doing these factorisations.
@sten

Show threadStephan NeuhausAug 16, 2025
@yaarur @marcel The point is that the papers merely say that they used "quantum" to factorise some large number, relying on the reader to imagine details like "...with a proper quantum algorithm like Shor's" and "...where the number to be factorised is chosen more or less randomly". Because if you announced that you had chosen the numbers so that even a dog could factorise them, then the obvious question would be "but why use a quantum computer for that".