Re: Factoring integers on a classical computer

• Previous message: tchow_at_lsa.umich.edu: "Re: Factoring integers on a classical computer"
• In reply to: Phil Carmody: "Re: Factoring integers on a classical computer"
• Next in thread: Pubkeybreaker: "Re: Factoring integers on a classical computer"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]

Date: 14 Mar 2005 06:14:21 -0800

No, they do not. The best sequence of algorithms depends on the size
of the
composite.

For a composite up to 20 digits or so, I would do trial division up to
about 1000,
followed by QS. My 1.5GHz Pentium IV will do all numbers of this
size in (worst case)
about 15 milliseconds, and average case about 3 milliseconds.

For a composite up to about 50 digits, I do trial division up about
10K, followed
by a few thousand iterations of Pollard Rho, followed by ECM (up to
about 1 minute of
CPU time), followed by QS. Worst case: maybe 6 minutes. Average
case 'about'
1 minute.

For a composite up to 100 digits, I spend quite a bit more time (say
2-3 hours) with
ECM, followed by QS. Worst case: 48 hours, average case: I don't
know.

For larger composites I spend a lot more time with ECM, then use GNFS.
The
exact time with ECM depends on the size of the composite. See my paper
(with Sam Wagstaff Jr.)

"A Practical Analysis of the Elliptic Curve Factoring Algorithm" for
an analysis
of how long to run ECM being changing over to QS or GNFS.

I do not bother with P-1 at all anymore, unless I know a priori that
P-1 has a
particular factor.

However, there is no doubt that for numbers in the ~20 digit range,
both QS and
SQUFOF are faster than Pollard Rho once small factors are removed by
trial
division.

• Previous message: tchow_at_lsa.umich.edu: "Re: Factoring integers on a classical computer"
• In reply to: Phil Carmody: "Re: Factoring integers on a classical computer"
• Next in thread: Pubkeybreaker: "Re: Factoring integers on a classical computer"
• Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]