The Tor Browser: security/nss/lib/freebl/mpi/utils/makeprime.c@6474c204b198

Cloned upstream origin tor-browser at tor-browser-31.3.0esr-4.5-1-build1
revision ID fc1c9ff7c1b2defdbc039f12214767608f46423f for hacking purpose.

     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/. */

    13 #include <stdio.h>

    14 #include <stdlib.h>

    15 #include <ctype.h>

    17 /* These two must be included for make_prime() to work */

    19 #include "mpi.h"

    20 #include "mpprime.h"

    22 /*

    23   make_prime(p, nr)

    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.

    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);

    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;

    42   if(argc < 2) {

    43     fprintf(stderr, "Usage: %s <start-value>\n", argv[0]);

    44     return 1;

    45   }

    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);

    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);

    59     return 1;

    61   } else {

    62     char  *buf = malloc(mp_radix_size(&start, 10));

    64     mp_todecimal(&start, buf);

    65     printf("%s\n", buf);

    66     free(buf);

    68     mp_clear(&start);

    70     return 0;

    71   }

    73 } /* end main() */

    75 /*------------------------------------------------------------------------*/

    77 mp_err   make_prime(mp_int *p, int nr)

    78 {

    79   mp_err  res;

    81   if(mp_iseven(p)) {

    82     mp_add_d(p, 1, p);

    83   }

    85   do {

    86     mp_digit   which = prime_tab_size;

    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;

    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;

   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;

   106   } while((res = mp_add_d(p, 2, p)) == MP_OKAY);

   108  CLEANUP:

   109   return res;

   111 } /* end make_prime() */

   113 /*------------------------------------------------------------------------*/

   114 /* HERE THERE BE DRAGONS                                                  */

The Tor Browser / file revision