# The fastest way to test primality ?

• Dec 8th 2011, 08:21 AM
princeps
The fastest way to test primality of the number ?
What is the fastest way to check if this number is a prime number ?

$MM_{31}=2^{2^{31}-1}-1$
• Dec 8th 2011, 06:02 PM
wsldam
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.
• Dec 8th 2011, 10:03 PM
princeps
Re: The fastest way to test primality of the number ?
Quote:

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 ?
• Dec 9th 2011, 08:43 AM
wsldam
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
• Dec 9th 2011, 09:00 AM
princeps
Re: The fastest way to test primality of the number ?
Quote:

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