Somewhat related is the work done in "Falling with Style: Factoring up to 255 “with” a Quantum Computer" published in the proceedings of SIGBOVIK 2025 [1]. The author, Craig Gidney [2], successfully factored all odd composite numbers up to 255 using Shor's algorithm, even though the quantum circuits involved were such that any meaningful output would be overwhelmed by noise (and indeed, performance was maintained when the circuits were replaced by a random number generator).
> To my knowledge, no one has cheated at factoring in this way before. Given the shenanigans pulled by past factoring experiments, that’s remarkable.
[2] Who has previous experience in cheating at quantum factoring: see "Factoring the largest number ever with a quantum computer", posted April Fools' Day 2020 at https://algassert.com/post/2000
I remember Peter Gutmann posting about this on the metzdowd cryptography mailing list in March. Fun to see this a few months later.
"Just as a thought experiment, what's the most gutless device that could
perform this "factorisation"? There's an isqrt() implementation that uses
three temporaries so you could possibly do the square root part on a ZX81, but
with 1k of RAM I don't think you can do the verification of the guess unless
you can maybe swap the values out to tape and load new code for the multiply
part. A VIC20 with 4k RAM should be able to do it... is there a programmable
calculator that does arbitrary-precision maths? A quick google just turns up
a lot of apps that do it but not much on physical devices.
Peter."
You can verify in limited memory by repeatedly verifying modulo a few small integers. If that works, then by Chinese remainder theorem the main result also holds.
> In the Callas Normal Form, the factors are integers p = 2^{n-1}
and q = 2^{m+1}, where n ≤ m, and p and q are ideally prime, but don’t have to be.
The paper's formatting clearly went wrong here, as it should have read p = 2^n - 1 and q = 2^m + 1.
The "Proposed Quantum Factorisation Evaluation Criteria" are excellent, but for measuring progress, the required minimum factor size of 64 bits is too large. A good milestone would be a quantum circuit that can factor the product of any pair of 5-bit primes {17,19,23,29,31}.
Yeah there's a reason that the quantum computing field has moved away from attempting factorisations. Not that there's not still hype and misleading claims being punished, but the hardware has improved a ton since 2001 and ever closer to actual useful quantum computation (such as large size quantum chemistry calculations).
this was great. I had no idea quantum factorisation was cooking their books!
The dog is funny but it just means, pick actually "random" numbers from a bigger range than the staged phony numbers quantum factorisation uses.
>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
Brilliant.
This is probably one of the first academic papers I've ever read completely from beginning to end in one go.
Somewhat related is the work done in "Falling with Style: Factoring up to 255 “with” a Quantum Computer" published in the proceedings of SIGBOVIK 2025 [1]. The author, Craig Gidney [2], successfully factored all odd composite numbers up to 255 using Shor's algorithm, even though the quantum circuits involved were such that any meaningful output would be overwhelmed by noise (and indeed, performance was maintained when the circuits were replaced by a random number generator).
> To my knowledge, no one has cheated at factoring in this way before. Given the shenanigans pulled by past factoring experiments, that’s remarkable.
[1] https://sigbovik.org/2025/; standalone paper is also available in the code repository https://github.com/strilanc/falling-with-style
[2] Who has previous experience in cheating at quantum factoring: see "Factoring the largest number ever with a quantum computer", posted April Fools' Day 2020 at https://algassert.com/post/2000
I remember Peter Gutmann posting about this on the metzdowd cryptography mailing list in March. Fun to see this a few months later.
It starts here: https://www.metzdowd.com/pipermail/cryptography/2025-Februar...
This part is from farther down thread:
"Just as a thought experiment, what's the most gutless device that could perform this "factorisation"? There's an isqrt() implementation that uses three temporaries so you could possibly do the square root part on a ZX81, but with 1k of RAM I don't think you can do the verification of the guess unless you can maybe swap the values out to tape and load new code for the multiply part. A VIC20 with 4k RAM should be able to do it... is there a programmable calculator that does arbitrary-precision maths? A quick google just turns up a lot of apps that do it but not much on physical devices.
Peter."
You can verify in limited memory by repeatedly verifying modulo a few small integers. If that works, then by Chinese remainder theorem the main result also holds.
> In the Callas Normal Form, the factors are integers p = 2^{n-1} and q = 2^{m+1}, where n ≤ m, and p and q are ideally prime, but don’t have to be.
The paper's formatting clearly went wrong here, as it should have read p = 2^n - 1 and q = 2^m + 1.
The "Proposed Quantum Factorisation Evaluation Criteria" are excellent, but for measuring progress, the required minimum factor size of 64 bits is too large. A good milestone would be a quantum circuit that can factor the product of any pair of 5-bit primes {17,19,23,29,31}.
Yeah there's a reason that the quantum computing field has moved away from attempting factorisations. Not that there's not still hype and misleading claims being punished, but the hardware has improved a ton since 2001 and ever closer to actual useful quantum computation (such as large size quantum chemistry calculations).
this was great. I had no idea quantum factorisation was cooking their books!
The dog is funny but it just means, pick actually "random" numbers from a bigger range than the staged phony numbers quantum factorisation uses.
>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
Brilliant.
This is probably one of the first academic papers I've ever read completely from beginning to end in one go.