20151031, 13:55  #1 
"Ram Shanker"
May 2015
Delhi
2×19 Posts 
Question on modular exponentiation?
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 P1 factoring test) than can we use Fermat's little theorem in following way? a^{E} (mod q)  1 ≡ a^{E (mod (q1))} (mod q)  1 because a^{ (q1)} ≡ 1 (mod q) by Fermat little theorem. Last fiddled with by ramshanker on 20151031 at 13:56 
20151031, 15:00  #2 
Romulan Interpreter
"name field"
Jun 2011
Thailand
2·7^{2}·103 Posts 
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 P1 algorithm q is the (prime) number we need to find, the factor, so the terminology can be confuse. The modulus is m=2^p1, we do all calculus mod m. And m is not a prime. In this case, your equation is not true, you have to replace q1 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 (x1)*(y1), which is different of q1, and unknown.
So, you can not get around that long exponentiation. Last fiddled with by LaurV on 20151031 at 15:06 
20151031, 15:28  #3 
"Ram Shanker"
May 2015
Delhi
38_{10} Posts 

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Modular Exponentiation results in PFGW  carpetpool  Information & Answers  2  20171103 07:24 
Modular question :)  LaurV  Homework Help  7  20120516 16:52 
Exponentiation w/ independent variable  Unregistered  Homework Help  4  20100804 06:38 
Modular Arithmetic  Numbers  Math  27  20051130 15:41 
optimum multiple exponentiation 'problem'  Greenbank  Math  5  20050930 10:20 