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).
tromp · 1h ago
> 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}.
qualeed · 2h ago
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."
remcob · 2h ago
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.
fcpguru · 5h ago
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.
neuroelectron · 2h ago
This is probably one of the first academic papers I've ever read completely from beginning to end in one go.
jojobas · 2h ago
>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
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}.
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."
The dog is funny but it just means, pick actually "random" numbers from a bigger range than the staged phony numbers quantum factorisation uses.
Brilliant.