Results 1 to 5 of 5

Math Help - The fastest way to test primality ?

  1. #1
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

    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
    Last edited by princeps; December 8th 2011 at 09:32 AM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Dec 2011
    Posts
    27
    Thanks
    1

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

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

    Quote Originally Posted by wsldam View Post
    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 ?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Dec 2011
    Posts
    27
    Thanks
    1

    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
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Nov 2011
    From
    Crna Gora
    Posts
    420
    Thanks
    64

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

    Quote Originally Posted by wsldam View Post
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Wilson's Primality Test ... what ?
    Posted in the Math Forum
    Replies: 3
    Last Post: June 9th 2010, 07:44 AM
  2. Wilson's Primality Test ... what ?
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: June 9th 2010, 07:44 AM
  3. Ironing out the Lucas Primality Test proof
    Posted in the Number Theory Forum
    Replies: 10
    Last Post: April 24th 2010, 07:31 PM
  4. program problem about primality test
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: January 12th 2010, 12:02 AM
  5. The Miller-Rabin test for primality...
    Posted in the Number Theory Forum
    Replies: 0
    Last Post: December 11th 2008, 03:24 PM

Search Tags


/mathhelpforum @mathhelpforum