[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Peter Gutmann]

Bill Stewart <billstewart at pobox.com> writes:
>On 2/24/2025 12:03 PM, Jon Callas wrote:
>>     Oh lord, they published it <screen shot> [This is the paper on the D-Wave
>>     factorization of a 2048-bit RSA number -- jdcc]
>>     <https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10817698>
>>     If you look at the ten "2048-bit factorizations" in appendix S1, the distance
>>     p-q between the factors is either 2 (a prime pair) or 6. You just compute square
>>     root of n and guess one bit -- the complexity is literally 2^1.
>>
>> So there's another slight-of-hand trick. Pick a number with the primes really close to each other. 
>
>Cool! Nice to know we don't have to actually worry about this,

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.