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

Trial division by 30030 = 2 * 3 * 5 * 7 * 11 * 13 Wheel is faster than trial division by primes

Expand Messages
  • Kermit Rose
    p = 10000019 q = 10000079 pq = 100000980001501L For 14 digit numbers, 13# wheel is faster than trial division by primes. It takes about 2 seconds to factor
    Message 1 of 2 , Aug 27, 2010
      p = 10000019
      q = 10000079
      pq = 100000980001501L

      For 14 digit numbers, 13# wheel is faster than trial division by primes.

      It takes about 2 seconds to factor this product of two primes, each
      near 10**7, by using relative primes to 30030.

      >>> TrialDivision(pq)
      [[10000019, 1], [10000079L, 1], 1.9279999732971191]

      Whereas, it takes about 12 seconds, 6 times longer,
      to factor the same number using only the primes.

      The times required to generate the primes outweighs the
      time used in dividing by composite integers relative prime to 30030.


      >>> TrialDivisionB(pq)
      [[10000019, 1], [10000079L, 1], 12.052999973297119]
      >>>

      Program TrialDivisionB calls on a prime generator function,
      that returns as value, the next prime integer.

      This prime generator function is based on the sieve of
      Eratosthenes, and is limited only by the computer memory
      available.

      On my machine, when I attempted to use it to "factor",
      2**61 - 1, it resulted in


      Traceback (most recent call last):
      File "<pyshell#257>", line 1, in <module>
      TrialDivisionB(z)
      File "C:\Python25\Klib2010August.py", line 1328, in TrialDivisionB
      p = Divisor.next()
      File "C:\Python25\Klib2010August.py", line 306, in Eratosthenes
      D[x] = p
      MemoryError


      Compare the time it took for wheel 300030 trial division versus
      p-1 factoring.

      >>> Factor(pq)
      [[10000019L, 1], [10000079L, 1], 0.43799996376037598]
      >>>

      >>> TrialDivision(pq)
      [[10000019, 1], [10000079L, 1], 1.9279999732971191]

      .43 * 4.5 = 1.935

      The time required for factoring this number by wheel 30030 trial
      division is approximately 4.5 times the time required to factor this
      number by p-1 algorithm.



      Kermit
    • Ali Adams
      Dear Kermit, See attached pictures please. On my 2.33GHz Intel Quad machine, it took only 0.154s to factor 100000980001501 and almost 0.000 to find the small
      Message 2 of 2 , Aug 28, 2010
        Dear Kermit,

        See attached pictures please.

        On my 2.33GHz Intel Quad machine, it took only 0.154s to factor 100000980001501
        and almost 0.000 to find the small prime to additive primes and their prime index.

        All my software are always free and open source to all (C#), downloadable from www.heliwave.com .

        PrimeFactors for both Windows and PocketPC Windows Mobile.
        BigPrimeFactors for both Windows and PocketPC Windows Mobile.
        Or the more informative version (with prime index, additive prime index and built-in calculator) inside QuranCode.
        All are copyleft :)

        Ali
        God > infinity


        ----- Original Message -----
        From: "Kermit Rose" <kermit@...>
        To: primenumbers@yahoogroups.com
        Sent: Saturday, August 28, 2010 10:33:29 AM GMT +08:00 Beijing / Chongqing / Hong Kong / Urumqi
        Subject: [PrimeNumbers] Trial division by 30030 = 2 * 3 * 5 * 7 * 11 * 13 Wheel is faster than trial division by primes







        p = 10000019
        q = 10000079
        pq = 100000980001501L

        For 14 digit numbers, 13# wheel is faster than trial division by primes.

        It takes about 2 seconds to factor this product of two primes, each
        near 10**7, by using relative primes to 30030.

        >>> TrialDivision(pq)
        [[10000019, 1], [10000079L, 1], 1.9279999732971191]

        Whereas, it takes about 12 seconds, 6 times longer,
        to factor the same number using only the primes.

        The times required to generate the primes outweighs the
        time used in dividing by composite integers relative prime to 30030.

        >>> TrialDivisionB(pq)
        [[10000019, 1], [10000079L, 1], 12.052999973297119]
        >>>

        Program TrialDivisionB calls on a prime generator function,
        that returns as value, the next prime integer.

        This prime generator function is based on the sieve of
        Eratosthenes, and is limited only by the computer memory
        available.

        On my machine, when I attempted to use it to "factor",
        2**61 - 1, it resulted in

        Traceback (most recent call last):
        File "<pyshell#257>", line 1, in <module>
        TrialDivisionB(z)
        File "C:\Python25\Klib2010August.py", line 1328, in TrialDivisionB
        p = Divisor.next()
        File "C:\Python25\Klib2010August.py", line 306, in Eratosthenes
        D[x] = p
        MemoryError

        Compare the time it took for wheel 300030 trial division versus
        p-1 factoring.

        >>> Factor(pq)
        [[10000019L, 1], [10000079L, 1], 0.43799996376037598]
        >>>

        >>> TrialDivision(pq)
        [[10000019, 1], [10000079L, 1], 1.9279999732971191]

        .43 * 4.5 = 1.935

        The time required for factoring this number by wheel 30030 trial
        division is approximately 4.5 times the time required to factor this
        number by p-1 algorithm.

        Kermit







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