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

diff --git a/factor/factor.c b/factor/factor.c
index 9225eb94..2f25d771 100644
--- a/factor/factor.c
+++ b/factor/factor.c
@@ -1,4 +1,4 @@
-/*	$NetBSD: factor.c,v 1.11 2002/06/16 22:24:01 itojun 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.11 2002/06/16 22:24:01 itojun 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.11 2002/06/16 22:24:01 itojun 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.
  */
@@ -82,10 +78,13 @@ __RCSID("$NetBSD: factor.c,v 1.11 2002/06/16 22:24:01 itojun Exp $");
 #else
 typedef long	BIGNUM;
 typedef u_long	BN_ULONG;
-#define BN_new()	((BIGNUM *)calloc(sizeof(BIGNUM), 1))
-#define BN_dec2bn(pp, str)	(**(pp) = atol(str))
-#define BN_is_zero(v)	(*(v) == 0)
-#define BN_is_one(v)	(*(v) == 1)
+int	BN_dec2bn(BIGNUM **a, const char *str);
+#define BN_new()		((BIGNUM *)calloc(sizeof(BIGNUM), 1))
+#define BN_is_zero(v)		(*(v) == 0)
+#define BN_is_one(v)		(*(v) == 1)
+#define BN_new()		((BIGNUM *)calloc(sizeof(BIGNUM), 1))
+#define BN_is_zero(v)		(*(v) == 0)
+#define BN_is_one(v)		(*(v) == 1)
 #define BN_mod_word(a, b)	(*(a) % (b))
 #endif
 
@@ -102,17 +101,36 @@ extern const ubig *pr_limit;		/* largest prime in the prime array */
 
 #define	PRIME_CHECKS	5
 
+#ifdef HAVE_OPENSSL 
+BN_CTX *ctx;				/* just use a global context */
+#endif
+
 int	main(int, char *[]);
-void	pr_fact(BIGNUM *);			/* print factors of a value */
+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 */
+void	pollard_pminus1(BIGNUM *);	/* print factors for big numbers */
 #else
 char	*BN_bn2dec(const BIGNUM *);
 BN_ULONG BN_div_word(BIGNUM *, BN_ULONG);
 #endif
 
+
+#ifndef HAVE_OPENSSL
+int
+BN_dec2bn(BIGNUM **a, const char *str)
+{
+	char *p;
+
+	errno = 0;
+	**a = strtoul(str, &p, 10);
+	if (errno)
+		err(1, "%s", str);
+	return (*p == '\n' || *p == '\0');
+}
+#endif
+
 int
 main(int argc, char *argv[])
 {
@@ -120,6 +138,9 @@ main(int argc, char *argv[])
 	int ch;
 	char *p, buf[LINE_MAX];		/* > max number of digits. */
 
+#ifdef HAVE_OPENSSL 
+	ctx = BN_CTX_new();
+#endif
 	val = BN_new();
 	if (val == NULL)
 		errx(1, "can't initialise bignum");
@@ -202,9 +223,20 @@ pr_fact(BIGNUM *val)
 		/* Watch for primes larger than the table. */
 		if (fact > pr_limit) {
 #ifdef HAVE_OPENSSL
-			pollard_pminus1(val);
+			BIGNUM *bnfact;
+
+			bnfact = BN_new();
+			BN_set_word(bnfact, *(fact - 1));
+			BN_sqr(bnfact, bnfact, ctx);
+			if (BN_cmp(bnfact, val) > 0
+			    || BN_is_prime(val, PRIME_CHECKS, NULL, NULL,
+					   NULL) == 1) {
+				putchar(' ');
+				BN_print_dec_fp(stdout, val);
+			} else
+				pollard_pminus1(val);
 #else
-			(void)printf(" %s", BN_bn2dec(val));
+			printf(" %s", BN_bn2dec(val));
 #endif
 			break;
 		}
@@ -247,26 +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;
-	BN_CTX *ctx;
-
-	ctx = BN_CTX_new();
+	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);