mersenneforum.org > Math Question on modular exponentiation?
 Register FAQ Search Today's Posts Mark Forums Read

 2015-10-31, 13:55 #1 ramshanker     "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 P-1 factoring test) than can we use Fermat's little theorem in following way? aE (mod q) - 1 ≡ aE (mod (q-1)) (mod q) - 1 because a (q-1) ≡ 1 (mod q) by Fermat little theorem. Last fiddled with by ramshanker on 2015-10-31 at 13:56
 2015-10-31, 15:00 #2 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 24·613 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 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. Last fiddled with by LaurV on 2015-10-31 at 15:06
2015-10-31, 15:28   #3
ramshanker

"Ram Shanker"
May 2015
Delhi

2616 Posts

Quote:
 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post carpetpool Information & Answers 2 2017-11-03 07:24 LaurV Homework Help 7 2012-05-16 16:52 Unregistered Homework Help 4 2010-08-04 06:38 Numbers Math 27 2005-11-30 15:41 Greenbank Math 5 2005-09-30 10:20

All times are UTC. The time now is 09:09.

Mon Nov 29 09:09:54 UTC 2021 up 129 days, 3:38, 0 users, load averages: 0.91, 1.19, 1.22