[Cryptography] Has quantum cryptanalysis actually achieved anything?

[Jon Callas]

> On Feb 19, 2025, at 15:42, Peter Gutmann <pgut001 at cs.auckland.ac.nz> wrote:
> 
> When I did the "Why quantum cryptanalysis is bollocks" writeup I avoided
> getting bogged down in technical detail and just went for the empirical
> gnosticism, because once you fall into the mathematical/physics sophistry you
> can make people believe anything.
> 
> However someone recently pointed out that since the only two non-smoke-and-
> mirrors factorisations we have, of 15 and 21, used the compiled form of Shor's
> algorithm, which requires knowing the answer in advance and takes advantage of
> special properties of the numbers, it could actually be claimed that we have
> zero cases of quantum cryptanalysis working in a real-world scenario, not two.
> 
> (For a quick overview of how this works, see "Pretending to factor large
> numbers on a quantum computer", John Smolin, Graeme Smith, and Alex Vargo).
> 
> Since pointing this out is going to make a lot of people very angry, what
> would be the best way of stating this?

Apropos of the commentary that you've kindly quote me on, here's what I say.

As a factoid, the special forms that 15 and 21 have is that they're 2^n-1 * 2^n+1 -- so a string of 1 bits times a high bit, a bunch of zero bits, and then the low bit.

The next technological step we need is a quantum computer that is basically a REPL loop. You tell it a number you want to factor and it does it. Poof.

The size of the number doesn't matter, and in fact can be used to show progress. So, for example, factor any 5-bit number. 31 or less. Or any two-digit number -- 99 or less. Then like maybe a 10-bit number. 20-bits. 6-digits.

What they need to do is to show an interactive or even quasi-interactive (like a batch job -- give us the number and we'll get back to you) where a human says, "factor this" and it does.

	Jon