3 ms·
Ah took me some time to understand why this works: Every uint32 can be expressed as k=3*N mod 2^32. We can get that N by multiplying by the modular inverse. k
by im3w1l 10y ago
Ah took me some time to understand why this works:
Every uint32 can be expressed as k=3*N mod 2^32. We can get that N by multiplying by the modular inverse. k is divisible by 3 if and only if the multiplication 3N doesn't "wrap around".
So: Multiply by modular inverse to get N, check that it's small enough that 3N < 2^32 ore equivalently that N < 2^32 / 3 = 0x55555556.