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