1 /* Test mpz_nextprime.
2
3 Copyright 2009, 2015, 2018 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
refmpz_nextprime(mpz_ptr p,mpz_srcptr t)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
run(const char * start,int reps,const char * end,short diffs[])36 run (const char *start, int reps, const char *end, short diffs[])
37 {
38 mpz_t x, y;
39 int i;
40
41 mpz_init_set_str (x, start, 0);
42 mpz_init (y);
43
44 for (i = 0; i < reps; i++)
45 {
46 mpz_nextprime (y, x);
47 mpz_sub (x, y, x);
48 if (diffs != NULL &&
49 (! mpz_fits_sshort_p (x) || diffs[i] != (short) mpz_get_ui (x)))
50 {
51 gmp_printf ("diff list discrepancy\n");
52 abort ();
53 }
54 mpz_swap (x, y);
55 }
56
57 mpz_set_str (y, end, 0);
58
59 if (mpz_cmp (x, y) != 0)
60 {
61 gmp_printf ("got %Zx\n", x);
62 gmp_printf ("want %Zx\n", y);
63 abort ();
64 }
65
66 mpz_clear (y);
67 mpz_clear (x);
68 }
69
70 extern short diff1[];
71 extern short diff3[];
72 extern short diff4[];
73 extern short diff5[];
74 extern short diff6[];
75
76 int
main(int argc,char ** argv)77 main (int argc, char **argv)
78 {
79 int i;
80 int reps = 20;
81 gmp_randstate_ptr rands;
82 mpz_t bs, x, nxtp, ref_nxtp;
83 unsigned long size_range;
84
85 tests_start();
86 rands = RANDS;
87
88 run ("2", 1000, "0x1ef7", diff1);
89
90 run ("3", 1000 - 1, "0x1ef7", NULL);
91
92 run ("0x8a43866f5776ccd5b02186e90d28946aeb0ed914", 50,
93 "0x8a43866f5776ccd5b02186e90d28946aeb0eeec5", diff3);
94
95 run ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF6C", 50, /* 2^148 - 148 */
96 "0x100000000000000000000000000000000010ab", diff4);
97
98 run ("0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898d8b1b", 50,
99 "0x1c2c26be55317530311facb648ea06b359b969715db83292ab8cf898da957", diff5);
100
101 run ("0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF80", 50, /* 2^128 - 128 */
102 "0x10000000000000000000000000000155B", diff6);
103
104 mpz_init (bs);
105 mpz_init (x);
106 mpz_init (nxtp);
107 mpz_init (ref_nxtp);
108
109 TESTS_REPS (reps, argv, argc);
110
111 for (i = 0; i < reps; i++)
112 {
113 mpz_urandomb (bs, rands, 32);
114 size_range = mpz_get_ui (bs) % 8 + 2; /* 0..1024 bit operands */
115
116 mpz_urandomb (bs, rands, size_range);
117 mpz_rrandomb (x, rands, mpz_get_ui (bs));
118
119 /* gmp_printf ("%ld: %Zd\n", mpz_sizeinbase (x, 2), x); */
120
121 mpz_nextprime (nxtp, x);
122 refmpz_nextprime (ref_nxtp, x);
123 if (mpz_cmp (nxtp, ref_nxtp) != 0)
124 abort ();
125 }
126
127 mpz_clear (bs);
128 mpz_clear (x);
129 mpz_clear (nxtp);
130 mpz_clear (ref_nxtp);
131
132 tests_end ();
133 return 0;
134 }
135
136 short diff1[] =
137 {
138 1,2,2,4,2,4,2,4,6,2,6,4,2,4,6,6,
139 2,6,4,2,6,4,6,8,4,2,4,2,4,14,4,6,
140 2,10,2,6,6,4,6,6,2,10,2,4,2,12,12,4,
141 2,4,6,2,10,6,6,6,2,6,4,2,10,14,4,2,
142 4,14,6,10,2,4,6,8,6,6,4,6,8,4,8,10,
143 2,10,2,6,4,6,8,4,2,4,12,8,4,8,4,6,
144 12,2,18,6,10,6,6,2,6,10,6,6,2,6,6,4,
145 2,12,10,2,4,6,6,2,12,4,6,8,10,8,10,8,
146 6,6,4,8,6,4,8,4,14,10,12,2,10,2,4,2,
147 10,14,4,2,4,14,4,2,4,20,4,8,10,8,4,6,
148 6,14,4,6,6,8,6,12,4,6,2,10,2,6,10,2,
149 10,2,6,18,4,2,4,6,6,8,6,6,22,2,10,8,
150 10,6,6,8,12,4,6,6,2,6,12,10,18,2,4,6,
151 2,6,4,2,4,12,2,6,34,6,6,8,18,10,14,4,
152 2,4,6,8,4,2,6,12,10,2,4,2,4,6,12,12,
153 8,12,6,4,6,8,4,8,4,14,4,6,2,4,6,2,
154 6,10,20,6,4,2,24,4,2,10,12,2,10,8,6,6,
155 6,18,6,4,2,12,10,12,8,16,14,6,4,2,4,2,
156 10,12,6,6,18,2,16,2,22,6,8,6,4,2,4,8,
157 6,10,2,10,14,10,6,12,2,4,2,10,12,2,16,2,
158 6,4,2,10,8,18,24,4,6,8,16,2,4,8,16,2,
159 4,8,6,6,4,12,2,22,6,2,6,4,6,14,6,4,
160 2,6,4,6,12,6,6,14,4,6,12,8,6,4,26,18,
161 10,8,4,6,2,6,22,12,2,16,8,4,12,14,10,2,
162 4,8,6,6,4,2,4,6,8,4,2,6,10,2,10,8,
163 4,14,10,12,2,6,4,2,16,14,4,6,8,6,4,18,
164 8,10,6,6,8,10,12,14,4,6,6,2,28,2,10,8,
165 4,14,4,8,12,6,12,4,6,20,10,2,16,26,4,2,
166 12,6,4,12,6,8,4,8,22,2,4,2,12,28,2,6,
167 6,6,4,6,2,12,4,12,2,10,2,16,2,16,6,20,
168 16,8,4,2,4,2,22,8,12,6,10,2,4,6,2,6,
169 10,2,12,10,2,10,14,6,4,6,8,6,6,16,12,2,
170 4,14,6,4,8,10,8,6,6,22,6,2,10,14,4,6,
171 18,2,10,14,4,2,10,14,4,8,18,4,6,2,4,6,
172 2,12,4,20,22,12,2,4,6,6,2,6,22,2,6,16,
173 6,12,2,6,12,16,2,4,6,14,4,2,18,24,10,6,
174 2,10,2,10,2,10,6,2,10,2,10,6,8,30,10,2,
175 10,8,6,10,18,6,12,12,2,18,6,4,6,6,18,2,
176 10,14,6,4,2,4,24,2,12,6,16,8,6,6,18,16,
177 2,4,6,2,6,6,10,6,12,12,18,2,6,4,18,8,
178 24,4,2,4,6,2,12,4,14,30,10,6,12,14,6,10,
179 12,2,4,6,8,6,10,2,4,14,6,6,4,6,2,10,
180 2,16,12,8,18,4,6,12,2,6,6,6,28,6,14,4,
181 8,10,8,12,18,4,2,4,24,12,6,2,16,6,6,14,
182 10,14,4,30,6,6,6,8,6,4,2,12,6,4,2,6,
183 22,6,2,4,18,2,4,12,2,6,4,26,6,6,4,8,
184 10,32,16,2,6,4,2,4,2,10,14,6,4,8,10,6,
185 20,4,2,6,30,4,8,10,6,6,8,6,12,4,6,2,
186 6,4,6,2,10,2,16,6,20,4,12,14,28,6,20,4,
187 18,8,6,4,6,14,6,6,10,2,10,12,8,10,2,10,
188 8,12,10,24,2,4,8,6,4,8,18,10,6,6,2,6,
189 10,12,2,10,6,6,6,8,6,10,6,2,6,6,6,10,
190 8,24,6,22,2,18,4,8,10,30,8,18,4,2,10,6,
191 2,6,4,18,8,12,18,16,6,2,12,6,10,2,10,2,
192 6,10,14,4,24,2,16,2,10,2,10,20,4,2,4,8,
193 16,6,6,2,12,16,8,4,6,30,2,10,2,6,4,6,
194 6,8,6,4,12,6,8,12,4,14,12,10,24,6,12,6,
195 2,22,8,18,10,6,14,4,2,6,10,8,6,4,6,30,
196 14,10,2,12,10,2,16,2,18,24,18,6,16,18,6,2,
197 18,4,6,2,10,8,10,6,6,8,4,6,2,10,2,12,
198 4,6,6,2,12,4,14,18,4,6,20,4,8,6,4,8,
199 4,14,6,4,14,12,4,2,30,4,24,6,6,12,12,14,
200 6,4,2,4,18,6,12,8
201 };
202
203 short diff3[] =
204 {
205 33,32,136,116,24,22,104,114,76,278,238,162,36,44,388,134,
206 130,26,312,42,138,28,24,80,138,108,270,12,330,130,98,102,
207 162,34,36,170,90,34,14,6,24,66,154,218,70,132,188,88,
208 80,82
209 };
210
211 short diff4[] =
212 {
213 239,92,64,6,104,24,46,258,68,18,54,100,68,154,26,4,
214 38,142,168,42,18,26,286,104,136,116,40,2,28,110,52,78,
215 104,24,54,96,4,626,196,24,56,36,52,102,48,156,26,18,
216 42,40
217 };
218
219 short diff5[] =
220 {
221 268,120,320,184,396,2,94,108,20,318,274,14,64,122,220,108,
222 18,174,6,24,348,32,64,116,268,162,20,156,28,110,52,428,
223 196,14,262,30,194,120,300,66,268,12,428,370,212,198,192,130,
224 30,80
225 };
226
227 short diff6[] =
228 {
229 179,30,84,108,112,36,42,110,52,132,60,30,326,114,496,92,100,
230 272,36,54,90,4,2,24,40,398,150,72,60,16,8,4,80,16,2,342,112,
231 14,136,236,40,18,50,192,198,204,40,266,42,274
232 };
233