factor arbitrarily large numbers

* m4/gmp.m4: New file; adds cu_GMP, which detects GNU MP.
* configure.ac: Use cu_GMP.
* src/Makefile.am: Link factor against libgmp if available.
* src/factor.c: Use GNU MP if it is available.
(emit_factor, emit_ul_factor, factor_using_division,
factor_using_pollard_rho, extract_factors_multi,
sort_and_print_factors, free_factors): new functions
for the arbitrary-precision implementation, taken from an example
in GNU MP.
(factor_wheel): Renamed; was called factor.
(print_factors_single): Renamed; was called print_factors.
(print_factors): New function, chooses between the single- and
arbitrary-precision algorithms according to availability of GNU MP
and the length of the number to be factored.
(usage, main): New options --bignum and --no-bignum.
* coreutils.texi (factor invocation): Document new command-line
options for the MP implementation and update the performance
numbers to take into account the asymptotically faster algorithm.
* TODO: Remove item about factoring large primes (it's done).
* m4/gmp.m4: Add support for --without-gmp.
* NEWS: Mention the new feature.

1 files changed, 37 insertions, 21 deletions

diff --git a/doc/coreutils.texi b/doc/coreutils.texi
index 76b22e44d..c789a6cc4 100644
--- a/doc/coreutils.texi
+++ b/doc/coreutils.texi
@@ -14359,36 +14359,52 @@ factor @var{option}
 If no @var{number} is specified on the command line, @command{factor} reads
 numbers from standard input, delimited by newlines, tabs, or spaces.
 
-The only options are @option{--help} and @option{--version}.  @xref{Common
-options}.
+The @command{factor} command supports only a small number of options:
 
-The algorithm it uses is not very sophisticated, so for some inputs
-@command{factor} runs for a long time.  The hardest numbers to factor are
-the products of large primes.  Factoring the product of the two largest 32-bit
-prime numbers takes about 80 seconds of CPU time on a 1.6 GHz Athlon.
+@table @samp
+@item --help
+Print a short help on standard output, then exit without further
+processing.
 
-@example
-$ p=`echo '4294967279 * 4294967291'|bc`
-$ factor $p
-18446743979220271189: 4294967279 4294967291
-@end example
+@item --bignum
+Forces the use of the GNU MP library.   By default, @command{factor}
+selects between using GNU MP and using native operations on the basis
+of the length of the number to be factored.
 
-Similarly, it takes about 80 seconds for GNU factor (from coreutils-5.1.2)
-to ``factor'' the largest 64-bit prime:
+@item --no-bignum
+Forces the use of native operations instead of GNU MP.  This causes
+@command{factor} to fail for larger inputs.
 
-@example
-$ factor 18446744073709551557
-  18446744073709551557: 18446744073709551557
-@end example
+@item --version
+Print the program version on standard output, then exit without further
+processing.
+@end table
 
-In contrast, @command{factor} factors the largest 64-bit number in just
-over a tenth of a second:
+Factoring the product of the eighth and ninth Mersenne primes
+takes about 30 milliseconds of CPU time on a 2.2 GHz Athlon.
 
 @example
-$ factor `echo '2^64-1'|bc`
-18446744073709551615: 3 5 17 257 641 65537 6700417
+M8=`echo 2^31-1|bc` ; M9=`echo 2^61-1|bc`
+/usr/bin/time -f '%U' factor $(echo "$M8 * $M9" | bc)
+4951760154835678088235319297: 2147483647 2305843009213693951
+0.03
 @end example
 
+Similarly, factoring the eighth Fermat number @math{2^{256}+1} takes
+about 20 seconds on the same machine.
+
+Factoring large prime numbers is, in general, hard.  The Pollard Rho
+algorithm used by @command{factor} is particularly effective for
+numbers with relatively small factors.  If you wish to factor large
+numbers which do not have small factors (for example, numbers which
+are the product of two large primes), other methods are far better.
+
+If @command{factor} is built without using GNU MP, only
+single-precision arithmetic is available, and so large numbers
+(typically @math{2^{64}} and above) will not be supported.  The single-precision
+code uses an algorithm which is designed for factoring smaller
+numbers.
+
 @exitstatus