1 /*
2 * isprime.c
3 *
4 * Probabilistic primality tester command-line tool
5 *
6 * This Source Code Form is subject to the terms of the Mozilla Public
7 * License, v. 2.0. If a copy of the MPL was not distributed with this
8 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
9
10 #include <stdio.h>
11 #include <stdlib.h>
12 #include <string.h>
13
14 #include "mpi.h"
15 #include "mpprime.h"
16
17 #define RM_TESTS 15 /* how many iterations of Rabin-Miller? */
18 #define MINIMUM 1024 /* don't bother us with a < this */
19
20 int g_tests = RM_TESTS;
21 char *g_prog = NULL;
22
23 int
main(int argc,char * argv[])24 main(int argc, char *argv[])
25 {
26 mp_int a;
27 mp_digit np = prime_tab_size; /* from mpprime.h */
28 int res = 0;
29
30 g_prog = argv[0];
31
32 if (argc < 2) {
33 fprintf(stderr, "Usage: %s <a>, where <a> is a decimal integer\n"
34 "Use '0x' prefix for a hexadecimal value\n",
35 g_prog);
36 return 1;
37 }
38
39 /* Read number of tests from environment, if present */
40 {
41 char *tmp;
42
43 if ((tmp = PR_GetEnvSecure("RM_TESTS")) != NULL) {
44 if ((g_tests = atoi(tmp)) <= 0)
45 g_tests = RM_TESTS;
46 }
47 }
48
49 mp_init(&a);
50 if (argv[1][0] == '0' && argv[1][1] == 'x')
51 mp_read_radix(&a, argv[1] + 2, 16);
52 else
53 mp_read_radix(&a, argv[1], 10);
54
55 if (mp_cmp_d(&a, MINIMUM) <= 0) {
56 fprintf(stderr, "%s: please use a value greater than %d\n",
57 g_prog, MINIMUM);
58 mp_clear(&a);
59 return 1;
60 }
61
62 /* Test for divisibility by small primes */
63 if (mpp_divis_primes(&a, &np) != MP_NO) {
64 printf("Not prime (divisible by small prime %d)\n", np);
65 res = 2;
66 goto CLEANUP;
67 }
68
69 /* Test with Fermat's test, using 2 as a witness */
70 if (mpp_fermat(&a, 2) != MP_YES) {
71 printf("Not prime (failed Fermat test)\n");
72 res = 2;
73 goto CLEANUP;
74 }
75
76 /* Test with Rabin-Miller probabilistic test */
77 if (mpp_pprime(&a, g_tests) == MP_NO) {
78 printf("Not prime (failed pseudoprime test)\n");
79 res = 2;
80 goto CLEANUP;
81 }
82
83 printf("Probably prime, 1 in 4^%d chance of false positive\n", g_tests);
84
85 CLEANUP:
86 mp_clear(&a);
87
88 return res;
89 }
90