Fix a tip: use pkg_info, not pkg_add to find out which executables

[bsdgames-darwin.git] / factor / factor.c

diff --git a/factor/factor.c b/factor/factor.c
index 23fce2b7d198d31d46f5ff1b45154aa9079581e7..2f25d7718c4d0e9c42b1b558600bcbb2b6d1a77c 100644 (file)
--- 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);