1 /* Exercise mpz_probab_prime_p.
2
3 Copyright 2002 Free Software Foundation, Inc.
4
5 This file is part of the GNU MP Library test suite.
6
7 The GNU MP Library test suite is free software; you can redistribute it
8 and/or modify it under the terms of the GNU General Public License as
9 published by the Free Software Foundation; either version 3 of the License,
10 or (at your option) any later version.
11
12 The GNU MP Library test suite is distributed in the hope that it will be
13 useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General
15 Public License for more details.
16
17 You should have received a copy of the GNU General Public License along with
18 the GNU MP Library test suite. If not, see https://www.gnu.org/licenses/. */
19
20 #include <stdio.h>
21 #include <stdlib.h>
22 #include "gmp.h"
23 #include "gmp-impl.h"
24 #include "tests.h"
25
26
27 /* Enhancements:
28
29 - Test some big primes don't come back claimed to be composite.
30 - Test some big composites don't come back claimed to be certainly prime.
31 - Test some big composites with small factors are identified as certainly
32 composite. */
33
34
35 /* return 1 if prime, 0 if composite */
36 int
isprime(long n)37 isprime (long n)
38 {
39 long i;
40
41 n = ABS(n);
42
43 if (n < 2)
44 return 0;
45 if (n == 2)
46 return 1;
47 if ((n & 1) == 0)
48 return 0;
49
50 for (i = 3; i < n; i++)
51 if ((n % i) == 0)
52 return 0;
53
54 return 1;
55 }
56
57 void
check_one(mpz_srcptr n,int want)58 check_one (mpz_srcptr n, int want)
59 {
60 int got;
61
62 got = mpz_probab_prime_p (n, 25);
63
64 /* "definitely prime" is fine if we only wanted "probably prime" */
65 if (got == 2 && want == 1)
66 want = 2;
67
68 if (got != want)
69 {
70 printf ("mpz_probab_prime_p\n");
71 mpz_trace (" n ", n);
72 printf (" got =%d", got);
73 printf (" want=%d", want);
74 abort ();
75 }
76 }
77
78 void
check_pn(mpz_ptr n,int want)79 check_pn (mpz_ptr n, int want)
80 {
81 check_one (n, want);
82 mpz_neg (n, n);
83 check_one (n, want);
84 }
85
86 /* expect certainty for small n */
87 void
check_small(void)88 check_small (void)
89 {
90 mpz_t n;
91 long i;
92
93 mpz_init (n);
94
95 for (i = 0; i < 300; i++)
96 {
97 mpz_set_si (n, i);
98 check_pn (n, isprime (i));
99 }
100
101 mpz_clear (n);
102 }
103
104 void
check_composites(int count)105 check_composites (int count)
106 {
107 int i;
108 mpz_t a, b, n, bs;
109 unsigned long size_range, size;
110 gmp_randstate_ptr rands = RANDS;
111
112 mpz_init (a);
113 mpz_init (b);
114 mpz_init (n);
115 mpz_init (bs);
116
117 for (i = 0; i < count; i++)
118 {
119 mpz_urandomb (bs, rands, 32);
120 size_range = mpz_get_ui (bs) % 13 + 1; /* 0..8192 bit operands */
121
122 mpz_urandomb (bs, rands, size_range);
123 size = mpz_get_ui (bs);
124 mpz_rrandomb (a, rands, size);
125
126 mpz_urandomb (bs, rands, 32);
127 size_range = mpz_get_ui (bs) % 13 + 1; /* 0..8192 bit operands */
128 mpz_rrandomb (b, rands, size);
129
130 /* Exclude trivial factors */
131 if (mpz_cmp_ui (a, 1) == 0)
132 mpz_set_ui (a, 2);
133 if (mpz_cmp_ui (b, 1) == 0)
134 mpz_set_ui (b, 2);
135
136 mpz_mul (n, a, b);
137
138 check_pn (n, 0);
139 }
140 mpz_clear (a);
141 mpz_clear (b);
142 mpz_clear (n);
143 mpz_clear (bs);
144 }
145
146 static void
check_primes(void)147 check_primes (void)
148 {
149 static const char * const primes[] = {
150 "2", "17", "65537",
151 /* diffie-hellman-group1-sha1, also "Well known group 2" in RFC
152 2412, 2^1024 - 2^960 - 1 + 2^64 * { [2^894 pi] + 129093 } */
153 "0xFFFFFFFFFFFFFFFFC90FDAA22168C234C4C6628B80DC1CD1"
154 "29024E088A67CC74020BBEA63B139B22514A08798E3404DD"
155 "EF9519B3CD3A431B302B0A6DF25F14374FE1356D6D51C245"
156 "E485B576625E7EC6F44C42E9A637ED6B0BFF5CB6F406B7ED"
157 "EE386BFB5A899FA5AE9F24117C4B1FE649286651ECE65381"
158 "FFFFFFFFFFFFFFFF",
159 NULL
160 };
161
162 mpz_t n;
163 int i;
164
165 mpz_init (n);
166
167 for (i = 0; primes[i]; i++)
168 {
169 mpz_set_str_or_abort (n, primes[i], 0);
170 check_one (n, 1);
171 }
172 mpz_clear (n);
173 }
174
175 int
main(int argc,char ** argv)176 main (int argc, char **argv)
177 {
178 int count = 1000;
179
180 TESTS_REPS (count, argv, argc);
181
182 tests_start ();
183
184 check_small ();
185 check_composites (count);
186 check_primes ();
187
188 tests_end ();
189 exit (0);
190 }
191