bug-coreutils
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: faster algorithm for factor?


From: Paul Eggert
Subject: Re: faster algorithm for factor?
Date: 07 Jan 2004 15:34:51 -0800
User-agent: Gnus/5.09 (Gnus v5.9.0) Emacs/21.3

I'd like to second Bruno's suggestion for using gmp-ecm for "factor",
if someone wants to improve "factor"'s algorithm substantially.

I asked Peter Montgomery of CWI about this, as he's an expert in the
field and I happen to know him from way back.  Peter wrote that
Pollard Rho, ECM, and SQUFOF are all reasonable choices if the inputs
are limited to 64 bits.

It'd be nicer if "factor" wasn't limited to 64 bits, though.  Peter
wrote that when he did a comparison several years ago, Pollard Rho
beat ECM when a factor had 8 digits or fewer, but lost otherwise.  He
concluded, "As long as inputs are only 64 bits, it's a tossup between
ECM and Pollard Rho, but ECM is a definite winner if the inputs might
be larger.  Pollard Rho is a shorter program."




reply via email to

[Prev in Thread] Current Thread [Next in Thread]