←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.205s | 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. shiandow ◴[31 Aug 25 14:29 UTC] No.45083397[source]▶
It is phrasing mathematicians sometimes use. In this sentence 'mod 4' does not indicate an operator but denotes what number system you are in.

For instance the following are equivalent:

2 = 6 mod 4

6 = 2 mod 4

This 'mod 4' can also appear in parentheses or in some other way, but it must appear at the end. Like I said it is not an operator rather it denotes that the entire preceding statement takes place in the appropriate quotient space.

So it is not (multiplying by (4 mod 21)) but ((multiplying by 4) mod 21)