## Re: [PrimeNumbers] building factoring routines

Expand Messages
• ... 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 1 of 4 , Jun 3, 2006
• 0 Attachment
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 2 of 4 , Jun 3, 2006
• 0 Attachment
--- 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.