svn commit: r199815 - head/games/factor

[Tony Finch]

Author: fanf
Date: Thu Nov 26 00:38:13 2009
New Revision: 199815
URL: http://svn.freebsd.org/changeset/base/199815

Log:
  Fix a performance bug in factor(6).
  
  Check if large factor is prime before applying Pollard's algorithm;
  fixes "factor 2147483647111311".  Increase base if p-1 algorithm
  reaches 1; fixes "factor 99999999999991".
  
  Testcases from David A Bagley <bagleyd at tux.org>.
  Fixes from Joseph Myers <jsm at NetBSD.org>.
  Problem rediscovered by an attempt to factor my phone number.
  
  A few other incidental fixes: correct a couple of factually incorrect
  comments; use ident string macros; move from 4-clause to 3-clause
  BSD licence (University of California copyright).
  
  Obtained from:	NetBSD

Modified:
  head/games/factor/factor.c

Modified: head/games/factor/factor.c
==============================================================================
--- head/games/factor/factor.c	Wed Nov 25 20:50:43 2009	(r199814)
+++ head/games/factor/factor.c	Thu Nov 26 00:38:13 2009	(r199815)
@@ -13,11 +13,7 @@
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
  *    documentation and/or other materials provided with the distribution.
- * 3. All advertising materials mentioning features or use of this software
- *    must display the following acknowledgement:
- *	This product includes software developed by the University of
- *	California, Berkeley and its contributors.
- * 4. Neither the name of the University nor the names of its contributors
+ * 3. Neither the name of the University nor the names of its contributors
  *    may be used to endorse or promote products derived from this software
  *    without specific prior written permission.
  *
@@ -35,18 +31,20 @@
  */
 
 #ifndef lint
-static const char copyright[] =
-"@(#) Copyright (c) 1989, 1993\n\
-	The Regents of the University of California.  All rights reserved.\n";
-#endif /* not lint */
-
-#ifndef lint
-#if 0
-static char sccsid[] = "@(#)factor.c	8.4 (Berkeley) 5/4/95";
-__RCSID("$NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $");
+#include <sys/cdefs.h>
+#ifdef __COPYRIGHT
+__COPYRIGHT("@(#) Copyright (c) 1989, 1993\
+	The Regents of the University of California.  All rights reserved.");
+#endif
+#ifdef __SCCSID
+__SCCSID("@(#)factor.c	8.4 (Berkeley) 5/4/95");
+#endif
+#ifdef __RCSID
+__RCSID("$NetBSD: factor.c,v 1.19 2009/08/12 05:54:31 dholland Exp $");
+#endif
+#ifdef __FBSDID
+__FBSDID("$FreeBSD$");
 #endif
-static const char rcsid[] =
- "$FreeBSD$";
 #endif /* not lint */
 
 /*
@@ -63,7 +61,7 @@ static const char rcsid[] =
  *
  *	number: factor1 factor1 factor2 factor3 factor3 factor3 ...
  *
- * where factor1 < factor2 < factor3 < ...
+ * where factor1 <= factor2 <= factor3 <= ...
  *
  * If no args are given, the list of numbers are read from stdin.
  */
@@ -214,7 +212,9 @@ pr_fact(BIGNUM *val)
 			bnfact = BN_new();
 			BN_set_word(bnfact, *(fact - 1));
 			BN_sqr(bnfact, bnfact, ctx);
-			if (BN_cmp(bnfact, val) > 0)
+			if (BN_cmp(bnfact, val) > 0 ||
+			    BN_is_prime(val, PRIME_CHECKS,
+					NULL, NULL, NULL) == 1)
 				pr_print(val);
 			else
 				pollard_pminus1(val);
@@ -257,22 +257,28 @@ usage(void)
 
 #ifdef HAVE_OPENSSL
 
-/* pollard rho, algorithm from Jim Gillogly, May 2000 */
+/* pollard p-1, algorithm from Jim Gillogly, May 2000 */
 static void
 pollard_pminus1(BIGNUM *val)
 {
-	BIGNUM *base, *num, *i, *x;
+	BIGNUM *base, *rbase, *num, *i, *x;
 
 	base = BN_new();
+	rbase = BN_new();
 	num = BN_new();
 	i = BN_new();
 	x = BN_new();
 
+	BN_set_word(rbase, 1);
+newbase:
+	BN_add_word(rbase, 1);
 	BN_set_word(i, 2);
-	BN_set_word(base, 2);
+	BN_copy(base, rbase);
 
 	for (;;) {
 		BN_mod_exp(base, base, i, val, ctx);
+		if (BN_is_one(base))
+			goto newbase;
 
 		BN_copy(x, base);
 		BN_sub_word(x, 1);