Question on modular exponentiation?

[ramshanker]

I have started learning number theory bit by bit. Mostly online. I made an observation and need to confirm if I am thinking correctly?

If "a" and "q" are both prime number and E some really large composite number (as in P-1 factoring test) than can we use Fermat's little theorem in following way?

a^E (mod q) - 1 ≡ a^{E (mod (q-1))} (mod q) - 1

because a ^(q-1) ≡ 1 (mod q) by Fermat little theorem.

[LaurV]

I think you are trying to "improve" the method. Been there, in the beginning. Like everyone else. The problem is that, generally, q is not a prime. In P-1 algorithm q is the (prime) number we need to find, the factor, so the terminology can be confuse. The modulus is m=2^p-1, we do all calculus mod m. And m is not a prime. In this case, your equation is not true, you have to replace q-1 from the exponent with Euler's totient. For example if q is a product of 2 primes x and y, the exponent is then mod (x-1)*(y-1), which is different of q-1, and unknown.

So, you can not get around that long exponentiation.

[ramshanker]

Originally Posted by LaurV

I think you are trying to "improve" the method.

So, you can not get around that long exponentiation.

Ohh, better luck next time.