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

Expand Messages
• 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
• 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,

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.
All are copyleft :)

Ali
God > infinity

----- Original Message -----
From: "Kermit Rose" <kermit@...>
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.