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

trial division

Expand Messages
  • aldrich617
    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
    Message 1 of 4 , May 1, 2007
      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
    • 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 2 of 4 , May 1, 2007
        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 3 of 4 , May 1, 2007
          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 4 of 4 , May 2, 2007
            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.