GNU bug report logs - #42269
Remove non-GMP code from coreutils factor.c

Previous Next

Full log

Message #24 received at submit <at> debbugs.gnu.org (full text, mbox):

From: tg <at> gmplib.org (Torbjörn Granlund)
To: nisse <at> lysator.liu.se (Niels Möller)
Cc: James Youngman <jay <at> gnu.org>,
 Pádraig Brady <P <at> draigBrady.com>,
 Paul Eggert <eggert <at> cs.ucla.edu>, Coreutils bugs <bug-coreutils <at> gnu.org>,
 Jim Meyering <jim <at> meyering.net>
Subject: Re: Remove non-GMP code from coreutils factor.c
Date: Wed, 08 Jul 2020 23:46:38 +0200

nisse <at> lysator.liu.se (Niels Möller) writes:

  I'm really not that familiar with state of the art factoring, but I'd
  guess pollard rho is a bad algorithm choice for that range, and one
  ought to use, e.g., some variant of the quadratic sieve.

Let me modify that statement somewhat.

Pollars rho is suitable for finding small factors of any size
composites.  Small here might mean about < 2^64.

Any factoring effort should start with trial division, then some rounds
of Pollard rho, then perhaps some EC rounds.  Only after that and when a
remaining cofactor is non-prime, QS is to be rolled out.

That could sound like the GMP code of coreutils factor is great for
factoring really large numbers.  It is, but only for smooth huge
numbers.

If we ever get crazy enough to consider QS for coreutils factor, its
current GMP Pollard rho code would become part of a general factoring
engine for numbers > 2^127.

-- 
Torbjörn
Please encrypt, key id 0xC8601622

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.