mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2015-10-31, 13:55   #1
ramshanker
 
ramshanker's Avatar
 
"Ram Shanker"
May 2015
Delhi

2×19 Posts
Default 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
ramshanker is offline   Reply With Quote
Old 2015-10-31, 15:00   #2
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
"name field"
Jun 2011
Thailand

24·613 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2015-10-31, 15:28   #3
ramshanker
 
ramshanker's Avatar
 
"Ram Shanker"
May 2015
Delhi

2616 Posts
Default

Quote:
Originally Posted by LaurV View Post
I think you are trying to "improve" the method.

So, you can not get around that long exponentiation.
Ohh, better luck next time.
ramshanker is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Modular Exponentiation results in PFGW carpetpool Information & Answers 2 2017-11-03 07:24
Modular question :) LaurV Homework Help 7 2012-05-16 16:52
Exponentiation w/ independent variable Unregistered Homework Help 4 2010-08-04 06:38
Modular Arithmetic Numbers Math 27 2005-11-30 15:41
optimum multiple exponentiation 'problem' 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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.