- 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]

>>>

[[10000019, 1], [10000079L, 1], 1.9279999732971191]

>>> TrialDivision(pq)

.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 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]