[kirillcool]

Good luck running ^4 on larger numbers and overflowing integer / long bounds orders of magnitude faster than the plain "boring" solutions

[Jtsummers]

The 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]

Well, 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.

[bidirectional]

Modular 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]

Python'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.

[anthk]

https://medium.com/@c0D3M/introduction-to-rsa-e8cb39af508e

EDIT: Pasting into Lynx screwed formatting from Groff.

[Jtsummers]

> a^n % b = a % b.

That is not generally true. A quick counterexample:

  a = 2, n = 3, b = 5
  2^3 % 5 = 8 % 5 = 3
  2 % 5 = 2
  3 != 2

[anthk]

I was to type something like

       (a ^ n) % n = a % n

[anthk]

I missed something from Groff, sorry.