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