From owner-svn-src-all@FreeBSD.ORG Wed Dec 2 19:28:56 2009 Return-Path: Delivered-To: svn-src-all@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [IPv6:2001:4f8:fff6::34]) by hub.freebsd.org (Postfix) with ESMTP id 111E21065695; Wed, 2 Dec 2009 19:28:56 +0000 (UTC) (envelope-from fanf@FreeBSD.org) Received: from svn.freebsd.org (svn.freebsd.org [IPv6:2001:4f8:fff6::2c]) by mx1.freebsd.org (Postfix) with ESMTP id F2E818FC26; Wed, 2 Dec 2009 19:28:55 +0000 (UTC) Received: from svn.freebsd.org (localhost [127.0.0.1]) by svn.freebsd.org (8.14.3/8.14.3) with ESMTP id nB2JStP9070436; Wed, 2 Dec 2009 19:28:55 GMT (envelope-from fanf@svn.freebsd.org) Received: (from fanf@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id nB2JSte0070434; Wed, 2 Dec 2009 19:28:55 GMT (envelope-from fanf@svn.freebsd.org) Message-Id: <200912021928.nB2JSte0070434@svn.freebsd.org> From: Tony Finch Date: Wed, 2 Dec 2009 19:28:55 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-stable@freebsd.org, svn-src-stable-8@freebsd.org X-SVN-Group: stable-8 MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r200043 - stable/8/games/factor X-BeenThere: svn-src-all@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: "SVN commit messages for the entire src tree \(except for " user" and " projects" \)" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 02 Dec 2009 19:28:56 -0000 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 +#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);