The Tor Browser / file comparison
comparison: security/nss/lib/freebl/mpi/utils/makeprime.c
security/nss/lib/freebl/mpi/utils/makeprime.c
- changeset 0
- 6474c204b198
equal
deleted
inserted
replaced
| -1:000000000000 | 0:c22cb4c07686 |
|---|---|
| 1 /* | |
| 2 * makeprime.c | |
| 3 * | |
| 4 * A simple prime generator function (and test driver). Prints out the | |
| 5 * first prime it finds greater than or equal to the starting value. | |
| 6 * | |
| 7 * Usage: makeprime <start> | |
| 8 * | |
| 9 * This Source Code Form is subject to the terms of the Mozilla Public | |
| 10 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 11 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 12 | |
| 13 #include <stdio.h> | |
| 14 #include <stdlib.h> | |
| 15 #include <ctype.h> | |
| 16 | |
| 17 /* These two must be included for make_prime() to work */ | |
| 18 | |
| 19 #include "mpi.h" | |
| 20 #include "mpprime.h" | |
| 21 | |
| 22 /* | |
| 23 make_prime(p, nr) | |
| 24 | |
| 25 Find the smallest prime integer greater than or equal to p, where | |
| 26 primality is verified by 'nr' iterations of the Rabin-Miller | |
| 27 probabilistic primality test. The caller is responsible for | |
| 28 generating the initial value of p. | |
| 29 | |
| 30 Returns MP_OKAY if a prime has been generated, otherwise the error | |
| 31 code indicates some other problem. The value of p is clobbered; the | |
| 32 caller should keep a copy if the value is needed. | |
| 33 */ | |
| 34 mp_err make_prime(mp_int *p, int nr); | |
| 35 | |
| 36 /* The main() is not required -- it's just a test driver */ | |
| 37 int main(int argc, char *argv[]) | |
| 38 { | |
| 39 mp_int start; | |
| 40 mp_err res; | |
| 41 | |
| 42 if(argc < 2) { | |
| 43 fprintf(stderr, "Usage: %s <start-value>\n", argv[0]); | |
| 44 return 1; | |
| 45 } | |
| 46 | |
| 47 mp_init(&start); | |
| 48 if(argv[1][0] == '0' && tolower(argv[1][1]) == 'x') { | |
| 49 mp_read_radix(&start, argv[1] + 2, 16); | |
| 50 } else { | |
| 51 mp_read_radix(&start, argv[1], 10); | |
| 52 } | |
| 53 mp_abs(&start, &start); | |
| 54 | |
| 55 if((res = make_prime(&start, 5)) != MP_OKAY) { | |
| 56 fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res)); | |
| 57 mp_clear(&start); | |
| 58 | |
| 59 return 1; | |
| 60 | |
| 61 } else { | |
| 62 char *buf = malloc(mp_radix_size(&start, 10)); | |
| 63 | |
| 64 mp_todecimal(&start, buf); | |
| 65 printf("%s\n", buf); | |
| 66 free(buf); | |
| 67 | |
| 68 mp_clear(&start); | |
| 69 | |
| 70 return 0; | |
| 71 } | |
| 72 | |
| 73 } /* end main() */ | |
| 74 | |
| 75 /*------------------------------------------------------------------------*/ | |
| 76 | |
| 77 mp_err make_prime(mp_int *p, int nr) | |
| 78 { | |
| 79 mp_err res; | |
| 80 | |
| 81 if(mp_iseven(p)) { | |
| 82 mp_add_d(p, 1, p); | |
| 83 } | |
| 84 | |
| 85 do { | |
| 86 mp_digit which = prime_tab_size; | |
| 87 | |
| 88 /* First test for divisibility by a few small primes */ | |
| 89 if((res = mpp_divis_primes(p, &which)) == MP_YES) | |
| 90 continue; | |
| 91 else if(res != MP_NO) | |
| 92 goto CLEANUP; | |
| 93 | |
| 94 /* If that passes, try one iteration of Fermat's test */ | |
| 95 if((res = mpp_fermat(p, 2)) == MP_NO) | |
| 96 continue; | |
| 97 else if(res != MP_YES) | |
| 98 goto CLEANUP; | |
| 99 | |
| 100 /* If that passes, run Rabin-Miller as often as requested */ | |
| 101 if((res = mpp_pprime(p, nr)) == MP_YES) | |
| 102 break; | |
| 103 else if(res != MP_NO) | |
| 104 goto CLEANUP; | |
| 105 | |
| 106 } while((res = mp_add_d(p, 2, p)) == MP_OKAY); | |
| 107 | |
| 108 CLEANUP: | |
| 109 return res; | |
| 110 | |
| 111 } /* end make_prime() */ | |
| 112 | |
| 113 /*------------------------------------------------------------------------*/ | |
| 114 /* HERE THERE BE DRAGONS */ |
