From owner-svn-src-all@FreeBSD.ORG Thu Nov 26 00:38:14 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 DC18E1065679; Thu, 26 Nov 2009 00:38:13 +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 CA7AB8FC17; Thu, 26 Nov 2009 00:38:13 +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 nAQ0cD4A065982; Thu, 26 Nov 2009 00:38:13 GMT (envelope-from fanf@svn.freebsd.org) Received: (from fanf@localhost) by svn.freebsd.org (8.14.3/8.14.3/Submit) id nAQ0cDfO065980; Thu, 26 Nov 2009 00:38:13 GMT (envelope-from fanf@svn.freebsd.org) Message-Id: <200911260038.nAQ0cDfO065980@svn.freebsd.org> From: Tony Finch Date: Thu, 26 Nov 2009 00:38:13 +0000 (UTC) To: src-committers@freebsd.org, svn-src-all@freebsd.org, svn-src-head@freebsd.org X-SVN-Group: head MIME-Version: 1.0 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: 8bit Cc: Subject: svn commit: r199815 - head/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: Thu, 26 Nov 2009 00:38:14 -0000 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 . Fixes from Joseph Myers . 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 +#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);