Asking again a question in a different way
- I'm evolving a set of factor algorithms
and so far have used the criterion that
the algorithm is fast enough for integers of a given number of digits
if it finds the factors as fast as it can print them out.
So my question, re-worded is:
For those of you who factor large integers regularly,
what's the largest number of digits for which your factor routines
will find the factors as quickly as they can be printed out?
Kermit < kermit@... >
- --- Kermit Rose <kermit@...> wrote:
> I'm evolving a set of factor algorithmsIt's still ill-formed.
> and so far have used the criterion that
> the algorithm is fast enough for integers of a given number of digits
> if it finds the factors as fast as it can print them out.
> So my question, re-worded is:
> For those of you who factor large integers regularly,
> what's the largest number of digits for which your factor routines
> will find the factors as quickly as they can be printed out?
There are two parameters which decide how quickly a factor-finding
algorithm will find a factor. The first is the size of the number
you are trying to factor. The second is the size of the factor that
it will find.
So the size that can be found almost instantly depends on the size of the
For large composites (tens to hundreds of thousand digits), I'd guess that even
2-4 digits would begin to have a noticable lag.
Moderate size numbers (thousands of digits), 4-5 digits.
Smallish numbers (hundreds of digits) 5-6 digits.
Tiny numbers (tens of digits) 6-7 digits.
But remember, factors that are so small that you can find them almost instantly
just aren't interesting for that very reason. If you can find 16-digit factors
almost instantly, then perhaps you've got something that will interest people.
() 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