michael@0: /*
michael@0:  * makeprime.c
michael@0:  *
michael@0:  * A simple prime generator function (and test driver).  Prints out the
michael@0:  * first prime it finds greater than or equal to the starting value.
michael@0:  *
michael@0:  * Usage: makeprime <start>
michael@0:  *
michael@0:  * This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: #include <stdio.h>
michael@0: #include <stdlib.h>
michael@0: #include <ctype.h>
michael@0: 
michael@0: /* These two must be included for make_prime() to work */
michael@0: 
michael@0: #include "mpi.h"
michael@0: #include "mpprime.h"
michael@0: 
michael@0: /*
michael@0:   make_prime(p, nr)
michael@0: 
michael@0:   Find the smallest prime integer greater than or equal to p, where
michael@0:   primality is verified by 'nr' iterations of the Rabin-Miller
michael@0:   probabilistic primality test.  The caller is responsible for
michael@0:   generating the initial value of p.
michael@0: 
michael@0:   Returns MP_OKAY if a prime has been generated, otherwise the error
michael@0:   code indicates some other problem.  The value of p is clobbered; the
michael@0:   caller should keep a copy if the value is needed.  
michael@0:  */
michael@0: mp_err   make_prime(mp_int *p, int nr);
michael@0: 
michael@0: /* The main() is not required -- it's just a test driver */
michael@0: int main(int argc, char *argv[])
michael@0: {
michael@0:   mp_int    start;
michael@0:   mp_err    res;
michael@0: 
michael@0:   if(argc < 2) {
michael@0:     fprintf(stderr, "Usage: %s <start-value>\n", argv[0]);
michael@0:     return 1;
michael@0:   }
michael@0: 	    
michael@0:   mp_init(&start);
michael@0:   if(argv[1][0] == '0' && tolower(argv[1][1]) == 'x') {
michael@0:     mp_read_radix(&start, argv[1] + 2, 16);
michael@0:   } else {
michael@0:     mp_read_radix(&start, argv[1], 10);
michael@0:   }
michael@0:   mp_abs(&start, &start);
michael@0: 
michael@0:   if((res = make_prime(&start, 5)) != MP_OKAY) {
michael@0:     fprintf(stderr, "%s: error: %s\n", argv[0], mp_strerror(res));
michael@0:     mp_clear(&start);
michael@0: 
michael@0:     return 1;
michael@0: 
michael@0:   } else {
michael@0:     char  *buf = malloc(mp_radix_size(&start, 10));
michael@0: 
michael@0:     mp_todecimal(&start, buf);
michael@0:     printf("%s\n", buf);
michael@0:     free(buf);
michael@0:     
michael@0:     mp_clear(&start);
michael@0: 
michael@0:     return 0;
michael@0:   }
michael@0:   
michael@0: } /* end main() */
michael@0: 
michael@0: /*------------------------------------------------------------------------*/
michael@0: 
michael@0: mp_err   make_prime(mp_int *p, int nr)
michael@0: {
michael@0:   mp_err  res;
michael@0: 
michael@0:   if(mp_iseven(p)) {
michael@0:     mp_add_d(p, 1, p);
michael@0:   }
michael@0: 
michael@0:   do {
michael@0:     mp_digit   which = prime_tab_size;
michael@0: 
michael@0:     /*  First test for divisibility by a few small primes */
michael@0:     if((res = mpp_divis_primes(p, &which)) == MP_YES)
michael@0:       continue;
michael@0:     else if(res != MP_NO)
michael@0:       goto CLEANUP;
michael@0: 
michael@0:     /* If that passes, try one iteration of Fermat's test */
michael@0:     if((res = mpp_fermat(p, 2)) == MP_NO)
michael@0:       continue;
michael@0:     else if(res != MP_YES)
michael@0:       goto CLEANUP;
michael@0: 
michael@0:     /* If that passes, run Rabin-Miller as often as requested */
michael@0:     if((res = mpp_pprime(p, nr)) == MP_YES)
michael@0:       break;
michael@0:     else if(res != MP_NO)
michael@0:       goto CLEANUP;
michael@0:       
michael@0:   } while((res = mp_add_d(p, 2, p)) == MP_OKAY);
michael@0: 
michael@0:  CLEANUP:
michael@0:   return res;
michael@0: 
michael@0: } /* end make_prime() */
michael@0: 
michael@0: /*------------------------------------------------------------------------*/
michael@0: /* HERE THERE BE DRAGONS                                                  */