1 /* Test mpz_nextprime.
2
3 Copyright 2009, 2015, 2018, 2020 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
21 #include <stdio.h>
22 #include <stdlib.h>
23
24 #include "gmp-impl.h"
25 #include "tests.h"
26
27 void
28 refmpz_nextprime (mpz_ptr p, mpz_srcptr t)
29 {
30 mpz_add_ui (p, t, 1L);
31 while (! mpz_probab_prime_p (p, 10))
32 mpz_add_ui (p, p, 1L);
33 }
34
35 void
36 refmpz_prevprime (mpz_ptr p, mpz_srcptr t)
37 {
38 if (mpz_cmp_ui(t, 2) <= 0)
39 return;
40
41 mpz_sub_ui (p, t, 1L);
42 while (! mpz_probab_prime_p (p, 10))
43 mpz_sub_ui (p, p, 1L);
44 }
45
46 void
47 test_largegap (mpz_t low, const int gap)
48 {
49 mpz_t t, nxt;
50 mpz_init (t);
51 mpz_init (nxt);
52
53 mpz_nextprime(nxt, low);
54 mpz_sub(t, nxt, low);
55
56 if (mpz_cmp_ui(t, gap) != 0)
57 {
58 gmp_printf ("nextprime gap %Zd => %Zd != %d\n", low, nxt, gap);
59 abort ();
60 }
61
62 mpz_prevprime(t, nxt);
63 if (mpz_cmp(t, low) != 0)
64 {
65 gmp_printf ("prevprime gap %Zd => %Zd != %d\n", nxt, t, gap);
66 abort ();
67 }
68
69 mpz_clear (t);
70 mpz_clear (nxt);
71 }
72
73 void
74 test_largegaps ()
75 {
76 mpz_t n;
77
78 mpz_init (n);
79
80 // largest gap with start < 2^32.
81 mpz_set_str (n, "3842610773", 10);
82 test_largegap (n, 336);
83
84 // largest gap with start < 2^64.
85 mpz_set_str (n, "18361375334787046697", 10);
86 test_largegap (n, 1550);
87
88 // test high merit primegap in the P30 digit range.
89 mpz_set_str (n, "3001549619028223830552751967", 10);
90 test_largegap (n, 2184);
91
92 // test high merit primegap in the P100 range.
93 mpz_primorial_ui (n, 257);
94 mpz_divexact_ui (n, n, 5610);
95 mpz_mul_ui (n, n, 4280516017UL);
96 mpz_sub_ui (n, n, 2560);
97 test_largegap (n, 9006);
98
99 // test high merit primegap in the P200 range.
100 mpz_primorial_ui (n, 409);
101 mpz_divexact_ui (n, n, 30);
102 mpz_mul_ui (n, n, 3483347771UL);
103 mpz_sub_ui (n, n, 7016);
104 test_largegap (n, 15900);
105
106 mpz_clear (n);
107 }
108
109 void
110 test_bitboundaries ()
111 {
112 mpz_t n;
113 mpz_init (n);
114
115 mpz_set_str (n, "0xfff1", 0);
116 test_largegap (n, 16);
117
118 mpz_set_str (n, "0xfffffffb", 0);
119 test_largegap (n, 20);
120
121 mpz_set_str (n, "0xffffffffffc5", 0);
122 test_largegap (n, 80);
123
124 mpz_set_str (n, "0xffffffffffffffc5", 0);
125 test_largegap (n, 72);
126
127 mpz_set_str (n, "0xffffffffffffffffffbf", 0);
128 test_largegap (n, 78);
129
130 mpz_set_str (n, "0xffffffffffffffffffffffef", 0);
131 test_largegap (n, 78);
132
133 mpz_set_str (n, "0xffffffffffffffffffffffffffb5", 0);
134 test_largegap (n, 100);
135
136 mpz_set_str (n, "0xffffffffffffffffffffffffffffff61", 0);
137 test_largegap (n, 210);
138
139 mpz_set_str (n, "0xffffffffffffffffffffffffffffffffffffffffffffff13", 0);
140 test_largegap (n, 370);
141
142 mpz_clear (n);
143 }
144
145 void
146 run (const char *start, int reps, const char *end, short diffs[])
147 {
148 mpz_t x, y;
149 int i;
150
151 mpz_init_set_str (x, start, 0);
152 mpz_init (y);
153
154 for (i = 0; i < reps; i++)
155 {
156 mpz_nextprime (y, x);
157 mpz_sub (x, y, x);
158 if (diffs != NULL &&
159 (! mpz_fits_sshort_p (x) || diffs[i] != (short) mpz_get_ui (x)))
160 {
161 gmp_printf ("diff list discrepancy\n");
162 abort ();
163 }
164 mpz_swap (x, y);
165 }
166
167 mpz_set_str (y, end, 0);
168
169 if (mpz_cmp (x, y) != 0)
170 {
171 gmp_printf ("got %Zd\n", x);
172 gmp_printf ("want %Zd\n", y);
173 abort ();
174 }
175
176 mpz_clear (y);
177 mpz_clear (x);
178 }
179
180 void
181 run_p (const char *start, int reps, const char *end, short diffs[])
182 {
183 mpz_t x, y;
184 int i;
185
186 mpz_init_set_str (x, end, 0);
187 mpz_init (y);
188
189 // Last rep doesn't share same data with nextprime
190 for (i = 0; i < reps - 1; i++)
191 {
192 mpz_prevprime (y, x);
193 mpz_sub (x, x, y);
194 if (diffs != NULL &&
195 (! mpz_fits_sshort_p (x) || diffs[reps - i - 1] != (short) mpz_get_ui (x)))
196 {
197 gmp_printf ("diff list discrepancy %Zd, %d vs %d\n",
198 y, diffs[i], mpz_get_ui (x));
199 abort ();
200 }
201 mpz_swap (x, y);
202 }
203
204 // starts aren't always prime, so check that result is less than or equal
205 mpz_prevprime(x, x);
206
207 mpz_set_str(y, start, 0);
208 if (mpz_cmp (x, y) > 0)
209 {
210 gmp_printf ("got %Zd\n", x);
211 gmp_printf ("want %Zd\n", y);
212 abort ();
213 }
214
215 mpz_clear (y);
216 mpz_clear (x);
217 }
218
219
220 extern short diff1[];
221 extern short diff3[];
222 extern short diff4[];
223 extern short diff5[];
224 extern short diff6[];
225
226 void
227 test_ref (gmp_randstate_ptr rands, int reps,
228 void (*func)(mpz_t, const mpz_t),
229 void(*ref_func)(mpz_t, const mpz_t))
230 {
231 int i;
232 mpz_t bs, x, test_p, ref_p;
233 unsigned long size_range;
234
235 mpz_init (bs);
236 mpz_init (x);
237 mpz_init (test_p);
238 mpz_init (ref_p);
239
240 for (i = 0; i < reps; i++)
241 {
242 mpz_urandomb (bs, rands, 32);
243 size_range = mpz_get_ui (bs) % 8 + 2; /* 0..1024 bit operands */
244
245 mpz_urandomb (bs, rands, size_range);
246 mpz_rrandomb (x, rands, mpz_get_ui (bs));
247
248 func (test_p, x);
249 ref_func (ref_p, x);
250 if (mpz_cmp (test_p, ref_p) != 0)
251 {
252 gmp_printf ("start %Zd\n", x);
253 gmp_printf ("got %Zd\n", test_p);
254 gmp_printf ("want %Zd\n", ref_p);
255 abort ();
256 }
257 }
258
259 mpz_clear (bs);
260 mpz_clear (x);
261 mpz_clear (test_p);
262 mpz_clear (ref_p);
263 }
264
265 void
266 test_nextprime(gmp_randstate_ptr rands, int reps)
267 {
268 run ("2", 1000, "0x1ef7", diff1);
269
270 run ("3", 1000 - 1, "0x1ef7", NULL);
271
272 run ("0x8a43866f5776ccd5b02186e90d28946aeb0ed914", 50,
273 "0x8a43866f5776ccd5b02186e90d28946aeb0eeec5", diff3);
274
275 run ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C", 50, /* 2^148 - 148 */
276 "0x100000000000000000000000000000000010ab", diff4);
277
278 run ("0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898d8b1b", 50,
279 "0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898da957", diff5);
280
281 run ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80", 50, /* 2^128 - 128 */
282 "0x10000000000000000000000000000155B", diff6);
283
284 test_ref(
285 rands, reps,
286 (void (*)(mpz_t, const mpz_t)) mpz_nextprime,
287 refmpz_nextprime);
288 }
289
290 void
291 test_prevprime (gmp_randstate_ptr rands, int reps)
292 {
293 long i;
294 int retval;
295 mpz_t n, prvp;
296
297 mpz_init (n);
298 mpz_init (prvp);
299
300 /* Test mpz_prevprime(n <= 2) returns 0, leaves rop unchanged. */
301 {
302 int temp = 123;
303 mpz_set_ui (prvp, temp);
304 for (i = 0; i <= 2; i++)
305 {
306 mpz_set_si(n, i);
307 retval = mpz_prevprime (prvp, n);
308 if ( retval != 0 || mpz_cmp_ui (prvp, temp) != 0 )
309 {
310 gmp_printf ("mpz_prevprime(%Zd) return (%d) rop (%Zd)\n", n, retval, prvp);
311 abort ();
312 }
313 }
314 }
315
316 mpz_clear (n);
317 mpz_clear (prvp);
318
319 run_p ("2", 1000, "0x1ef7", diff1);
320
321 run_p ("3", 1000 - 1, "0x1ef7", NULL);
322
323 run_p ("0x8a43866f5776ccd5b02186e90d28946aeb0ed914", 50,
324 "0x8a43866f5776ccd5b02186e90d28946aeb0eeec5", diff3);
325
326 run_p ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C", 50, /* 2^148 - 148 */
327 "0x100000000000000000000000000000000010ab", diff4);
328
329 run_p ("0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898d8b1b", 50,
330 "0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898da957", diff5);
331
332 run_p ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80", 50, /* 2^128 - 128 */
333 "0x10000000000000000000000000000155B", diff6);
334
335 // Cast away int return from mpz_prevprime for test ref.
336 test_ref(
337 rands, reps,
338 (void (*)(mpz_t, const mpz_t)) mpz_prevprime,
339 refmpz_prevprime);
340 }
341
342 int
343 main (int argc, char **argv)
344 {
345 gmp_randstate_ptr rands;
346 int reps = 20;
347
348 tests_start();
349
350 rands = RANDS;
351 TESTS_REPS (reps, argv, argc);
352
353 test_nextprime(rands, reps);
354 test_prevprime(rands, reps);
355
356 test_largegaps ();
357 test_bitboundaries ();
358
359 tests_end ();
360 return 0;
361 }
362
363 short diff1[] =
364 {
365 1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,
366 2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,
367 2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,
368 2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,
369 4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,
370 2,10,2,6,4,6,8,4,2,4,12,8,4,8,4,6,
371 12,2,18,6,10,6,6,2,6,10,6,6,2,6,6,4,
372 2,12,10,2,4,6,6,2,12,4,6,8,10,8,10,8,
373 6,6,4,8,6,4,8,4,14,10,12,2,10,2,4,2,
374 10,14,4,2,4,14,4,2,4,20,4,8,10,8,4,6,
375 6,14,4,6,6,8,6,12,4,6,2,10,2,6,10,2,
376 10,2,6,18,4,2,4,6,6,8,6,6,22,2,10,8,
377 10,6,6,8,12,4,6,6,2,6,12,10,18,2,4,6,
378 2,6,4,2,4,12,2,6,34,6,6,8,18,10,14,4,
379 2,4,6,8,4,2,6,12,10,2,4,2,4,6,12,12,
380 8,12,6,4,6,8,4,8,4,14,4,6,2,4,6,2,
381 6,10,20,6,4,2,24,4,2,10,12,2,10,8,6,6,
382 6,18,6,4,2,12,10,12,8,16,14,6,4,2,4,2,
383 10,12,6,6,18,2,16,2,22,6,8,6,4,2,4,8,
384 6,10,2,10,14,10,6,12,2,4,2,10,12,2,16,2,
385 6,4,2,10,8,18,24,4,6,8,16,2,4,8,16,2,
386 4,8,6,6,4,12,2,22,6,2,6,4,6,14,6,4,
387 2,6,4,6,12,6,6,14,4,6,12,8,6,4,26,18,
388 10,8,4,6,2,6,22,12,2,16,8,4,12,14,10,2,
389 4,8,6,6,4,2,4,6,8,4,2,6,10,2,10,8,
390 4,14,10,12,2,6,4,2,16,14,4,6,8,6,4,18,
391 8,10,6,6,8,10,12,14,4,6,6,2,28,2,10,8,
392 4,14,4,8,12,6,12,4,6,20,10,2,16,26,4,2,
393 12,6,4,12,6,8,4,8,22,2,4,2,12,28,2,6,
394 6,6,4,6,2,12,4,12,2,10,2,16,2,16,6,20,
395 16,8,4,2,4,2,22,8,12,6,10,2,4,6,2,6,
396 10,2,12,10,2,10,14,6,4,6,8,6,6,16,12,2,
397 4,14,6,4,8,10,8,6,6,22,6,2,10,14,4,6,
398 18,2,10,14,4,2,10,14,4,8,18,4,6,2,4,6,
399 2,12,4,20,22,12,2,4,6,6,2,6,22,2,6,16,
400 6,12,2,6,12,16,2,4,6,14,4,2,18,24,10,6,
401 2,10,2,10,2,10,6,2,10,2,10,6,8,30,10,2,
402 10,8,6,10,18,6,12,12,2,18,6,4,6,6,18,2,
403 10,14,6,4,2,4,24,2,12,6,16,8,6,6,18,16,
404 2,4,6,2,6,6,10,6,12,12,18,2,6,4,18,8,
405 24,4,2,4,6,2,12,4,14,30,10,6,12,14,6,10,
406 12,2,4,6,8,6,10,2,4,14,6,6,4,6,2,10,
407 2,16,12,8,18,4,6,12,2,6,6,6,28,6,14,4,
408 8,10,8,12,18,4,2,4,24,12,6,2,16,6,6,14,
409 10,14,4,30,6,6,6,8,6,4,2,12,6,4,2,6,
410 22,6,2,4,18,2,4,12,2,6,4,26,6,6,4,8,
411 10,32,16,2,6,4,2,4,2,10,14,6,4,8,10,6,
412 20,4,2,6,30,4,8,10,6,6,8,6,12,4,6,2,
413 6,4,6,2,10,2,16,6,20,4,12,14,28,6,20,4,
414 18,8,6,4,6,14,6,6,10,2,10,12,8,10,2,10,
415 8,12,10,24,2,4,8,6,4,8,18,10,6,6,2,6,
416 10,12,2,10,6,6,6,8,6,10,6,2,6,6,6,10,
417 8,24,6,22,2,18,4,8,10,30,8,18,4,2,10,6,
418 2,6,4,18,8,12,18,16,6,2,12,6,10,2,10,2,
419 6,10,14,4,24,2,16,2,10,2,10,20,4,2,4,8,
420 16,6,6,2,12,16,8,4,6,30,2,10,2,6,4,6,
421 6,8,6,4,12,6,8,12,4,14,12,10,24,6,12,6,
422 2,22,8,18,10,6,14,4,2,6,10,8,6,4,6,30,
423 14,10,2,12,10,2,16,2,18,24,18,6,16,18,6,2,
424 18,4,6,2,10,8,10,6,6,8,4,6,2,10,2,12,
425 4,6,6,2,12,4,14,18,4,6,20,4,8,6,4,8,
426 4,14,6,4,14,12,4,2,30,4,24,6,6,12,12,14,
427 6,4,2,4,18,6,12,8
428 };
429
430 short diff3[] =
431 {
432 33,32,136,116,24,22,104,114,76,278,238,162,36,44,388,134,
433 130,26,312,42,138,28,24,80,138,108,270,12,330,130,98,102,
434 162,34,36,170,90,34,14,6,24,66,154,218,70,132,188,88,
435 80,82
436 };
437
438 short diff4[] =
439 {
440 239,92,64,6,104,24,46,258,68,18,54,100,68,154,26,4,
441 38,142,168,42,18,26,286,104,136,116,40,2,28,110,52,78,
442 104,24,54,96,4,626,196,24,56,36,52,102,48,156,26,18,
443 42,40
444 };
445
446 short diff5[] =
447 {
448 268,120,320,184,396,2,94,108,20,318,274,14,64,122,220,108,
449 18,174,6,24,348,32,64,116,268,162,20,156,28,110,52,428,
450 196,14,262,30,194,120,300,66,268,12,428,370,212,198,192,130,
451 30,80
452 };
453
454 short diff6[] =
455 {
456 179,30,84,108,112,36,42,110,52,132,60,30,326,114,496,92,100,
457 272,36,54,90,4,2,24,40,398,150,72,60,16,8,4,80,16,2,342,112,
458 14,136,236,40,18,50,192,198,204,40,266,42,274
459 };