diff options
| -rw-r--r-- | games/factor/factor.c | 48 |
1 files changed, 27 insertions, 21 deletions
diff --git a/games/factor/factor.c b/games/factor/factor.c index e3aa90c..1444d0b 100644 --- a/games/factor/factor.c +++ b/games/factor/factor.c @@ -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); |
