michael@0: /*
michael@0:  *  isprime.c
michael@0:  *
michael@0:  *  Probabilistic primality tester command-line tool
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 <string.h>
michael@0: 
michael@0: #include "mpi.h"
michael@0: #include "mpprime.h"
michael@0: 
michael@0: #define  RM_TESTS       15   /* how many iterations of Rabin-Miller? */
michael@0: #define  MINIMUM        1024 /* don't bother us with a < this        */
michael@0: 
michael@0: int      g_tests = RM_TESTS;
michael@0: char    *g_prog = NULL;
michael@0: 
michael@0: int main(int argc, char *argv[])
michael@0: {
michael@0:   mp_int   a;
michael@0:   mp_digit np = prime_tab_size; /* from mpprime.h */
michael@0:   int      res = 0;
michael@0: 
michael@0:   g_prog = argv[0];
michael@0: 
michael@0:   if(argc < 2) {
michael@0:     fprintf(stderr, "Usage: %s <a>, where <a> is a decimal integer\n"
michael@0: 	    "Use '0x' prefix for a hexadecimal value\n", g_prog);
michael@0:     return 1;
michael@0:   }
michael@0: 
michael@0:   /* Read number of tests from environment, if present */
michael@0:   {
michael@0:     char *tmp;
michael@0: 
michael@0:     if((tmp = getenv("RM_TESTS")) != NULL) {
michael@0:       if((g_tests = atoi(tmp)) <= 0)
michael@0: 	g_tests = RM_TESTS;
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   mp_init(&a);
michael@0:   if(argv[1][0] == '0' && argv[1][1] == 'x')
michael@0:     mp_read_radix(&a, argv[1] + 2, 16);
michael@0:   else
michael@0:     mp_read_radix(&a, argv[1], 10);
michael@0: 
michael@0:   if(mp_cmp_d(&a, MINIMUM) <= 0) {
michael@0:     fprintf(stderr, "%s: please use a value greater than %d\n", 
michael@0: 	    g_prog, MINIMUM);
michael@0:     mp_clear(&a);
michael@0:     return 1;
michael@0:   }
michael@0: 
michael@0:   /* Test for divisibility by small primes */
michael@0:   if(mpp_divis_primes(&a, &np) != MP_NO) {
michael@0:     printf("Not prime (divisible by small prime %d)\n", np);
michael@0:     res = 2;
michael@0:     goto CLEANUP;
michael@0:   }
michael@0: 
michael@0:   /* Test with Fermat's test, using 2 as a witness */
michael@0:   if(mpp_fermat(&a, 2) != MP_YES) {
michael@0:     printf("Not prime (failed Fermat test)\n");
michael@0:     res = 2;
michael@0:     goto CLEANUP;
michael@0:   }
michael@0:  
michael@0:   /* Test with Rabin-Miller probabilistic test */
michael@0:   if(mpp_pprime(&a, g_tests) == MP_NO) {
michael@0:       printf("Not prime (failed pseudoprime test)\n");
michael@0:       res = 2;
michael@0:       goto CLEANUP;
michael@0:   }
michael@0: 
michael@0:   printf("Probably prime, 1 in 4^%d chance of false positive\n", g_tests);
michael@0: 
michael@0: CLEANUP:
michael@0:   mp_clear(&a);
michael@0:   
michael@0:   return res;
michael@0: 
michael@0: }