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

Re: [PrimeNumbers] trial division

Expand Messages
  • Jens Kruse Andersen
    ... I don t have any commercial factoring program but here is the free PrimeForm/GW: C: Users Jens pfgw -f -e2000000000 -q1986619529684749961 PFGW Version
    Message 1 of 4 , May 1, 2007
    • 0 Attachment
      aldrich617 wrote:

      > Trial division can be an easy and predictable way to verify
      > primality if the number is not too large. I am hoping that
      > someone who has a commercial factoring program will check
      > the time it takes to verify that 1986619529684749961 is prime.
      > My little homemade program takes about 160 seconds on a
      > pentium3 866 Dell. This prime is only special in that it
      > appears on a proved +1 mod 10 sequence. If this were not known
      > it would take my program 640 seconds to resolve.

      I don't have any commercial factoring program but here is the free
      PrimeForm/GW:

      C:\Users\Jens>pfgw -f -e2000000000 -q1986619529684749961
      PFGW Version 1.2.0 for Windows [FFT v23.8]

      trial factoring to 1409474912
      1986619529684749961 factors prime!: 1986619529684749961

      That took 7 seconds on one core of a 2.4 GHz Core 2 Duo.

      The free PARI/GP proves primality in a small fraction of a second without
      using trial factoring:

      ? isprime(1986619529684749961)
      time = 0 ms.
      %209 = 1
      ? for(i=1,5000,isprime(1986619529684749961))
      time = 860 ms.

      That is 860 ms / 5000 = 0.00017 second for one proof on a 2.4 GHz core.

      Both programs are for arbitrary number sizes.
      Similar programs optimized for 64-bit numbers would probably be faster.

      --
      Jens Kruse Andersen
    • Alan Eliasen
      ... Is your program dividing by all numbers up to sqrt[n] or just the prime ones? Admittedly, it s a lot more complicated and can be quite memory-intensive to
      Message 2 of 4 , May 1, 2007
      • 0 Attachment
        aldrich617 wrote:
        > Trial division can be an easy and predictable way to verify
        > primality if the number is not too large. I am hoping that
        > someone who has a commercial factoring program will check
        > the time it takes to verify that 1986619529684749961 is prime.
        > My little homemade program takes about 160 seconds on a
        > pentium3 866 Dell. This prime is only special in that it
        > appears on a proved +1 mod 10 sequence. If this were not known
        > it would take my program 640 seconds to resolve.

        Is your program dividing by all numbers up to sqrt[n] or just the
        prime ones? Admittedly, it's a lot more complicated and can be quite
        memory-intensive to build a naive sieve of the primes up to about 1.4
        billion in this case, so I'm guessing you might just divide by all of
        the smaller numbers (at least the odd ones) up to sqrt[n]? Or do you
        have a cleverer sieve to generate all the primes?

        As you may know, as a next step, you might consider doing a test like
        the Rabin-Miller test on your numbers, which can very rapidly give you
        at least a probabilistic result that a number is prime or not. If the
        Rabin-Miller test says that a number is composite, it's definitely
        composite. If it says that it's prime, it's very likely prime, and it's
        easy to run enough rounds of the test that the probability of it
        returning a false result are far, far less than the probability of your
        hardware failing during the test and returning an incorrect result, or
        even you testing billions of numbers each second continuously for the
        life of the universe, and never getting a wrong answer. It will also be
        immensely faster than trial division for numbers of this size (although
        your tests may also consist of trial division for small primes, which,
        as a practical matter, tends to reduce the size of large numbers
        somewhat rapidly when factoring.) In addition, the Rabin-Miller test
        tends to become more and more reliable as the numbers get larger,
        greatly improving the probability that a number is indeed prime even if
        tested against a smaller number of bases.

        In addition, it is known for numbers up to the smaller number
        341550071728321 which bases you need to test against in a Rabin-Miller
        test to *prove* primality, although this limit is not large enough for
        the numbers you're working with. Does anyone know if this limit has
        been improved?

        What would those here recommend as a somewhat efficient and, perhaps
        more importantly, easy-to-implement algorithm for *proving* primality
        for numbers of a general form?

        --
        Alan Eliasen | "Furious activity is no substitute
        eliasen@... | for understanding."
        http://futureboy.us/ | --H.H. Williams
      • Josechu Gonzalez
        The small Darío Alpern s applet in this page: http://www.alpertron.com.ar/ECM.HTM also certifies it is a prime in a fraction of second. (On a 1.13 GHz
        Message 3 of 4 , May 2, 2007
        • 0 Attachment
          The small Darío Alpern's applet in this page:

          http://www.alpertron.com.ar/ECM.HTM

          also certifies it is a prime in a fraction of second. (On a 1.13 GHz
          Pentium.)


          Josechu



          On 5/2/07, aldrich617 <aldrich617@...> wrote:
          >
          > Trial division can be an easy and predictable way to verify
          > primality if the number is not too large. I am hoping that
          > someone who has a commercial factoring program will check
          > the time it takes to verify that 1986619529684749961 is prime.
          > My little homemade program takes about 160 seconds on a
          > pentium3 866 Dell. This prime is only special in that it
          > appears on a proved +1 mod 10 sequence. If this were not known
          > it would take my program 640 seconds to resolve.
          >
          > aldrich
          >
          >
          >


          [Non-text portions of this message have been removed]
        Your message has been successfully submitted and would be delivered to recipients shortly.