1 //==============================================================================================
2 //
3 // This file is part of LiDIA --- a library for computational number theory
4 //
5 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
6 //
7 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
8 //
9 //----------------------------------------------------------------------------------------------
10 //
11 // $Id$
12 //
13 // Author : Markus Maurer (MM)
14 // Changes : See CVS log
15 //
16 //==============================================================================================
17
18
19 #ifdef HAVE_CONFIG_H
20 # include "config.h"
21 #endif
22 #include "LiDIA/multi_bigmod.h"
23 #include "LiDIA/random_generator.h"
24 #include <cassert>
25 #include <cstdio>
26
27
28
29 #ifdef LIDIA_NAMESPACE
30 using namespace LiDIA;
31 #endif
32
33
34
35 void
identitytest(multi_bigmod & a,multi_bigmod & b,multi_bigmod & c)36 identitytest (multi_bigmod & a, multi_bigmod & b, multi_bigmod & c)
37 {
38 assert(-(-a) == a);
39 assert((a + b) == (b + a));
40 assert((a + (-b)) == (a - b));
41 assert((a + (-b)) == (b - a + 2*a - 2*b));
42 assert((a * b) == (b * a));
43 assert((a * (-b)) == -(a * b));
44 assert((a / (-b)) == -(a / b));
45 assert((a - b) == -(b - a));
46 assert((a + (b + c)) == ((a + b) + c));
47 assert((a + (b + c)) == ((a + c) + b));
48 assert((a * (b * c)) == ((a * b) * c));
49 assert((a * (b * c)) == ((c * a) * b));
50 assert((a * (b + c)) == ((a * b) + (a * c)));
51 assert(((a - b) + b) == a);
52 assert(((a + b) - b) == a);
53 assert(((a * b) / b) == a);
54 assert(((a * b) / a) == b);
55 assert(((a / b) / a) == (1/b));
56
57 multi_bigmod d, d2;
58
59 negate(d, a);
60 assert(d == (-a));
61 add(d, b, a);
62 assert((a + b) == d);
63 subtract(d, a , b);
64 assert((a + (-b)) == d);
65 negate(d, b);
66 assert((a + d) == (b - a+2*a - 2*b));
67 d.assign(a); d.multiply_by_2();
68 assert((a + a) == d);
69 multiply(d, a, b);
70 assert(d == (b * a));
71 square(d, a); multiply(d2, a , a);
72 assert(d == d2);
73 d.assign(b); d.negate(); multiply(d, a, d);
74 assert(d == -(a * b));
75 divide(d, a, b);
76 assert((a / (-b)) == -d);
77 add(d, b, c); multiply(d, a, d);
78 assert(d == ((a * b) + (a * c)));
79 d = b;
80 d.invert();
81 assert(((a / b) / a) == d);
82 }
83
84
85
86 void
utiltest(multi_bigmod & a)87 utiltest (multi_bigmod & a)
88 {
89 multi_bigmod b, c;
90 multi_bigmod x, y;
91
92 x.set_modulus (a.modulus());
93 x = 1;
94 y.set_modulus (a.modulus());
95 y = 1;
96
97 int i;
98 for (i = 0; i < 10; ++i) {
99 power(b, a, i);
100 assert(b == x);
101 x *= a;
102 y = a * y;
103 assert(y == x);
104 }
105 x.assign_one();
106 assert(x.is_one());
107
108 invert(c, a);
109
110 for (i = 0; i > -10; --i) {
111 power(b, a, i);
112 assert(b == x);
113 x *= c;
114 }
115 }
116
117
118
119 void
accumtest(multi_bigmod & a,multi_bigmod & b,multi_bigmod & c)120 accumtest (multi_bigmod & a, multi_bigmod & b, multi_bigmod & c)
121 {
122 multi_bigmod x = a;
123 x *= b;
124 assert(x == (b * a));
125 x += c;
126 assert(x == (c+(b * a)));
127 x -= a;
128 assert(x == (-a + c + (b * a)));
129 x /= b;
130 assert(x == (((b *a) -a + c) / b));
131
132 x.assign(a);
133 assert(x == a);
134 multiply(x, x, b);
135 assert(x == (b * a));
136 add(x, x, c);
137 assert(x == (c+(b * a)));
138 subtract(x, x, a);
139 assert(x == (-a + c + (b * a)));
140 divide(x, x, b);
141 assert(x == (((b *a) -a + c) / b));
142 }
143
144
145
146 void
longidentitytest(multi_bigmod & a,long b,long c)147 longidentitytest (multi_bigmod& a, long b, long c)
148 {
149 assert((a + b) == (b + a));
150 assert((a + (-b)) == (a - b));
151 assert((a * b) == (b * a));
152 assert((a * (-b)) == -(a * b));
153 assert((a / (-b)) == -(a / b));
154 assert((a - b) == -(b - a));
155 assert((a + (b + c)) == ((a + b) + c));
156 assert((a + (b + c)) == ((c + a) + b));
157 assert((a * (b + c)) == ((a * b) + (a * c)));
158 assert(((a - b) + b) == a);
159 assert(((a + b) - b) == a);
160 assert(((a * b) / b) == a);
161 assert((b * (a / b)) == a);
162
163 multi_bigmod d;
164
165 negate(d, a);
166 assert(-(d) == a);
167 add(d, a, b);
168 assert((a + b) == d);
169 subtract(d, a , b);
170 assert((a + (-b)) == d);
171 negate(d, multi_bigmod(b, d.modulus()));
172 assert((a + d) == (b - a+2*a - 2*b));
173 d.assign(a); d.multiply_by_2();
174 assert((a + a) == d);
175 multiply(d, a, b);
176 assert(d == (b * a));
177 d.set_mantissa(b); d.negate(); multiply(d, a, d);
178 assert(d == -(a * b));
179 divide(d, a, b);
180 assert((a / (-b)) == -d);
181 add(d, multi_bigmod(c, a.modulus()), b); multiply(d, a, d);
182 assert(d == ((a * b) + (a * c)));
183 add(d, multi_bigmod(b, a.modulus()), c); multiply(d, a, d);
184 assert(d == ((a * b) + (a * c)));
185
186 bigint h;
187
188 d = b; h = d.invert(1);
189 assert((multi_bigmod(1, d.modulus()) / multi_bigmod(b, d.modulus())) == d);
190 assert(((a / b) / a) == d);
191 }
192
193
194
195 void
longaccumtest(multi_bigmod & a,long b,long c)196 longaccumtest (multi_bigmod & a, long b, long c)
197 {
198 multi_bigmod x = a;
199 x *= b;
200 assert(x == (a * b));
201 x += c;
202 assert(x == ((a * b) + c));
203 x -= a;
204 assert(x == (((a * b) + c) - a));
205 x /= b;
206 assert(x == ((((a * b) + c) - a) / b));
207
208 x.assign(a);
209 assert(x == a);
210 multiply(x, x, b);
211 assert(x == (a * b));
212 add(x, x, c);
213 assert(x == ((a * b) + c));
214 subtract(x, x, a);
215 assert(x == (((a * b) + c) - a));
216 divide(x, x, b);
217 assert(x == ((((a * b) + c) - a) / b));
218 }
219
220
221
222 void
anothertest(bigint m)223 anothertest (bigint m)
224 {
225 multi_bigmod pow64;
226 pow64.set_modulus(m);
227
228 multi_bigmod two(2, m);
229 power(pow64, two, 64);
230
231 multi_bigmod s64(1, m);
232
233 power(s64, two, 65);
234 divide(s64, s64, 2);
235
236 assert(s64 == pow64);
237 assert(!(s64 != pow64));
238
239 multi_bigmod s32;
240 power(s32, two, 32);
241 assert(!(pow64 == s32));
242 assert(pow64 != s32);
243
244 identitytest(s64, s32, pow64);
245 accumtest(pow64, s32, pow64);
246 utiltest(s32);
247 longidentitytest(s64, 1000, 50);
248 longaccumtest(s32, 100000, 11);
249 }
250
251
252
253 void
iotest()254 iotest ()
255 {
256 multi_bigmod result;
257
258 std::cout << "\n please, enter an multi_bigmod (format: (mantissa, modulus)): ";
259 std::cin >> result;
260 std::cout << "number = ->" << result << " < -\n";
261
262 char * string = new char[1000];
263
264 multi_bigmod_to_string(result, string);
265 std::cout << "\n multi_bigmod_to_string:->" << string << " < - \n";
266
267 result.assign_zero();
268 result.set_modulus(bigint(1));
269
270 string_to_multi_bigmod(string, result);
271 std::cout << " string_to_multi_bigmod:->" << result << " < - \n\n";
272 std::cout.flush();
273
274 FILE *fp;
275
276 fp = fopen("test.txt", "w");
277
278 int i;
279 for (i = 0; i < 10; i++) {
280 inc(result);
281 result.print_to_file(fp);
282 }
283 fclose (fp);
284
285 fp = fopen("test.txt", "r");
286
287 while (!feof(fp)) {
288 result.scan_from_file(fp);
289 }
290 fclose(fp);
291 std::remove("test.txt");
292 }
293
294
295
296 void
bigmod_and_multi_bigmod(bigint m)297 bigmod_and_multi_bigmod (bigint m)
298 {
299 bigmod::set_modulus(m);
300 bigint m1, m2;
301
302 bigmod a, b;
303 multi_bigmod c, d;
304
305 m1 = randomize(m);
306 m2 = randomize(m);
307
308 a.assign(m1);
309 b.assign(m2);
310
311 c.set_modulus(m);
312 c.set_mantissa(m1);
313
314 d.assign(m2, m);
315
316 assert(a == c);
317 assert(b == d);
318 assert(a+d == b+c);
319
320 assert(b-a == b-c);
321 assert(b*a == b*c);
322 assert(b/a == b/c);
323
324 assert(a-b == c-b);
325 assert(a*b == c*b);
326 assert(a/b == c/b);
327
328 d = c = a;
329 assert(a == d);
330
331 d += a;
332 c += c;
333 assert(c == d);
334
335 d = c = a;
336 d -= a;
337 c -= a;
338 assert(c == d);
339
340 d = c = a;
341 d *= a;
342 c *= c;
343 assert(c == d);
344
345 d = c = a;
346 d /= a;
347 c /= c;
348 assert(c == d);
349 }
350
351
352
353 void
multi_bigmod_moduli(bigint m)354 multi_bigmod_moduli (bigint m)
355 {
356 multi_bigmod a(m, m);
357 multi_bigmod b(m+bigint(1), m);
358
359 multi_bigmod c(bigint(1), m+bigint(1));
360 multi_bigmod d(bigint(1), m+bigint(1));
361
362 multi_bigmod g(m, m);
363
364 multi_bigmod e(bigint(2), m+bigint(2));
365 multi_bigmod f(bigint(2), m+bigint(2));
366
367 multi_bigmod h(m, m);
368 multi_bigmod i;
369
370
371 assert(a.is_zero());
372 assert(g.is_zero());
373 assert(h.is_zero());
374 assert(b.is_one());
375 assert(c.is_one());
376 assert(d.is_one());
377
378 assert(a == g);
379 assert(c == d);
380 assert(e == f);
381
382 assert(a+b+multi_bigmod(bigint(2), m) == multi_bigmod(bigint(3), m));
383 assert(c+d == c + multi_bigmod(bigint(1), m+bigint(1)));
384 assert(e+f == f + multi_bigmod(bigint(2), m+bigint(2)));
385
386 i.set_modulus(h);
387 i.set_mantissa(h.mantissa());
388 assert(h == i);
389 }
390
391
392
393 void
all_test(bigint m)394 all_test (bigint m)
395 {
396 random_generator rg;
397 multi_bigmod a, b;
398 long x, y;
399
400 a.randomize(multi_bigmod(m - multi_bigmod(1, m)));
401 b.randomize(a);
402
403 rg >> x >> y;
404 x %= 10000000;
405 y %= 1000000;
406
407 utiltest(a);
408 identitytest(a, b, b);
409 identitytest(a, a, b);
410
411 accumtest(a, a, b);
412 accumtest(b, a, b);
413
414 utiltest(a);
415 utiltest(b);
416
417 longidentitytest(a, x, y);
418 longidentitytest(b, x, x);
419
420 longaccumtest(b, x, y);
421 longaccumtest(a, x, x);
422 bigmod_and_multi_bigmod(m);
423 multi_bigmod_moduli(m);
424 }
425
426
427
main_LiDIA(int,char **)428 int main_LiDIA (int, char**)
429 {
430 bigint modul;
431
432 bigint::seed(234534);
433
434 power(modul, bigint(10), 20);
435
436 modul = randomize(modul);
437
438 while (!is_prime(modul, 5)) {
439 inc(modul);
440 }
441
442 std::cout << "\n Modul " << modul << " (prime number) \n";
443
444 multi_bigmod one (1, modul);
445 multi_bigmod two (2, modul);
446 multi_bigmod n (0, modul);
447 assert(n.is_zero());
448
449 assert(one == multi_bigmod(1, modul));
450 assert(two == multi_bigmod((1+1), modul));
451
452 assert(n.is_zero());
453 anothertest(modul);
454 iotest();
455
456 int j;
457 for (j = 0; j < 10; j++) {
458 all_test(modul);
459 std::cout << "\n " << (j+1) << "th test succeeded ";
460 std::cout.flush();
461 }
462
463
464 std::cout << "\nEnd of multi_bigmod_appl\n";
465 return 0;
466 }
467
468
main(int argc,char ** argv)469 int main(int argc, char** argv) {
470
471 #if defined(LIDIA_EXCEPTIONS)
472 try {
473 #endif
474
475 main_LiDIA(argc, argv);
476
477 #if defined(LIDIA_EXCEPTIONS)
478 }
479 catch(basic_error const& ex) {
480 ex.traditional_error_handler();
481 return 1;
482 }
483 catch(std::exception const& ex) {
484 std::cerr << "unexpected exception: " << ex.what() << "\n";
485 return 1;
486 }
487 #endif
488
489 }
490