Primality Tresting

I would like to know what is the correct way to approach the problem?

1 Like

Try using miller rabin primality test.

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

Also, you may try reading this: https://docs.google.com/viewer?a=v&q=cache:pcBEzTliZ2kJ:www.math.uic.edu/~marker/math435/rm.pdf+&hl=en&gl=in&pid=bl&srcid=ADGEESho0Ovr4aYe6TJNjR1-s2a8fLfjNRI7RuxirPPoHXb1izcO9_l4ebEil72XeVuYr92VVENF2M19BLfD9PAGaLPPf4T0tTCTHhf_j48ER5KaRIFtqGtFQ1M7DR0wkxGsTg58F_9y&sig=AHIEtbR4HXXFeTni3O8saLip-a2xSA2X3A

and

https://docs.google.com/viewer?a=v&q=cache:lBz_-rZqdwIJ:home.sandiego.edu/~dhoffoss/teaching/cryptography/10-Rabin-Miller.pdf+&hl=en&gl=in&pid=bl&srcid=ADGEESgMM54f1pbKQNbyPZMxcUfnftwpplhaEtl5KVkrtDz4-RJX16DvsvlQo33PMTUccJ0z6Sezr4tOZsIm7Mi8WLy38Dsgk8bHc9dOUCgDh0A-qHmFWKbLLXxYPV5EiOpUs2YccQ9U&sig=AHIEtbRu3CaSB-DYm_z68Ptd7tneMrqEoQ

1 Like
//