4 ms·
What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.
by nyeah 4mo ago
What are you assuming about overflow? Three 32-bit numbers multiply out to 96 bits.
- deleted 4mo ago[deleted]
- shiandow 4mo agoIf you bring overflow into the mix things become a lot more complicated. You likely don't even need 32 bits, the numbers 2 and 3 might be enough (I don't know for sure or if there's a quick way to check).
- thaumasiotes 4mo agoWell, if you "bring overflow into the mix", what you get depends on your behavior when overflowing. If you say that you want to be doing modular arithmetic instead of arithmetic, it doesn't look like 2 and 3 are enough. You're looking for a solution to 2ᵃ * 3ᵇ ≡ n (mod 2⁶⁴) If n is even, we can supply any number of 2 factors by fiddling with a. We can assume without loss of generality that n is odd and a = 0. Now we want 3ᵇ ≡ n (mod 2⁶⁴) for odd n. If I'm reading wikipedia correctly, we know that this will fail for some n: https://en.wikipedia.org/wiki/Primitive_root_modulo_n https://en.wikipedia.org/wiki/Primitive_root_modulo_n > In symbols, g is a primitive root modulo n if for every integer a coprime to n, there is some integer k for which gᵏ ≡ a (mod n). This is what we want, with g = 3, k = b, a = n₁, and n₂ = 2⁶⁴. Our restriction that n₁ (our n) is odd satisfies the requirement that a be coprime to n₂ (wikipedia's n, the modulus). The article continues: > a primitive root exists modulo n if and only if n is 4, pᵏ or 2pᵏ for some odd prime number p and some k ≥ 0. 2⁶⁴ does not satisfy this requirement and therefore there is no primitive root modulo 2⁶⁴. As such, 3 is not a primitive root modulo 2⁶⁴.
- shiandow 4mo agoInteresting, one of those situations where the odd primes behave slightly differently. Which means it's probably above my paygrade. I did say things would get complicated.