I would like to know what is the correct way to approach the problem?
1 Like
Hi saikrishna73,
As ani94 pointed it out, Miller Rabin Primality Test is the go about for such problems. But before reading and understanding it, I think it would be better if you read about Fermat’s little theorem, and the “issues” with it. Meanwhile, the following text, and links should be helpful! Take a look.
"Suppose p was prime, and y was a non-trivial square root of 1 mod p.
Then we must have that y2=1modp and so (y−1)(y+1)=0modp. This implies that either y=1modp or y=−1modp, which implies that y is a trivial square root.
Thus, if there is a non-trivial square root of 1 mod p, then p has to be composite.
For an example of a non trivial square root of a composite, consider p=15. We have that 42=16=1mod15. Thus 15 is composite.
Note that the witness in the primality test is not necessarily a non-trivial square root of 1 mod p.
The fact about non-trivial square roots can be used to prove that if p is prime, then for any a relatively prime to p, some power of a from a given set of powers (the powers are based on the even factors of p−1) must be −1 or a specific odd power of a (again based on factor of p−1) must be 1.
If for some a none of the above set of powers is −1 and the specific odd power is not 1, then it must be the fact that p is composite.
It can also be shown that for composite p, the chances of finding such a is atleast 3/4. This a is the witness in the primality test and is not necessarily a non-trivial square root of 1 mod p.
The squaring that is done is to get the powers described above which are based on the factors of p−1.
The wiki page has really got a lot of good information (including the exact powers of a that need to be taken)" - http://math.stackexchange.com/questions/4597/simple-explanation-and-examples-of-the-miller-rabin-primality-test
and
1 Like