CODEWITHSUNDEEP
javascriptpythonmathnumber-theorymodular-arithmetic
Patryk Grzyb
Patryk Grzyb

Reputation: 43

Square number multiple times

I'm looking for a way to square a number n, x times and get the answer in modulo m (m is prime)? For example, if n = 5, x = 3 and m = 7, it would be (((5^2)^2)^2) % 7 = 390625 % 7 = 4

I tried exponentiation by squaring (I have a function called modularPow that accepts base, power, mod), and in this case it would simply be modularPow(5, 2^3, 7), which produces the correct answer. But the problem is, that x can be very big, even 10^12, so I would have to do modularPow(5, 2^(10^12), 7), which won't work. Is there any better way to do it? Preferably in Javascript, but Python would also work for me

Upvotes: -3

Views: 206

Answers (1)

Simon Goater
Simon Goater

Reputation: 1908

Euler's Theorem states that if gcd(a,n) = 1, where gcd() is the greatest common divisor, then

a^(phi(n)) = 1 mod n

where phi() is Euler's Totient function. So, from this we know that any exponent of a can instead be calculated modulo phi(n). Suppose y = w phi(n) + u where 0 <= u < phi(n), then

a^y mod n = a^(w phi(n) + u) mod n = (a^(phi(n))^w)a^u mod n = a^u mod n

Therefore,

gcd(a,n) = 1 => (a^y mod n = a^(y mod phi(n)) mod n)

If y = z^k, with gcd(y,phi(n)) = 1, then

y mod phi(n) = z^(k mod phi(phi(n))) mod phi(n)

and so on. So for example,

modularPow(5, 2^(10^12), 7) = modularPow(5, modularPow(2, 10^12, 6), 7)

since gcd(5,7) = 1 and phi(7) = 6 but we can't go on to another level in this case because gcd(2,6) = 2. If gcd(a,n) = g where g != 1, then it's a bit trickier. You have to compute

a^y mod (n/g)

and

a^y mod g

separately and then combine the results with the Chinese Remainder Theorem.

Upvotes: 0

Related Questions