←back to thread

Why haven't quantum computers factored 21 yet?

(algassert.com)
335 points ingve | 1 comments | 31 Aug 25 12:14 UTC | HN request time: 0.217s | source
Show context
taway789aaa6 ◴[31 Aug 25 14:03 UTC] No.45083214[source]▶
> Third, notice that the only remaining multiplication is a multiplication by 4. Because 15 is one less than a power of 2, multiplying by 2 modulo 15 can be implemented using a circular shift. A multiplication by 4 is just two multiplications by 2, so it can also be implemented by a circular shift. This is a very rare property for a modular multiplication to have, and here it reduces what should be an expensive operation into a pair of conditional swaps.

> Aside: multiplication by 16 mod 21 is the inverse of multiplying by 4 mod 21, and the circuits are reversible, so multiplying by 16 uses the same number of Toffolis as multiplying by 4.

I couldn't really find anything explaining the significance of this. The only info I found said that "4 mod 21 = 4" (but I don't know if it was AI slop or not).

Is "multiplying by 4 mod 21" something distinct to quantum computing?

replies(4): >>45083381 #>>45083397 #>>45083794 #>>45083963 #
1. AnotherGoodName ◴[31 Aug 25 15:31 UTC] No.45083963[source]▶
Fractions are under any modulus are actually representable as whole numbers (provided they don’t share factors with the modulus).

For example under mod 21 a half can actually be represented by 11. Try it. Times any even number by 11 and you’ll see you halved it.

Take any number that’s a multiple of 4 and times it by 16 under mod 21. You now have that number divided by 4.

Etc.

Absolutely nothing to do with quantum computers.