Date: Wed, 2 Dec 2009 19:28:55 +0000 (UTC) From: Tony Finch <fanf@FreeBSD.org> To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-8@freebsd.org Subject: svn commit: r200043 - stable/8/games/factor Message-ID: <200912021928.nB2JSte0070434@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help
Author: fanf Date: Wed Dec 2 19:28:55 2009 New Revision: 200043 URL: http://svn.freebsd.org/changeset/base/200043 Log: MFC 199815: Fix performance bugs in factor(6). Modified: stable/8/games/factor/factor.c Directory Properties: stable/8/games/factor/ (props changed) Modified: stable/8/games/factor/factor.c ============================================================================== --- stable/8/games/factor/factor.c Wed Dec 2 18:11:14 2009 (r200042) +++ stable/8/games/factor/factor.c Wed Dec 2 19:28:55 2009 (r200043) @@ -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);
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?200912021928.nB2JSte0070434>