# Thread: The fastest way to test primality ?

1. ## The fastest way to test primality of the number ?

What is the fastest way to check if this number is a prime number ?

$\displaystyle MM_{31}=2^{2^{31}-1}-1$

2. ## Re: The fastest way to test primality of the number ?

I would probably use the Lucas-Lehmer primality test, but even with that you have to run the trial 2,147,483,645 times. That being said this number has been shown to have at least four factors.

3. ## Re: The fastest way to test primality of the number ?

Originally Posted by wsldam
I would probably use the Lucas-Lehmer primality test, but even with that you have to run the trial 2,147,483,645 times. That being said this number has been shown to have at least four factors.
Miller-Rabin test is probably faster than Lucas-Lehmer . Do you know how it is discovered that number has at least four factors ?

4. ## Re: The fastest way to test primality of the number ?

This is what I read... he used his own sieving program

https://listserv.nodak.edu/cgi-bin/w...0&F=&S=&P=2514

5. ## Re: The fastest way to test primality of the number ?

Originally Posted by wsldam
This is what I read... he used his own sieving program

https://listserv.nodak.edu/cgi-bin/w...0&F=&S=&P=2514
Thanks..I have found this one : Mfaktc