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." _______________________________________________ Bug-coreutils mailing list [EMAIL PROTECTED] http://mail.gnu.org/mailman/listinfo/bug-coreutils
