building factoring routines

Expand Messages
• I m slowly building my factoring subroutines. I can factor numbers in the 12 digit range pretty quickly now, but it still took over a minute to find a factor
Message 1 of 4 , Jun 2 5:47 PM
I'm slowly building my factoring subroutines.

I can factor numbers in the 12 digit range pretty quickly now, but it still
took over a minute to find a factor of 10^15 + 3.

>>> for z in range(10**15+1,10**15+15):
w = getordfac(z,m)
print z,w

1000000000000001 1001
1000000000000002 2
1000000000000003 67103479
1000000000000004 2
1000000000000005 255
1000000000000006 2
1000000000000007 2773
1000000000000008 2
1000000000000009 179
1000000000000010 2
1000000000000011 3477
1000000000000012 2
1000000000000013 1091
1000000000000014 2

Kermit < kermit@... >

[Non-text portions of this message have been removed]
• I can factor numbers in the 12 digit range pretty quickly now, but it still took over a minute to find a factor of 10^15 + 3. Why so long? It takes me 24 ms
Message 2 of 4 , Jun 3 6:42 AM
I can factor numbers in the 12 digit range pretty quickly now, but it still
took over a minute to find a factor of 10^15 + 3.

Why so long? It takes me 24 ms (Pollard Rho, HIT library, PIII 700 MHz)

[Non-text portions of this message have been removed]
• ... For numbers in that range (fewer than 64 bits), I wouldn t use HIT or any other such package. Just use the native data types. Also, Shank s method is
Message 3 of 4 , Jun 3 3:19 PM
At 09:42 AM 6/3/2006, hecht wrote:
>I can factor numbers in the 12 digit range pretty quickly now, but it still
>took over a minute to find a factor of 10^15 + 3.
>
>Why so long? It takes me 24 ms (Pollard Rho, HIT library, PIII 700 MHz)

For numbers in that range (fewer than 64 bits), I wouldn't use HIT or any
other such package. Just use the native data types. Also, Shank's method
is probably better for that application than Pollard's method. My program
on a 2.4 GHz factors 10^15+3 in 0.01 second.
• ... Now I ve decomissioned my PPro/200, I don t have a machine slow enough to measure my native double reimplimantation of Lenstra s (LIP) version of Shanks
Message 4 of 4 , Jun 3 4:32 PM
--- Jud McCranie <j.mccranie@...> wrote:
> At 09:42 AM 6/3/2006, hecht wrote:
> >I can factor numbers in the 12 digit range pretty quickly now, but it still
> >took over a minute to find a factor of 10^15 + 3.
> >
> >Why so long? It takes me 24 ms (Pollard Rho, HIT library, PIII 700 MHz)
>
> For numbers in that range (fewer than 64 bits), I wouldn't use HIT or any
> other such package. Just use the native data types. Also, Shank's method
> is probably better for that application than Pollard's method. My program
> on a 2.4 GHz factors 10^15+3 in 0.01 second.

Now I've decomissioned my PPro/200, I don't have a machine slow
enough to measure my native double reimplimantation of Lenstra's
(LIP) version of Shanks' SQUFOF on that number! (And I gave away
my ARM dev board yesterday - that would have been really slow.)

However, I found two Sparcs, with their notoriously underpowered FPUs,
in America, and indeed they are slow enough for it to be measurable:
SunUltra5 - 0.010s
(no idea what clock speed they may be).

Paul - may I post the code? It's Lenstra's copyright, but you seem
to be the guardian of it presently?

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

__________________________________________________
Do You Yahoo!?
Tired of spam? Yahoo! Mail has the best spam protection around
http://mail.yahoo.com
Your message has been successfully submitted and would be delivered to recipients shortly.