5 ms·
Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions
by kirillcool 6y ago
Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions
- bidirectional 6y agoModular exponentiation can be done very quickly, you don't need to compute n^4 at all. Not sure if this particular implementation makes use of that, though. In Haskell, I can compute (100000 ^ 1000000 `mod` 15) near instantly.
- nonameiguess 6y agoPython's built in pow function does this, but the ** operator does not. Of course, like Haskell, it also uses arbitrary precision integers by default, so it might take forever to compute something, but it won't overflow unless you actually run out of memory.
- Jtsummers 6y agoThe trick is to do the modulus before the exponentiation. It gives the same result. n^4 % x = m == (n % x)^4 % x = m By way of demonstration: n = 18, x = 15 18^4 = 104976 = 6 (mod 15) ---- 18 % 15 = 3 3^4 = 81 = 6 (mod 15) A very handy result to remember for cases where you don't want to use or don't have easy access to arbitrary precision integers.
- anthk 6y agoWell, this doesn't need much of a demonstration. The rest of a division will be the same "visually" if you keep "stacking" the same number on top.
- anthk 6y agohttps://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e EDIT: Pasting into Lynx screwed formatting from Groff.