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