"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 · 23m 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.
wasabi991011 · 1h ago
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).
fcpguru · 3h 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 · 1h ago
This is probably one of the first academic papers I've ever read completely from beginning to end in one go.
jojobas · 27m 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
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.