X-Git-Url: https://git.cameronkatri.com/bsdgames-darwin.git/blobdiff_plain/94b5353c71e7246077d468afe68d51ce85fc213d..4842cad26009ebcd3c2e39d529d0f4908599a7b5:/factor/factor.c diff --git a/factor/factor.c b/factor/factor.c index c578a747..23fce2b7 100644 --- a/factor/factor.c +++ b/factor/factor.c @@ -1,4 +1,4 @@ -/* $NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $ */ +/* $NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $ */ /* * Copyright (c) 1989, 1993 @@ -36,17 +36,17 @@ * SUCH DAMAGE. */ +#include #ifndef lint -static char copyright[] = -"@(#) Copyright (c) 1989, 1993\n\ - The Regents of the University of California. All rights reserved.\n"; +__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.3 (Berkeley) 3/30/94"; +static char sccsid[] = "@(#)factor.c 8.4 (Berkeley) 5/4/95"; #else -static char rcsid[] = "$NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $"; +__RCSID("$NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $"); #endif #endif /* not lint */ @@ -69,37 +69,87 @@ static char rcsid[] = "$NetBSD: factor.c,v 1.5 1995/03/23 08:28:07 cgd Exp $"; * If no args are given, the list of numbers are read from stdin. */ -#include #include +#include #include #include #include #include +#include + +#ifdef HAVE_OPENSSL +#include +#else +typedef long BIGNUM; +typedef u_long BN_ULONG; +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 #include "primes.h" /* * prime[i] is the (i-1)th prime. * - * We are able to sieve 2^32-1 because this byte table yields all primes + * We are able to sieve 2^32-1 because this byte table yields all primes * up to 65537 and 65537^2 > 2^32-1. */ -extern ubig prime[]; -extern ubig *pr_limit; /* largest prime in the prime array */ +extern const ubig prime[]; +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 BN_print_dec_fp(FILE *, const BIGNUM *); +void usage(void) __attribute__((__noreturn__)); +#ifdef HAVE_OPENSSL +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; -void pr_fact __P((ubig)); /* print factors of a value */ -void usage __P((void)); + errno = 0; + **a = strtoul(str, &p, 10); + if (errno) + err(1, "%s", str); + return (*p == '\n' || *p == '\0'); +} +#endif int -main(argc, argv) - int argc; - char *argv[]; +main(int argc, char *argv[]) { - ubig val; + BIGNUM *val; int ch; - char *p, buf[100]; /* > max number of digits. */ + char *p, buf[LINE_MAX]; /* > max number of digits. */ - while ((ch = getopt(argc, argv, "")) != EOF) +#ifdef HAVE_OPENSSL + ctx = BN_CTX_new(); +#endif + val = BN_new(); + if (val == NULL) + errx(1, "can't initialise bignum"); + + while ((ch = getopt(argc, argv, "")) != -1) switch (ch) { case '?': default: @@ -121,12 +171,8 @@ main(argc, argv) continue; if (*p == '-') errx(1, "negative numbers aren't permitted."); - errno = 0; - val = strtoul(buf, &p, 10); - if (errno) - err(1, "%s", buf); - if (*p != '\n') - errx(1, "%s: illegal numeric format.", buf); + if (BN_dec2bn(&val, buf) == 0) + errx(1, "%s: illegal numeric format.", argv[0]); pr_fact(val); } /* Factor the arguments. */ @@ -134,11 +180,7 @@ main(argc, argv) for (; *argv != NULL; ++argv) { if (argv[0][0] == '-') errx(1, "negative numbers aren't permitted."); - errno = 0; - val = strtoul(argv[0], &p, 10); - if (errno) - err(1, "%s", argv[0]); - if (*p != '\0') + if (BN_dec2bn(&val, argv[0]) == 0) errx(1, "%s: illegal numeric format.", argv[0]); pr_fact(val); } @@ -159,49 +201,152 @@ main(argc, argv) * Factors are printed with leading tabs. */ void -pr_fact(val) - ubig val; /* Factor this value. */ +pr_fact(BIGNUM *val) { - ubig *fact; /* The factor found. */ + const ubig *fact; /* The factor found. */ /* Firewall - catch 0 and 1. */ - if (val == 0) /* Historical practice; 0 just exits. */ + if (BN_is_zero(val)) /* Historical practice; 0 just exits. */ exit(0); - if (val == 1) { - (void)printf("1: 1\n"); + if (BN_is_one(val)) { + printf("1: 1\n"); return; } /* Factor value. */ - (void)printf("%lu:", val); - for (fact = &prime[0]; val > 1; ++fact) { + + BN_print_dec_fp(stdout, val); + putchar(':'); + for (fact = &prime[0]; !BN_is_one(val); ++fact) { /* Look for the smallest factor. */ do { - if (val % (long)*fact == 0) + if (BN_mod_word(val, (BN_ULONG)*fact) == 0) break; } while (++fact <= pr_limit); /* Watch for primes larger than the table. */ if (fact > pr_limit) { - (void)printf(" %lu", val); +#ifdef HAVE_OPENSSL + BIGNUM *bnfact; + + bnfact = BN_new(); + BN_set_word(bnfact, *(fact - 1)); + BN_sqr(bnfact, bnfact, ctx); + if (BN_cmp(bnfact, val) > 0) { + putchar(' '); + BN_print_dec_fp(stdout, val); + } else + pollard_pminus1(val); +#else + printf(" %s", BN_bn2dec(val)); +#endif break; } /* Divide factor out until none are left. */ do { - (void)printf(" %lu", *fact); - val /= (long)*fact; - } while ((val % (long)*fact) == 0); + printf(" %lu", *fact); + BN_div_word(val, (BN_ULONG)*fact); + } while (BN_mod_word(val, (BN_ULONG)*fact) == 0); /* Let the user know we're doing something. */ - (void)fflush(stdout); + fflush(stdout); } - (void)putchar('\n'); + putchar('\n'); +} + +/* + * Sigh.. No _decimal_ output to file functions in BN. + */ +void +BN_print_dec_fp(FILE *fp, const BIGNUM *num) +{ + char *buf; + + buf = BN_bn2dec(num); + if (buf == NULL) + return; /* XXX do anything here? */ + fprintf(fp, buf); + free(buf); } void -usage() +usage(void) { - (void)fprintf(stderr, "usage: factor [value ...]\n"); + fprintf(stderr, "usage: factor [value ...]\n"); exit (0); } + + + + +#ifdef HAVE_OPENSSL +/* pollard rho, algorithm from Jim Gillogly, May 2000 */ + +void +pollard_pminus1(BIGNUM *val) +{ + BIGNUM *base, *num, *i, *x; + + base = BN_new(); + num = BN_new(); + i = BN_new(); + x = BN_new(); + + BN_set_word(i, 2); + BN_set_word(base, 2); + + for (;;) { + BN_mod_exp(base, base, i, val, ctx); + + BN_copy(x, base); + BN_sub_word(x, 1); + BN_gcd(x, x, val, ctx); + + if (!BN_is_one(x)) { + if (BN_is_prime(x, PRIME_CHECKS, NULL, NULL, + NULL) == 1) { + putchar(' '); + BN_print_dec_fp(stdout, x); + } else + pollard_pminus1(x); + fflush(stdout); + + BN_div(num, NULL, val, x, ctx); + if (BN_is_one(num)) + return; + if (BN_is_prime(num, PRIME_CHECKS, NULL, NULL, + NULL) == 1) { + putchar(' '); + BN_print_dec_fp(stdout, num); + fflush(stdout); + return; + } + BN_copy(val, num); + } + BN_add_word(i, 1); + } +} +#else +char * +BN_bn2dec(const BIGNUM *val) +{ + char *buf; + + buf = malloc(100); + if (!buf) + return buf; + snprintf(buf, 100, "%ld", (long)*val); + return buf; +} + +BN_ULONG +BN_div_word(BIGNUM *a, BN_ULONG b) +{ + BN_ULONG mod; + + mod = *a % b; + *a /= b; + return mod; +} +#endif