usr.bin/factor/factor.c

   1 /*
   2  * Copyright (c) 1989, 1993
   3  *      The Regents of the University of California.  All rights reserved.
   4  *
   5  * This code is derived from software contributed to Berkeley by
   6  * Landon Curt Noll.
   7  *
   8  * Redistribution and use in source and binary forms, with or without
   9  * modification, are permitted provided that the following conditions
  10  * are met:
  11  * 1. Redistributions of source code must retain the above copyright
  12  *    notice, this list of conditions and the following disclaimer.
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *    notice, this list of conditions and the following disclaimer in the
  15  *    documentation and/or other materials provided with the distribution.
  16  * 3. Neither the name of the University nor the names of its contributors
  17  *    may be used to endorse or promote products derived from this software
  18  *    without specific prior written permission.
  19  *
  20  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
  21  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  22  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  23  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
  24  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  25  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  26  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  27  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  28  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  29  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  30  * SUCH DAMAGE.
  31  */
  32
  33 #ifndef lint
  34 #include <sys/cdefs.h>
  35 #ifdef __COPYRIGHT
  36 __COPYRIGHT("@(#) Copyright (c) 1989, 1993\
  37         The Regents of the University of California.  All rights reserved.");
  38 #endif
  39 #ifdef __SCCSID
  40 __SCCSID("@(#)factor.c  8.4 (Berkeley) 5/4/95");
  41 #endif
  42 #ifdef __RCSID
  43 __RCSID("$NetBSD: factor.c,v 1.19 2009/08/12 05:54:31 dholland Exp $");
  44 #endif
  45 #ifdef __FBSDID
  46 __FBSDID("$FreeBSD$");
  47 #endif
  48 #endif /* not lint */
  49
  50 /*
  51  * factor - factor a number into primes
  52  *
  53  * By: Landon Curt Noll   chongo@toad.com,   ...!{sun,tolsoft}!hoptoad!chongo
  54  *
  55  *   chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\
  56  *
  57  * usage:
  58  *      factor [-h] [number] ...
  59  *
  60  * The form of the output is:
  61  *
  62  *      number: factor1 factor1 factor2 factor3 factor3 factor3 ...
  63  *
  64  * where factor1 <= factor2 <= factor3 <= ...
  65  *
  66  * If no args are given, the list of numbers are read from stdin.
  67  */
  68
  69 #include <ctype.h>
  70 #include <err.h>
  71 #include <errno.h>
  72 #include <inttypes.h>
  73 #include <limits.h>
  74 #include <stdbool.h>
  75 #include <stdio.h>
  76 #include <stdlib.h>
  77 #include <unistd.h>
  78
  79 #include "primes.h"
  80
  81 #ifdef HAVE_OPENSSL
  82
  83 #include <openssl/bn.h>
  84
  85 #define PRIME_CHECKS    5
  86
  87 static void     pollard_pminus1(BIGNUM *); /* print factors for big numbers */
  88
  89 #else
  90
  91 typedef ubig    BIGNUM;
  92 typedef u_long  BN_ULONG;
  93
  94 #define BN_CTX                  int
  95 #define BN_CTX_new()            NULL
  96 #define BN_new()                ((BIGNUM *)calloc(sizeof(BIGNUM), 1))
  97 #define BN_is_zero(v)           (*(v) == 0)
  98 #define BN_is_one(v)            (*(v) == 1)
  99 #define BN_mod_word(a, b)       (*(a) % (b))
 100
 101 static int      BN_dec2bn(BIGNUM **, const char *);
 102 static int      BN_hex2bn(BIGNUM **, const char *);
 103 static BN_ULONG BN_div_word(BIGNUM *, BN_ULONG);
 104 static void     BN_print_fp(FILE *, const BIGNUM *);
 105
 106 #endif
 107
 108 static void     BN_print_dec_fp(FILE *, const BIGNUM *);
 109 static void     convert_str2bn(BIGNUM **, char *);
 110 static bool     is_hex_str(char *);
 111 static void     pr_fact(BIGNUM *);      /* print factors of a value */
 112 static void     pr_print(BIGNUM *);     /* print a prime */
 113 static void     usage(void);
 114
 115 static BN_CTX   *ctx;                   /* just use a global context */
 116 static int      hflag;
 117
 118 int
 119 main(int argc, char *argv[])
 120 {
 121         BIGNUM *val;
 122         int ch;
 123         char *p, buf[LINE_MAX];         /* > max number of digits. */
 124
 125         ctx = BN_CTX_new();
 126         val = BN_new();
 127         if (val == NULL)
 128                 errx(1, "can't initialise bignum");
 129
 130         while ((ch = getopt(argc, argv, "h")) != -1)
 131                 switch (ch) {
 132                 case 'h':
 133                         hflag++;
 134                         break;
 135                 case '?':
 136                 default:
 137                         usage();
 138                 }
 139         argc -= optind;
 140         argv += optind;
 141
 142         /* No args supplied, read numbers from stdin. */
 143         if (argc == 0)
 144                 for (;;) {
 145                         if (fgets(buf, sizeof(buf), stdin) == NULL) {
 146                                 if (ferror(stdin))
 147                                         err(1, "stdin");
 148                                 exit (0);
 149                         }
 150                         for (p = buf; isblank(*p); ++p);
 151                         if (*p == '\n' || *p == '\0')
 152                                 continue;
 153                         convert_str2bn(&val, p);
 154                         pr_fact(val);
 155                 }
 156         /* Factor the arguments. */
 157         else
 158                 for (p = *argv; p != NULL; p = *++argv) {
 159                         convert_str2bn(&val, p);
 160                         pr_fact(val);
 161                 }
 162         exit(0);
 163 }
 164
 165 /*
 166  * pr_fact - print the factors of a number
 167  *
 168  * Print the factors of the number, from the lowest to the highest.
 169  * A factor will be printed multiple times if it divides the value
 170  * multiple times.
 171  *
 172  * Factors are printed with leading tabs.
 173  */
 174 static void
 175 pr_fact(BIGNUM *val)
 176 {
 177         const ubig *fact;       /* The factor found. */
 178
 179         /* Firewall - catch 0 and 1. */
 180         if (BN_is_zero(val))    /* Historical practice; 0 just exits. */
 181                 exit(0);
 182         if (BN_is_one(val)) {
 183                 printf("1: 1\n");
 184                 return;
 185         }
 186
 187         /* Factor value. */
 188
 189         if (hflag) {
 190                 fputs("0x", stdout);
 191                 BN_print_fp(stdout, val);
 192         } else
 193                 BN_print_dec_fp(stdout, val);
 194         putchar(':');
 195         for (fact = &prime[0]; !BN_is_one(val); ++fact) {
 196                 /* Look for the smallest factor. */
 197                 do {
 198                         if (BN_mod_word(val, (BN_ULONG)*fact) == 0)
 199                                 break;
 200                 } while (++fact <= pr_limit);
 201
 202                 /* Watch for primes larger than the table. */
 203                 if (fact > pr_limit) {
 204 #ifdef HAVE_OPENSSL
 205                         BIGNUM *bnfact;
 206
 207                         bnfact = BN_new();
 208                         BN_set_word(bnfact, *(fact - 1));
 209                         if (!BN_sqr(bnfact, bnfact, ctx))
 210                                 errx(1, "error in BN_sqr()");
 211                         if (BN_cmp(bnfact, val) > 0 ||
 212                             BN_is_prime_ex(val, PRIME_CHECKS, NULL, NULL) == 1)
 213                                 pr_print(val);
 214                         else
 215                                 pollard_pminus1(val);
 216 #else
 217                         pr_print(val);
 218 #endif
 219                         break;
 220                 }
 221
 222                 /* Divide factor out until none are left. */
 223                 do {
 224                         printf(hflag ? " 0x%" PRIx64 "" : " %" PRIu64 "", *fact);
 225                         BN_div_word(val, (BN_ULONG)*fact);
 226                 } while (BN_mod_word(val, (BN_ULONG)*fact) == 0);
 227
 228                 /* Let the user know we're doing something. */
 229                 fflush(stdout);
 230         }
 231         putchar('\n');
 232 }
 233
 234 static void
 235 pr_print(BIGNUM *val)
 236 {
 237         if (hflag) {
 238                 fputs(" 0x", stdout);
 239                 BN_print_fp(stdout, val);
 240         } else {
 241                 putchar(' ');
 242                 BN_print_dec_fp(stdout, val);
 243         }
 244 }
 245
 246 static void
 247 usage(void)
 248 {
 249         fprintf(stderr, "usage: factor [-h] [value ...]\n");
 250         exit(1);
 251 }
 252
 253 #ifdef HAVE_OPENSSL
 254
 255 /* pollard p-1, algorithm from Jim Gillogly, May 2000 */
 256 static void
 257 pollard_pminus1(BIGNUM *val)
 258 {
 259         BIGNUM *base, *rbase, *num, *i, *x;
 260
 261         base = BN_new();
 262         rbase = BN_new();
 263         num = BN_new();
 264         i = BN_new();
 265         x = BN_new();
 266
 267         BN_set_word(rbase, 1);
 268 newbase:
 269         if (!BN_add_word(rbase, 1))
 270                 errx(1, "error in BN_add_word()");
 271         BN_set_word(i, 2);
 272         BN_copy(base, rbase);
 273
 274         for (;;) {
 275                 BN_mod_exp(base, base, i, val, ctx);
 276                 if (BN_is_one(base))
 277                         goto newbase;
 278
 279                 BN_copy(x, base);
 280                 BN_sub_word(x, 1);
 281                 if (!BN_gcd(x, x, val, ctx))
 282                         errx(1, "error in BN_gcd()");
 283
 284                 if (!BN_is_one(x)) {
 285                         if (BN_is_prime_ex(x, PRIME_CHECKS, NULL, NULL) == 1)
 286                                 pr_print(x);
 287                         else
 288                                 pollard_pminus1(x);
 289                         fflush(stdout);
 290
 291                         BN_div(num, NULL, val, x, ctx);
 292                         if (BN_is_one(num))
 293                                 return;
 294                         if (BN_is_prime_ex(num, PRIME_CHECKS, NULL,
 295                             NULL) == 1) {
 296                                 pr_print(num);
 297                                 fflush(stdout);
 298                                 return;
 299                         }
 300                         BN_copy(val, num);
 301                 }
 302                 if (!BN_add_word(i, 1))
 303                         errx(1, "error in BN_add_word()");
 304         }
 305 }
 306
 307 /*
 308  * Sigh..  No _decimal_ output to file functions in BN.
 309  */
 310 static void
 311 BN_print_dec_fp(FILE *fp, const BIGNUM *num)
 312 {
 313         char *buf;
 314
 315         buf = BN_bn2dec(num);
 316         if (buf == NULL)
 317                 return; /* XXX do anything here? */
 318         fprintf(fp, "%s", buf);
 319         free(buf);
 320 }
 321
 322 #else
 323
 324 static void
 325 BN_print_fp(FILE *fp, const BIGNUM *num)
 326 {
 327         fprintf(fp, "%lx", (unsigned long)*num);
 328 }
 329
 330 static void
 331 BN_print_dec_fp(FILE *fp, const BIGNUM *num)
 332 {
 333         fprintf(fp, "%lu", (unsigned long)*num);
 334 }
 335
 336 static int
 337 BN_dec2bn(BIGNUM **a, const char *str)
 338 {
 339         char *p;
 340
 341         errno = 0;
 342         **a = strtoul(str, &p, 10);
 343         return (errno == 0 ? 1 : 0);    /* OpenSSL returns 0 on error! */
 344 }
 345
 346 static int
 347 BN_hex2bn(BIGNUM **a, const char *str)
 348 {
 349         char *p;
 350
 351         errno = 0;
 352         **a = strtoul(str, &p, 16);
 353         return (errno == 0 ? 1 : 0);    /* OpenSSL returns 0 on error! */
 354 }
 355
 356 static BN_ULONG
 357 BN_div_word(BIGNUM *a, BN_ULONG b)
 358 {
 359         BN_ULONG mod;
 360
 361         mod = *a % b;
 362         *a /= b;
 363         return mod;
 364 }
 365
 366 #endif
 367
 368 /*
 369  * Scan the string from left-to-right to see if the longest substring
 370  * is a valid hexadecimal number.
 371  */
 372 static bool
 373 is_hex_str(char *str)
 374 {
 375         char c, *p;
 376         bool saw_hex = false;
 377
 378         for (p = str; *p; p++) {
 379                 if (isdigit(*p))
 380                         continue;
 381                 c = tolower(*p);
 382                 if (c >= 'a' && c <= 'f') {
 383                         saw_hex = true;
 384                         continue;
 385                 }
 386                 break;  /* Not a hexadecimal digit. */
 387         }
 388         return saw_hex;
 389 }
 390
 391 /* Convert string pointed to by *str to a bignum.  */
 392 static void
 393 convert_str2bn(BIGNUM **val, char *p)
 394 {
 395         int n = 0;
 396
 397         if (*p == '+') p++;
 398         if (*p == '-')
 399                 errx(1, "negative numbers aren't permitted.");
 400         if (*p == '0') {
 401                 p++;
 402                 if (*p == 'x' || *p == 'X')
 403                         n = BN_hex2bn(val, ++p);
 404         } else {
 405                 n = is_hex_str(p) ? BN_hex2bn(val, p) : BN_dec2bn(val, p);
 406         }
 407         if (n == 0)
 408                 errx(1, "%s: illegal numeric format.", p);
 409 }