Why haven't quantum computers factored 21 yet?

> 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?

I mean 4 is equivalent to 4 mod 21. That part's not AI slop.

I think, in fact, for every prime number p at least 5, 4 mod p is (congruent to) 4.

Even without the restriction to primes, that feels like a pretty good guess!

Or for less than 5.