Find x in a^x = a (mod n)

Question

I want to calculate a^m mod n, where n is a prime number, and m is very large. Rather doing this with binary power calculation, I'd like to find such x that a^x = a (mod n) and then calculate a^{(m mod x)} mod n.

Obviously such x exists for any a, because powers mod n loop at some point, but I didn't find out how to calculate it with modular arithmetics. I wonder if I missed something or maybe there exists some numerical method for that?

Answer 1

Your modulus is prime, that makes it easy to get a start, as by Fermat's (inappropriately dubbed "little") theorem, then

a^n ≡ a (mod n)

for all a. Equivalent is the formulation

a^(n-1) ≡ 1 (mod n),  if n doesn't divide a.

Then you have

a^m ≡ 0 (mod n) if a ≡ 0 (mod n) and m > 0

and

a^m ≡ a^(m % (n-1)) (mod n) otherwise

(note that your suggested a^(m % x) is in general not correct, if m = q*x + r, you'd have

a^m ≡ (a^x)^q * a^r ≡ a^q * a^r ≡ a^(q+r) (mod n)

and you'd need to repeat that reduction for q+r until you obtain an exponent smaller than x).

If you are really interested in the smallest x > 1 such that a^x ≡ a (mod n), again the case of a ≡ 0 (mod n) is trivial [x = 2], and for the other cases, let y = min { k > 0 : a^k ≡ 1 (mod n) }, then the desired x = y+1, and, since the units in the ring Z/(n) form a (cyclic) group of order n-1, we know that y is a divisor of n-1.

If you have the factorisation of n-1, the divisors and hence candidates for y are easily found and checked, so it isn't too much work to find y then - but it usually is still far more work than computing a^r (mod n) for one single 0 <= r < n-1.

Finding the factorisation of n-1 can be trivial (e.g. for Fermat primes), but it can also be very hard. In addition to the fact that finding the exact period of a modulo n is usually far more work than just computing a^r (mod n) for some 0 <= r < n-1, that makes it very doubtful whether it's worth even attempting to reduce the exponent further.

Generally, when the modulus is not a prime, the case when gcd(a,n) = 1 is analogous, with n-1 replaced by λ(n) [where λ is the Carmichael function, which yields the smallest exponent of the group of units of Z/(n); for primes n, we have λ(n) = n-1].