Loading ...
Sorry, an error occurred while loading the content.
 

Best algorithm to check if a number is prime??

Expand Messages
  • ashok_iiit
    Hi, I am new to the prime numbers. Does anyone know what is the best deterministic algorithm that says if a number is prime. If one can guide to me with a link
    Message 1 of 4 , Sep 1, 2003
      Hi,
      I am new to the prime numbers. Does anyone know what is the best
      deterministic algorithm that says if a number is prime. If one can
      guide to me with a link to the code that implements that alogrithm,
      please do include that.
      When I heard of the largest prime number I was surprised
      how one could determine if its a prime number. Later I saw that the
      ZIMP program uses the properties of mersenne numbers. If u can guide
      to me with a link to the code that implements that alogrithm, please
      do include that.
      And are there any other numbers such as mersenne numbers
      which can help in finding largest prime number.


      ashok
    • Jud McCranie
      ... Here s a good link: http://www.utm.edu/research/primes/prove/index.html ... http://www.mersenne.org/ ... Yes - Proth primes. The test for Proth primes is
      Message 2 of 4 , Sep 1, 2003
        At 08:11 PM 9/1/2003, ashok_iiit wrote:
        >Hi,
        > I am new to the prime numbers. Does anyone know what is the best
        >deterministic algorithm that says if a number is prime. If one can
        >guide to me with a link to the code that implements that alogrithm,
        >please do include that.

        Here's a good link:
        http://www.utm.edu/research/primes/prove/index.html


        > When I heard of the largest prime number I was surprised
        >how one could determine if its a prime number.



        >Later I saw that the
        >ZIMP program uses the properties of mersenne numbers. If u can guide
        >to me with a link to the code that implements that alogrithm, please
        >do include that.

        http://www.mersenne.org/

        > And are there any other numbers such as mersenne numbers
        >which can help in finding largest prime number.

        Yes - Proth primes. The test for Proth primes is almost as efficient as
        the test for Mersenne primes, and a few years ago the largest known prime
        was a Proth prime.

        http://mathworld.wolfram.com/ProthPrime.html


        [Non-text portions of this message have been removed]
      • Paul Underwood
        ... best ... guide ... please ... For a general purpose proving algorithm see: http://www.ellipsa.net/ this program will take several months to prove a number
        Message 3 of 4 , Sep 1, 2003
          --- In primenumbers@yahoogroups.com, "ashok_iiit" <g_ashok@g...>
          wrote:
          > Hi,
          > I am new to the prime numbers. Does anyone know what is the
          best
          > deterministic algorithm that says if a number is prime. If one can
          > guide to me with a link to the code that implements that alogrithm,
          > please do include that.
          > When I heard of the largest prime number I was surprised
          > how one could determine if its a prime number. Later I saw that the
          > ZIMP program uses the properties of mersenne numbers. If u can
          guide
          > to me with a link to the code that implements that alogrithm,
          please
          > do include that.
          > And are there any other numbers such as mersenne numbers
          > which can help in finding largest prime number.

          For a general purpose proving algorithm see:

          http://www.ellipsa.net/

          this program will take several months to prove a number with say
          6,000 digits.

          However, searchers of really big numbers do much quicker tests using
          one of Proth,PRP,LLR,Prime95, or PFGW.

          Prime95.exe is used to test the primality of 2^p-1 (Mersenne Numbers,
          p prime) ( and it can be used to factor 2^n+-1. ) It uses the Lucas-
          Lemer method.

          LLR.exe ( Lucas Lemer Riesel ) tests numbers of the form k*2^n-1
          where k is fairly small ( say 10 digits I think. ) It says either a
          number is prime or it is not. ( It flies on a P4 computer. )

          PRP.exe tests numbers of of the form k*2^n+-1 but does not prove
          them -- you would have to use another program to achieve that.

          Both LLR and PRP take the output from the trial division sieving
          program called NewPGen.

          PFGW.exe is a general purpose program with many switches such as
          performing trial division etc. It can also understand NewPGen output.
          In it's factest mode it does a quick test but this does not give a
          certain answer, only a probable answer. If you can factor 33% of the
          number+-1 then PFGW can prove it prime. (If you can factor the
          number+-1 only to 30% then you can use KP but PFGW does not yet have
          this ability. )

          Proth.exe is excellent at testing numbers of the form E^(2^n)+1 where
          E is an even number -- so-called Generalized Fermat Numbers.

          I took years with many people's computers to find the current largest
          prime and it it will probablly take many more years to find the next!

          http://www.mersenne.org/prime.htm

          http://www.mersenne.org/gimps/

          http://groups.yahoo.com/group/primeform/files/ for PFGW.exe

          http://www.utm.edu/research/primes/programs/gallot/

          http://www.utm.edu/research/primes/programs/NewPGen/

          There are versions of these programs that run under both Windoze and
          Linux on PC's.

          Paul
        • Nathan Russell
          --On Tuesday, September 02, 2003 1:05 AM +0000 Paul Underwood ... However, it is much faster on numbers even a little smaller - think days for a 3000 digit
          Message 4 of 4 , Sep 1, 2003
            --On Tuesday, September 02, 2003 1:05 AM +0000 Paul Underwood
            <paulunderwood@...> wrote:

            > --- In primenumbers@yahoogroups.com, "ashok_iiit"
            > <g_ashok@g...> wrote:
            >> Hi,
            >> I am new to the prime numbers. Does anyone know what is
            >> the
            > best
            >> deterministic algorithm that says if a number is prime. If
            >> one can guide to me with a link to the code that implements
            >> that alogrithm, please do include that.
            >> When I heard of the largest prime number I was
            >> surprised how one could determine if its a prime
            >> number. Later I saw that the ZIMP program uses the
            >> properties of mersenne numbers. If u can
            > guide
            >> to me with a link to the code that implements that alogrithm,
            > please
            >> do include that.
            >> And are there any other numbers such as mersenne
            >> numbers which can help in finding largest prime
            >> number.
            >
            > For a general purpose proving algorithm see:
            >
            > http://www.ellipsa.net/
            >
            > this program will take several months to prove a number with
            > say 6,000 digits.

            However, it is much faster on numbers even a little smaller -
            think days for a 3000 digit number, and roughly an hour for a
            1000 digit number (half an hour on my XP 2000+ @ 1651)

            > However, searchers of really big numbers do much quicker tests
            > using one of Proth,PRP,LLR,Prime95, or PFGW.

            And should do so. Primo (the program linked above) uses an
            algorithm that is general, and very heavily optimized, but
            doesn't really take into account any special properties the
            number may have (aside from some numbers I've seen which are
            engineered specifically to test quickly under primo, but thats a
            different story).

            > Prime95.exe is used to test the primality of 2^p-1 (Mersenne
            > Numbers, p prime) ( and it can be used to factor 2^n+-1. ) It
            > uses the Lucas- Lemer method.

            However, all the low (taking less than a week to several months)
            numbers have been tested already for this very special form.

            > LLR.exe ( Lucas Lemer Riesel ) tests numbers of the form
            > k*2^n-1 where k is fairly small ( say 10 digits I think. ) It
            > says either a number is prime or it is not. ( It flies on a
            > P4 computer. )

            Note that this, and the programs mentioned above, are definitive
            tests - and their results can thus be submitted to e.g. Prof
            Caldwell's database. Some other tests are probabilistic - they
            say a number is "very likely" prime. Generally, "very likely"
            means much more likely than, for example, the event that I won't
            die of a sudden brain aneurysm before I finish typing this
            email. There's no real doubt about primality - but you
            shouldn't submit numbers that haven't been proven to be prime,
            as a matter of ethics.

            > PRP.exe tests numbers of of the form k*2^n+-1 but does not
            > prove them -- you would have to use another program to
            > achieve that.

            Also, it is now used somewhat less than PFGW. However, I
            believe PRP has optimizations not yet available in PFGW, since
            PRP is written by the same person who maintains the excellent
            multiplication libraries used by both programs. This should not
            make a huge difference though.

            > Both LLR and PRP take the output from the trial division
            > sieving program called NewPGen.

            Which, like any of the several other sieving programs available
            from this list's files area, may have rules for academic credit
            which should be followed.

            > PFGW.exe is a general purpose program with many switches such
            > as performing trial division etc. It can also understand
            > NewPGen output. In it's factest mode it does a quick test but
            > this does not give a certain answer, only a probable answer.
            > If you can factor 33% of the number+-1 then PFGW can prove it
            > prime. (If you can factor the number+-1 only to 30% then you
            > can use KP but PFGW does not yet have this ability. )

            If you're in that situation, you might want to ask for help on
            this list. I don't understand the theory of a KP proof in much
            detail.

            > Proth.exe is excellent at testing numbers of the form
            > E^(2^n)+1 where E is an even number -- so-called Generalized
            > Fermat Numbers.

            And in fact it is one of the two fastest programs in the world
            if you just want to find a large prime - the other being Prime95
            and its ports. However, Generalized Fermat Numbers are
            available in sizes which can be tested in minutes to hours - the
            same is not true of untested Mersenne numbers for Prime95.

            Question for the list - is Prime95 with the new Athlon
            improvements in the beta versions now slightly better than
            Proth? I don't use Proth much anymore.

            > I took years with many people's computers to find the current
            > largest prime and it it will probablly take many more years
            > to find the next!

            However, top 5000 primes can be found in a few hours.

            > http://www.mersenne.org/prime.htm
            >
            > http://www.mersenne.org/gimps/
            >
            > http://groups.yahoo.com/group/primeform/files/ for PFGW.exe
            >
            > http://www.utm.edu/research/primes/programs/gallot/
            >
            > http://www.utm.edu/research/primes/programs/NewPGen/
            >
            > There are versions of these programs that run under both
            > Windoze and Linux on PC's.

            However, in the case of Proth and Primo, you will need to use
            WINE or a similiar utility. I haven't seen a loss of efficienty
            using such utilities.

            Could this be the beginning of a FAQ?

            Nathan
          Your message has been successfully submitted and would be delivered to recipients shortly.