5 ms·
> 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 imp
by taway789aaa6 1y ago
> 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?
- oh_my_goodness 1y agoI mean 4 is equivalent to 4 mod 21. That part's not AI slop.
- JohnKemeny 1y agoI think, in fact, for every prime number p at least 5, 4 mod p is (congruent to) 4.
- oh_my_goodness 1y agoEven without the restriction to primes, that feels like a pretty good guess!
- freehorse 1y agoOr for less than 5.
- oh_my_goodness 1y agolol good point.
- shiandow 1y agoIt 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)
- layer8 1y agoSee https://en.wikipedia.org/wiki/Modular_arithmetic https://en.wikipedia.org/wiki/Modular_arithmetic. It means that the multiplication is performed modulo 21.
- taway789aaa6 1y agoThank you!
- AnotherGoodName 1y agoFractions 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.