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 9225eb94a1d2ce4f1452761615c68ca537219999..2f25d7718c4d0e9c42b1b558600bcbb2b6d1a77c 100644 (file)
--- 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);