X-Git-Url: https://git.cameronkatri.com/bsdgames-darwin.git/blobdiff_plain/3605b35b053f9bd5ad20e02585828040a3ce939b..4f45e985603ecf9965eca3a64c5df84b4c59c134:/factor/factor.c

diff --git a/factor/factor.c b/factor/factor.c
index 23fce2b7..2f25d771 100644
--- a/factor/factor.c
+++ b/factor/factor.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $	*/
+/*	$NetBSD: factor.c,v 1.17 2007/12/15 19:44:40 perry Exp $	*/
 
 /*
  * Copyright (c) 1989, 1993
@@ -15,11 +15,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.
  *
@@ -46,7 +42,7 @@ __COPYRIGHT("@(#) Copyright (c) 1989, 1993\n\
 #if 0
 static char sccsid[] = "@(#)factor.c	8.4 (Berkeley) 5/4/95";
 #else
-__RCSID("$NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $");
+__RCSID("$NetBSD: factor.c,v 1.17 2007/12/15 19:44:40 perry Exp $");
 #endif
 #endif /* not lint */
 
@@ -64,7 +60,7 @@ __RCSID("$NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $");
  *
  *	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.
  */
@@ -112,7 +108,7 @@ BN_CTX *ctx;				/* just use a global context */
 int	main(int, char *[]);
 void	pr_fact(BIGNUM *);		/* print factors of a value */
 void	BN_print_dec_fp(FILE *, const BIGNUM *);
-void	usage(void) __attribute__((__noreturn__));
+void	usage(void) __dead;
 #ifdef HAVE_OPENSSL
 void	pollard_pminus1(BIGNUM *);	/* print factors for big numbers */
 #else
@@ -232,7 +228,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) {
 				putchar(' ');
 				BN_print_dec_fp(stdout, val);
 			} else
@@ -281,23 +279,29 @@ usage(void)
 
 
 #ifdef HAVE_OPENSSL
-/* pollard rho, algorithm from Jim Gillogly, May 2000 */
+/* pollard p-1, algorithm from Jim Gillogly, May 2000 */
 
 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);