1 /*
2 Copyright (C) 2009, 2016 William Hart
3
4 This file is part of FLINT.
5
6 FLINT is free software: you can redistribute it and/or modify it under
7 the terms of the GNU Lesser General Public License (LGPL) as published
8 by the Free Software Foundation; either version 2.1 of the License, or
9 (at your option) any later version. See <http://www.gnu.org/licenses/>.
10 */
11
12 #include <gmp.h>
13 #include "flint.h"
14 #include "ulong_extras.h"
15 #include "long_extras.h"
16
17 int
main(void)18 main(void)
19 {
20 int i, result;
21 FLINT_TEST_INIT(state);
22
23 flint_printf("powmod2_preinv....");
24 fflush(stdout);
25
26 for (i = 0; i < 10000 * flint_test_multiplier(); i++)
27 {
28 ulong a, d, r1, r2, dinv;
29 mpz_t a_m, d_m, r2_m;
30 slong exp;
31
32 mpz_init(a_m);
33 mpz_init(d_m);
34 mpz_init(r2_m);
35
36 d = n_randtest_not_zero(state);
37 do
38 {
39 a = n_randtest(state);
40 } while (n_gcd(d, a) != 1);
41 exp = z_randtest(state);
42
43 dinv = n_preinvert_limb(d);
44 r1 = n_powmod2_preinv(a, exp, d, dinv);
45
46 flint_mpz_set_ui(a_m, a);
47 flint_mpz_set_ui(d_m, d);
48 if (exp < 0)
49 {
50 flint_mpz_powm_ui(r2_m, a_m, -exp, d_m);
51 mpz_invert(r2_m, r2_m, d_m);
52 }
53 else
54 flint_mpz_powm_ui(r2_m, a_m, exp, d_m);
55 r2 = flint_mpz_get_ui(r2_m);
56
57 result = (r1 == r2);
58 if (!result)
59 {
60 flint_printf("FAIL:\n");
61 flint_printf("a = %wu, exp = %wd, d = %wu, dinv = %wu\n", a, exp, d, dinv);
62 flint_printf("r1 = %wu, r2 = %wu\n", r1, r2);
63 abort();
64 }
65
66 mpz_clear(a_m);
67 mpz_clear(d_m);
68 mpz_clear(r2_m);
69 }
70
71 /* check 0^0 = 1 */
72 for (i = 0; i < 10000 * flint_test_multiplier(); i++)
73 {
74 ulong d, r, dinv;
75
76 d = n_randtest_not_zero(state);
77
78 dinv = n_preinvert_limb(d);
79 r = n_powmod2_preinv(0, 0, d, dinv);
80
81 result = (r == 1 || (d == 1 && r == 0));
82 if (!result)
83 {
84 flint_printf("FAIL:\n");
85 flint_printf("0^0 != 1 mod %wd\n", d);
86 abort();
87 }
88 }
89
90 /* check 0^exp = 0 mod 1 */
91 for (i = 0; i < 10000 * flint_test_multiplier(); i++)
92 {
93 ulong r, dinv;
94 slong exp;
95
96 exp = z_randtest(state);
97
98 dinv = n_preinvert_limb(1);
99 r = n_powmod2_preinv(0, exp, 1, dinv);
100
101 result = (r == 0);
102 if (!result)
103 {
104 flint_printf("FAIL:\n");
105 flint_printf("0^%wd != 0 mod 1\n", exp);
106 abort();
107 }
108 }
109
110 FLINT_TEST_CLEANUP(state);
111
112 flint_printf("PASS\n");
113 return 0;
114 }
115