Calculating Pow(A,B) Mod N

Calculating pow(a,b) mod n

You can try this C++ code. I've used it with 32 and 64-bit integers. I'm sure I got this from SO.

template <typename T>
T modpow(T base, T exp, T modulus) {
  base %= modulus;
  T result = 1;
  while (exp > 0) {
    if (exp & 1) result = (result * base) % modulus;
    base = (base * base) % modulus;
    exp >>= 1;
  }
  return result;
}

You can find this algorithm and related discussion in the literature on p. 244 of

Schneier, Bruce (1996). Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition (2nd ed.). Wiley. ISBN 978-0-471-11709-4.

---

Note that the multiplications result * base and base * base are subject to overflow in this simplified version. If the modulus is more than half the width of T (i.e. more than the square root of the maximum T value), then one should use a suitable modular multiplication algorithm instead - see the answers to Ways to do modulo multiplication with primitive types.

Calculating (a^b)%MOD

That's a typical task. Please (or, really, PLEASE!) read about the Euler's totient function.

And then the Euler's theorem.

The thing is you can dramatically reduce a^b to a^(b % phi(MOD)). Yes, you will need some kind of an integer factorization method, but still, no crazy ideas about actually calculating the power needed.

We did such samples by hand in my youth :) Even when the numbers where far beyond 32/64 bit range.

EDIT: Well, you live and learn. In 2008 the result is obtained:

"The totient is the discrete Fourier transform of the gcd: (Schramm (2008))"

So to calculate phi(b) one does not need to know its factors.

EDIT(2):

And the Carmichael's function is what you need to calculate to get the correct answer for any a, b and MOD.

calculate mod using pow function python

It's simple: pow takes an optional 3rd argument for the modulus.

From the docs:

pow(x, y[, z])

Return x to the power y; if z is present, return x to the power y, modulo z (computed more efficiently than pow(x, y) % z). The
two-argument form pow(x, y) is equivalent to using the power operator:
x**y.

So you want:

pow(6, 8, 5)

Not only is pow(x, y, z) faster & more efficient than (x ** y) % z it can easily handle large values of y without using arbitrary precision arithmetic, assuming z is a simple machine integer.

Calculating very large power

Looking at the answer on maths.stackexchange where the formula comes from, it appears that the easiest thing to calculate are the a(n).

So, this can be calculated by recurence very simply, and this time, as we only use multiplications and additions, we can take advantage of the rules of modulo arithmetic and keep the numbers we manipulate small:

def s(n, mod):
    a1 = 1
    a2 = 3
    for k in range(n-1):
        a1, a2 = a2, (3*a2 + 2* a1) % mod
    return (a1 + a2) % mod


mod = 1000000007

print(s(10, mod))
# 363314, as with the other formulas...

print(s(10**6, mod))
# 982192189

%timeit s(10**6, mod)
# 310 ms ± 6.46 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

%timeit s(10**7, mod)
# 3.39 s ± 93.8 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)

We get the same results as with the other formulas, (which is a really good thing...). As the numbers used during the calculation keep the same size, at most 5 times the modulo, the calculation time is about O(n) - s(10**7) takes only 10 times more time than s(10**6).

---

Related Topics