1 /* Test mpz_powm, mpz_mul, mpz_mod, mpz_mod_ui, mpz_div_ui.
2
3 Copyright 1991, 1993, 1994, 1996, 1999-2001, 2009, 2012, 2019 Free
4 Software 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 <stdio.h>
22 #include <stdlib.h>
23 #include <string.h>
24
25 #include "gmp-impl.h"
26 #include "tests.h"
27
28 void debug_mp (mpz_t, int);
29
30 #define SIZEM 13
31
32 /* Check that all sizes up to just above MUL_TOOM22_THRESHOLD have been tested
33 a few times. FIXME: If SIZEM is set too low, this will never happen. */
34 int
35 allsizes_seen (unsigned int *allsizes)
36 {
37 mp_size_t i;
38
39 for (i = 1; i < MUL_TOOM22_THRESHOLD + 4; i++)
40 if (allsizes[i] < 4)
41 return 0;
42 return 1;
43 }
44
45 void
46 small_2pow (unsigned long reps)
47 {
48 mpz_t du, exp, mod;
49 mpz_t r1;
50 unsigned long m, e, r;
51 mp_limb_t b0 = 2;
52
53 mpz_roinit_n (du, &b0, 1);
54 mpz_init (exp);
55 mpz_init (mod);
56 mpz_init (r1);
57
58 for (m = 3; m * m < reps; m += 2)
59 {
60 mpz_set_ui (mod, m);
61 r = 1;
62 for (e = 0; e < m; e += 1)
63 {
64 mpz_set_ui (exp, e);
65 mpz_powm (r1, du, exp, mod);
66 MPZ_CHECK_FORMAT (r1);
67 if (mpz_cmp_ui (r1, r) != 0)
68 {
69 fprintf (stderr, "\nIncorrect result for operands:\n");
70 debug_mp (du, -16);
71 debug_mp (exp, -16);
72 debug_mp (mod, -16);
73 fprintf (stderr, "mpz_powm result:\n");
74 debug_mp (r1, -16);
75 fprintf (stderr, "Should be 2 ^ 0x%lx = 0x%lx (mod 0x%lx)\n", e, r, m);
76 abort ();
77 }
78 if (r > (m >> 1))
79 r = (r << 1) - m;
80 else
81 r = r << 1;
82 }
83 }
84
85 mpz_clear (exp);
86 mpz_clear (mod);
87 mpz_clear (r1);
88 }
89
90 int
91 main (int argc, char **argv)
92 {
93 mpz_t base, exp, mod;
94 mpz_t r1, r2, t1, exp2, base2;
95 mp_size_t base_size, exp_size, mod_size;
96 int i;
97 int reps = 1000;
98 gmp_randstate_ptr rands;
99 mpz_t bs;
100 unsigned long bsi, size_range;
101 unsigned int allsizes[1 << (SIZEM + 2 - 1)];
102
103 tests_start ();
104 TESTS_REPS (reps, argv, argc);
105
106 small_2pow ((unsigned int) reps);
107 rands = RANDS;
108
109 mpz_init (bs);
110
111 mpz_init (base);
112 mpz_init (exp);
113 mpz_init (mod);
114 mpz_init (r1);
115 mpz_init (r2);
116 mpz_init (t1);
117 mpz_init (exp2);
118 mpz_init (base2);
119
120 memset (allsizes, 0, (1 << (SIZEM + 2 - 1)) * sizeof (int));
121
122 reps += reps >> 3;
123 for (i = 0; i < reps || ! allsizes_seen (allsizes); i++)
124 {
125 mpz_urandomb (bs, rands, 32);
126 size_range = mpz_get_ui (bs) % SIZEM + 2;
127
128 if ((i & 7) == 0)
129 {
130 mpz_set_ui (exp, 1);
131
132 do /* Loop until mathematically well-defined. */
133 {
134 mpz_urandomb (bs, rands, size_range / 2 + 2);
135 base_size = mpz_get_ui (bs);
136 mpz_rrandomb (base, rands, base_size);
137 }
138 while (mpz_cmp_ui (base, 0) == 0);
139
140 mpz_urandomb (bs, rands, size_range / 2);
141 mod_size = mpz_get_ui (bs);
142 mod_size = MIN (mod_size, base_size);
143 mpz_rrandomb (mod, rands, mod_size);
144
145 mpz_urandomb (bs, rands, size_range);
146 mod_size = mpz_get_ui (bs) + base_size + 2;
147 if ((i & 8) == 0)
148 mod_size += GMP_NUMB_BITS - mod_size % GMP_NUMB_BITS;
149 mpz_setbit (mod, mod_size);
150
151 mpz_sub (base, base, mod);
152 }
153 else
154 {
155 do /* Loop until mathematically well-defined. */
156 {
157 if ((i & 7) == 4)
158 mpz_set_ui (base, 2);
159 else
160 {
161 mpz_urandomb (bs, rands, size_range);
162 base_size = mpz_get_ui (bs);
163 mpz_rrandomb (base, rands, base_size);
164 }
165
166 mpz_urandomb (bs, rands, 7L);
167 exp_size = mpz_get_ui (bs);
168 mpz_rrandomb (exp, rands, exp_size);
169 }
170 while (mpz_cmp_ui (base, 0) == 0 && mpz_cmp_ui (exp, 0) == 0);
171
172 do
173 {
174 mpz_urandomb (bs, rands, size_range);
175 mod_size = mpz_get_ui (bs);
176 mpz_rrandomb (mod, rands, mod_size);
177 }
178 while (mpz_cmp_ui (mod, 0) == 0);
179
180 allsizes[SIZ(mod)] += 1;
181
182 mpz_urandomb (bs, rands, 2);
183 bsi = mpz_get_ui (bs);
184 if ((bsi & 1) != 0)
185 mpz_neg (base, base);
186
187 /* printf ("%ld %ld %ld\n", SIZ (base), SIZ (exp), SIZ (mod)); */
188 }
189
190 mpz_set_ui (r2, 1);
191 mpz_mod (base2, base, mod);
192 mpz_set (exp2, exp);
193 mpz_mod (r2, r2, mod);
194
195 for (;;)
196 {
197 if (mpz_tstbit (exp2, 0))
198 {
199 mpz_mul (r2, r2, base2);
200 mpz_mod (r2, r2, mod);
201 }
202 if (mpz_cmp_ui (exp2, 1) <= 0)
203 break;
204 mpz_mul (base2, base2, base2);
205 mpz_mod (base2, base2, mod);
206 mpz_tdiv_q_2exp (exp2, exp2, 1);
207 }
208
209 mpz_powm (r1, base, exp, mod);
210 MPZ_CHECK_FORMAT (r1);
211
212 if (mpz_cmp (r1, r2) != 0)
213 {
214 fprintf (stderr, "\nIncorrect results in test %d for operands:\n", i);
215 debug_mp (base, -16);
216 debug_mp (exp, -16);
217 debug_mp (mod, -16);
218 fprintf (stderr, "mpz_powm result:\n");
219 debug_mp (r1, -16);
220 fprintf (stderr, "reference result:\n");
221 debug_mp (r2, -16);
222 abort ();
223 }
224
225 if (mpz_tdiv_ui (mod, 2) == 0)
226 continue;
227
228 mpz_powm_sec (r1, base, exp, mod);
229 MPZ_CHECK_FORMAT (r1);
230
231 if (mpz_cmp (r1, r2) != 0)
232 {
233 fprintf (stderr, "\nIncorrect results in test %d for operands:\n", i);
234 debug_mp (base, -16);
235 debug_mp (exp, -16);
236 debug_mp (mod, -16);
237 fprintf (stderr, "mpz_powm_sec result:\n");
238 debug_mp (r1, -16);
239 fprintf (stderr, "reference result:\n");
240 debug_mp (r2, -16);
241 abort ();
242 }
243 }
244
245 mpz_clear (bs);
246 mpz_clear (base);
247 mpz_clear (exp);
248 mpz_clear (mod);
249 mpz_clear (r1);
250 mpz_clear (r2);
251 mpz_clear (t1);
252 mpz_clear (exp2);
253 mpz_clear (base2);
254
255 tests_end ();
256 exit (0);
257 }
258
259 void
260 debug_mp (mpz_t x, int base)
261 {
262 mpz_out_str (stderr, base, x); fputc ('\n', stderr);
263 }