1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/security/nss/lib/freebl/mpi/utils/makeprime.c Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,114 @@
1.4 +/*
1.5 + * makeprime.c
1.6 + *
1.7 + * A simple prime generator function (and test driver). Prints out the
1.8 + * first prime it finds greater than or equal to the starting value.
1.9 + *
1.10 + * Usage: makeprime <start>
1.11 + *
1.12 + * This Source Code Form is subject to the terms of the Mozilla Public
1.13 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.14 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.15 +
1.16 +#include <stdio.h>
1.17 +#include <stdlib.h>
1.18 +#include <ctype.h>
1.19 +
1.20 +/* These two must be included for make_prime() to work */
1.21 +
1.22 +#include "mpi.h"
1.23 +#include "mpprime.h"
1.24 +
1.25 +/*
1.26 + make_prime(p, nr)
1.27 +
1.28 + Find the smallest prime integer greater than or equal to p, where
1.29 + primality is verified by 'nr' iterations of the Rabin-Miller
1.30 + probabilistic primality test. The caller is responsible for
1.31 + generating the initial value of p.
1.32 +
1.33 + Returns MP_OKAY if a prime has been generated, otherwise the error
1.34 + code indicates some other problem. The value of p is clobbered; the
1.35 + caller should keep a copy if the value is needed.
1.36 + */
1.37 +mp_err make_prime(mp_int *p, int nr);
1.38 +
1.39 +/* The main() is not required -- it's just a test driver */
1.40 +int main(int argc, char *argv[])
1.41 +{
1.42 + mp_int start;
1.43 + mp_err res;
1.44 +
1.45 + if(argc < 2) {
1.46 + fprintf(stderr, "Usage: %s <start-value>\n", argv[0]);
1.47 + return 1;
1.48 + }
1.49 +
1.50 + mp_init(&start);
1.51 + if(argv[1][0] == '0' && tolower(argv[1][1]) == 'x') {
1.52 + mp_read_radix(&start, argv[1] + 2, 16);
1.53 + } else {
1.54 + mp_read_radix(&start, argv[1], 10);
1.55 + }
1.56 + mp_abs(&start, &start);
1.57 +
1.58 + if((res = make_prime(&start, 5)) != MP_OKAY) {
1.59 + fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
1.60 + mp_clear(&start);
1.61 +
1.62 + return 1;
1.63 +
1.64 + } else {
1.65 + char *buf = malloc(mp_radix_size(&start, 10));
1.66 +
1.67 + mp_todecimal(&start, buf);
1.68 + printf("%s\n", buf);
1.69 + free(buf);
1.70 +
1.71 + mp_clear(&start);
1.72 +
1.73 + return 0;
1.74 + }
1.75 +
1.76 +} /* end main() */
1.77 +
1.78 +/*------------------------------------------------------------------------*/
1.79 +
1.80 +mp_err make_prime(mp_int *p, int nr)
1.81 +{
1.82 + mp_err res;
1.83 +
1.84 + if(mp_iseven(p)) {
1.85 + mp_add_d(p, 1, p);
1.86 + }
1.87 +
1.88 + do {
1.89 + mp_digit which = prime_tab_size;
1.90 +
1.91 + /* First test for divisibility by a few small primes */
1.92 + if((res = mpp_divis_primes(p, &which)) == MP_YES)
1.93 + continue;
1.94 + else if(res != MP_NO)
1.95 + goto CLEANUP;
1.96 +
1.97 + /* If that passes, try one iteration of Fermat's test */
1.98 + if((res = mpp_fermat(p, 2)) == MP_NO)
1.99 + continue;
1.100 + else if(res != MP_YES)
1.101 + goto CLEANUP;
1.102 +
1.103 + /* If that passes, run Rabin-Miller as often as requested */
1.104 + if((res = mpp_pprime(p, nr)) == MP_YES)
1.105 + break;
1.106 + else if(res != MP_NO)
1.107 + goto CLEANUP;
1.108 +
1.109 + } while((res = mp_add_d(p, 2, p)) == MP_OKAY);
1.110 +
1.111 + CLEANUP:
1.112 + return res;
1.113 +
1.114 +} /* end make_prime() */
1.115 +
1.116 +/*------------------------------------------------------------------------*/
1.117 +/* HERE THERE BE DRAGONS */
