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 * @(#) Copyright (c) 1989, 1993 The Regents of the University of California. All rights reserved. 33 * @(#)factor.c 8.4 (Berkeley) 5/4/95 34 * $NetBSD: factor.c,v 1.13 2002/06/18 23:07:36 simonb Exp $ 35 * $FreeBSD: src/games/factor/factor.c,v 1.9.2.2 2002/10/23 14:59:14 fanf Exp $ 36 */ 37 38 /* 39 * factor - factor a number into primes 40 * 41 * By: Landon Curt Noll chongo@toad.com, ...!{sun,tolsoft}!hoptoad!chongo 42 * 43 * chongo <for a good prime call: 391581 * 2^216193 - 1> /\oo/\ 44 * 45 * usage: 46 * factor [-h] [number] ... 47 * 48 * The form of the output is: 49 * 50 * number: factor1 factor1 factor2 factor3 factor3 factor3 ... 51 * 52 * where factor1 < factor2 < factor3 < ... 53 * 54 * If no args are given, the list of numbers are read from stdin. 55 */ 56 57 #include <ctype.h> 58 #include <err.h> 59 #include <errno.h> 60 #include <limits.h> 61 #include <stdio.h> 62 #include <stdlib.h> 63 #include <unistd.h> 64 65 #include "primes.h" 66 67 #ifdef HAVE_OPENSSL 68 #include <openssl/bn.h> 69 #define PRIME_CHECKS 5 70 static void pollard_pminus1(BIGNUM *); /* print factors for big numbers */ 71 #else 72 typedef ubig BIGNUM; 73 typedef u_long BN_ULONG; 74 75 #define BN_CTX int 76 #define BN_CTX_new() NULL 77 #define BN_new() ((BIGNUM *)calloc(sizeof(BIGNUM), 1)) 78 #define BN_is_zero(v) (*(v) == 0) 79 #define BN_is_one(v) (*(v) == 1) 80 #define BN_mod_word(a, b) (*(a) % (b)) 81 82 static int BN_dec2bn(BIGNUM **a, const char *str); 83 static int BN_hex2bn(BIGNUM **a, const char *str); 84 static BN_ULONG BN_div_word(BIGNUM *, BN_ULONG); 85 static void BN_print_fp(FILE *, const BIGNUM *); 86 #endif 87 88 static void BN_print_dec_fp(FILE *, const BIGNUM *); 89 90 static void pr_fact(BIGNUM *); /* print factors of a value */ 91 static void pr_print(BIGNUM *); /* print a prime */ 92 static void usage(void); 93 94 static BN_CTX *ctx; /* just use a global context */ 95 static int hflag; 96 97 int 98 main(int argc, char *argv[]) 99 { 100 BIGNUM *val; 101 int ch; 102 char *p, buf[LINE_MAX]; /* > max number of digits. */ 103 104 ctx = BN_CTX_new(); 105 val = BN_new(); 106 if (val == NULL) 107 errx(1, "can't initialise bignum"); 108 109 while ((ch = getopt(argc, argv, "h")) != -1) 110 switch (ch) { 111 case 'h': 112 hflag++; 113 break; 114 case '?': 115 default: 116 usage(); 117 } 118 argc -= optind; 119 argv += optind; 120 121 /* No args supplied, read numbers from stdin. */ 122 if (argc == 0) 123 for (;;) { 124 if (fgets(buf, sizeof(buf), stdin) == NULL) { 125 if (ferror(stdin)) 126 err(1, "stdin"); 127 exit (0); 128 } 129 for (p = buf; isblank(*p); ++p); 130 if (*p == '\n' || *p == '\0') 131 continue; 132 if (*p == '-') 133 errx(1, "negative numbers aren't permitted."); 134 if (BN_dec2bn(&val, buf) == 0 && 135 BN_hex2bn(&val, buf) == 0) 136 errx(1, "%s: illegal numeric format.", buf); 137 pr_fact(val); 138 } 139 /* Factor the arguments. */ 140 else 141 for (; *argv != NULL; ++argv) { 142 if (argv[0][0] == '-') 143 errx(1, "negative numbers aren't permitted."); 144 if (BN_dec2bn(&val, argv[0]) == 0 && 145 BN_hex2bn(&val, argv[0]) == 0) 146 errx(1, "%s: illegal numeric format.", argv[0]); 147 pr_fact(val); 148 } 149 exit(0); 150 } 151 152 /* 153 * pr_fact - print the factors of a number 154 * 155 * Print the factors of the number, from the lowest to the highest. 156 * A factor will be printed multiple times if it divides the value 157 * multiple times. 158 * 159 * Factors are printed with leading tabs. 160 */ 161 static void 162 pr_fact(BIGNUM *val) 163 { 164 const ubig *fact; /* The factor found. */ 165 166 /* Firewall - catch 0 and 1. */ 167 if (BN_is_zero(val)) /* Historical practice; 0 just exits. */ 168 exit(0); 169 if (BN_is_one(val)) { 170 printf("1: 1\n"); 171 return; 172 } 173 174 /* Factor value. */ 175 176 if (hflag) { 177 fputs("0x", stdout); 178 BN_print_fp(stdout, val); 179 } else 180 BN_print_dec_fp(stdout, val); 181 putchar(':'); 182 for (fact = &prime[0]; !BN_is_one(val); ++fact) { 183 /* Look for the smallest factor. */ 184 do { 185 if (BN_mod_word(val, (BN_ULONG)*fact) == 0) 186 break; 187 } while (++fact <= pr_limit); 188 189 /* Watch for primes larger than the table. */ 190 if (fact > pr_limit) { 191 #ifdef HAVE_OPENSSL 192 BIGNUM *bnfact; 193 194 bnfact = BN_new(); 195 BN_set_word(bnfact, *(fact - 1)); 196 BN_sqr(bnfact, bnfact, ctx); 197 if (BN_cmp(bnfact, val) > 0) 198 pr_print(val); 199 else 200 pollard_pminus1(val); 201 #else 202 pr_print(val); 203 #endif 204 break; 205 } 206 207 /* Divide factor out until none are left. */ 208 do { 209 printf(hflag ? " 0x%lx" : " %lu", *fact); 210 BN_div_word(val, (BN_ULONG)*fact); 211 } while (BN_mod_word(val, (BN_ULONG)*fact) == 0); 212 213 /* Let the user know we're doing something. */ 214 fflush(stdout); 215 } 216 putchar('\n'); 217 } 218 219 static void 220 pr_print(BIGNUM *val) 221 { 222 if (hflag) { 223 fputs(" 0x", stdout); 224 BN_print_fp(stdout, val); 225 } else { 226 putchar(' '); 227 BN_print_dec_fp(stdout, val); 228 } 229 } 230 231 static void 232 usage(void) 233 { 234 fprintf(stderr, "usage: factor [-h] [value ...]\n"); 235 exit(1); 236 } 237 238 #ifdef HAVE_OPENSSL 239 240 /* pollard p-1, algorithm from Jim Gillogly, May 2000 */ 241 static void 242 pollard_pminus1(BIGNUM *val) 243 { 244 BIGNUM *base, *num, *i, *x; 245 246 base = BN_new(); 247 num = BN_new(); 248 i = BN_new(); 249 x = BN_new(); 250 251 BN_set_word(i, 2); 252 BN_set_word(base, 2); 253 254 for (;;) { 255 BN_mod_exp(base, base, i, val, ctx); 256 257 BN_copy(x, base); 258 BN_sub_word(x, 1); 259 BN_gcd(x, x, val, ctx); 260 261 if (!BN_is_one(x)) { 262 if (BN_is_prime(x, PRIME_CHECKS, NULL, NULL, 263 NULL) == 1) 264 pr_print(x); 265 else 266 pollard_pminus1(x); 267 fflush(stdout); 268 269 BN_div(num, NULL, val, x, ctx); 270 if (BN_is_one(num)) 271 return; 272 if (BN_is_prime(num, PRIME_CHECKS, NULL, NULL, 273 NULL) == 1) { 274 pr_print(num); 275 fflush(stdout); 276 return; 277 } 278 BN_copy(val, num); 279 } 280 BN_add_word(i, 1); 281 } 282 } 283 284 /* 285 * Sigh.. No _decimal_ output to file functions in BN. 286 */ 287 static void 288 BN_print_dec_fp(FILE *fp, const BIGNUM *num) 289 { 290 char *buf; 291 292 buf = BN_bn2dec(num); 293 if (buf == NULL) 294 return; /* XXX do anything here? */ 295 fprintf(fp, "%s", buf); 296 free(buf); 297 } 298 299 #else 300 301 static void 302 BN_print_fp(FILE *fp, const BIGNUM *num) 303 { 304 fprintf(fp, "%lx", (unsigned long)*num); 305 } 306 307 static void 308 BN_print_dec_fp(FILE *fp, const BIGNUM *num) 309 { 310 fprintf(fp, "%lu", (unsigned long)*num); 311 } 312 313 static int 314 BN_dec2bn(BIGNUM **a, const char *str) 315 { 316 char *p; 317 318 errno = 0; 319 **a = strtoul(str, &p, 10); 320 return (errno == 0 && (*p == '\n' || *p == '\0')); 321 } 322 323 static int 324 BN_hex2bn(BIGNUM **a, const char *str) 325 { 326 char *p; 327 328 errno = 0; 329 **a = strtoul(str, &p, 16); 330 return (errno == 0 && (*p == '\n' || *p == '\0')); 331 } 332 333 static BN_ULONG 334 BN_div_word(BIGNUM *a, BN_ULONG b) 335 { 336 BN_ULONG mod; 337 338 mod = *a % b; 339 *a /= b; 340 return mod; 341 } 342 343 #endif 344