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 <[email protected]>. Fixes from Joseph Myers <[email protected]>. 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); _______________________________________________ [email protected] mailing list http://lists.freebsd.org/mailman/listinfo/svn-src-all To unsubscribe, send any mail to "[email protected]"
