1 /*
2 Copyright (C) 2009 William Hart
3 Copyright (C) 2011 Fredrik Johansson
4 Copyright (C) 2012 Lina Kulakova
5
6 This file is part of FLINT.
7
8 FLINT is free software: you can redistribute it and/or modify it under
9 the terms of the GNU Lesser General Public License (LGPL) as published
10 by the Free Software Foundation; either version 2.1 of the License, or
11 (at your option) any later version. See <https://www.gnu.org/licenses/>.
12 */
13
14 #include <stdio.h>
15 #include <stdlib.h>
16 #include <gmp.h>
17 #include "flint.h"
18 #include "fmpz_vec.h"
19 #include "fmpz_mod_poly.h"
20 #include "ulong_extras.h"
21
22 int
main(void)23 main(void)
24 {
25 int i, result;
26 fmpz_mod_ctx_t ctx;
27 FLINT_TEST_INIT(state);
28
29 flint_printf("powmod_fmpz_binexp....");
30 fflush(stdout);
31
32 fmpz_mod_ctx_init_ui(ctx, 2);
33
34 /* Aliasing of res and a */
35 for (i = 0; i < 25 * flint_test_multiplier(); i++)
36 {
37 fmpz_mod_poly_t a, res, t, f;
38 fmpz_t p;
39 ulong exp;
40 fmpz_t expz;
41
42 fmpz_init(p);
43 fmpz_set_ui(p, n_randtest_prime(state, 0));
44 fmpz_mod_ctx_set_modulus(ctx, p);
45 exp = n_randint(state, 50);
46 fmpz_init_set_ui(expz, exp);
47
48 fmpz_mod_poly_init(a, ctx);
49 fmpz_mod_poly_init(f, ctx);
50 fmpz_mod_poly_init(res, ctx);
51 fmpz_mod_poly_init(t, ctx);
52
53 fmpz_mod_poly_randtest(a, state, n_randint(state, 50), ctx);
54 fmpz_mod_poly_randtest_not_zero(f, state, n_randint(state, 50) + 1, ctx);
55
56 fmpz_mod_poly_powmod_fmpz_binexp(res, a, expz, f, ctx);
57 fmpz_mod_poly_powmod_fmpz_binexp(a, a, expz, f, ctx);
58
59 result = (fmpz_mod_poly_equal(res, a, ctx));
60 if (!result)
61 {
62 flint_printf("FAIL:\n");
63 flint_printf("a:\n"); fmpz_mod_poly_print(a, ctx), flint_printf("\n\n");
64 flint_printf("f:\n"); fmpz_mod_poly_print(f, ctx), flint_printf("\n\n");
65 flint_printf("res:\n"); fmpz_mod_poly_print(res, ctx), flint_printf("\n\n");
66 abort();
67 }
68
69 fmpz_clear(p);
70 fmpz_mod_poly_clear(a, ctx);
71 fmpz_mod_poly_clear(f, ctx);
72 fmpz_mod_poly_clear(res, ctx);
73 fmpz_mod_poly_clear(t, ctx);
74 fmpz_clear(expz);
75 }
76
77 /* Aliasing of res and f */
78 for (i = 0; i < 25 * flint_test_multiplier(); i++)
79 {
80 fmpz_mod_poly_t a, res, t, f;
81 fmpz_t p;
82 ulong exp;
83 fmpz_t expz;
84
85 fmpz_init(p);
86 fmpz_set_ui(p, n_randtest_prime(state, 0));
87 fmpz_mod_ctx_set_modulus(ctx, p);
88 exp = n_randint(state, 50);
89 fmpz_init_set_ui(expz, exp);
90
91 fmpz_mod_poly_init(a, ctx);
92 fmpz_mod_poly_init(f, ctx);
93 fmpz_mod_poly_init(res, ctx);
94 fmpz_mod_poly_init(t, ctx);
95
96 fmpz_mod_poly_randtest(a, state, n_randint(state, 50), ctx);
97 fmpz_mod_poly_randtest_not_zero(f, state, n_randint(state, 50) + 1, ctx);
98
99 fmpz_mod_poly_powmod_fmpz_binexp(res, a, expz, f, ctx);
100 fmpz_mod_poly_powmod_fmpz_binexp(f, a, expz, f, ctx);
101
102 result = (fmpz_mod_poly_equal(res, f, ctx));
103 if (!result)
104 {
105 flint_printf("FAIL:\n");
106 flint_printf("a:\n"); fmpz_mod_poly_print(a, ctx), flint_printf("\n\n");
107 flint_printf("f:\n"); fmpz_mod_poly_print(f, ctx), flint_printf("\n\n");
108 flint_printf("res:\n"); fmpz_mod_poly_print(res, ctx), flint_printf("\n\n");
109 flint_abort();
110 }
111
112 fmpz_clear(p);
113 fmpz_mod_poly_clear(a, ctx);
114 fmpz_mod_poly_clear(f, ctx);
115 fmpz_mod_poly_clear(res, ctx);
116 fmpz_mod_poly_clear(t, ctx);
117 fmpz_clear(expz);
118 }
119
120 /* No aliasing */
121 for (i = 0; i < 50 * flint_test_multiplier(); i++)
122 {
123 fmpz_mod_poly_t a, res1, res2, t, f;
124 fmpz_t p;
125 ulong exp;
126 fmpz_t expz;
127
128 fmpz_init(p);
129 fmpz_set_ui(p, n_randtest_prime(state, 0));
130 fmpz_mod_ctx_set_modulus(ctx, p);
131 exp = n_randint(state, 50);
132
133 fmpz_mod_poly_init(a, ctx);
134 fmpz_mod_poly_init(f, ctx);
135 fmpz_mod_poly_init(res1, ctx);
136 fmpz_mod_poly_init(res2, ctx);
137 fmpz_mod_poly_init(t, ctx);
138
139 fmpz_mod_poly_randtest(a, state, n_randint(state, 50), ctx);
140 fmpz_mod_poly_randtest_not_zero(f, state, n_randint(state, 50) + 1, ctx);
141 fmpz_init_set_ui(expz, exp);
142
143 fmpz_mod_poly_powmod_fmpz_binexp(res1, a, expz, f, ctx);
144 fmpz_mod_poly_powmod_ui_binexp(res2, a, exp, f, ctx);
145
146 result = (fmpz_mod_poly_equal(res1, res2, ctx));
147 if (!result)
148 {
149 flint_printf("FAIL:\n");
150 flint_printf("a:\n"); fmpz_mod_poly_print(a, ctx), flint_printf("\n\n");
151 flint_printf("f:\n"); fmpz_mod_poly_print(f, ctx), flint_printf("\n\n");
152 flint_printf("res1:\n"); fmpz_mod_poly_print(res1, ctx), flint_printf("\n\n");
153 flint_printf("res2:\n"); fmpz_mod_poly_print(res2, ctx), flint_printf("\n\n");
154 flint_abort();
155 }
156
157 fmpz_clear(p);
158 fmpz_mod_poly_clear(a, ctx);
159 fmpz_mod_poly_clear(f, ctx);
160 fmpz_mod_poly_clear(res1, ctx);
161 fmpz_mod_poly_clear(res2, ctx);
162 fmpz_mod_poly_clear(t, ctx);
163 fmpz_clear(expz);
164 }
165
166 /* Check that a^(b+c) = a^b * a^c */
167 for (i = 0; i < 50 * flint_test_multiplier(); i++)
168 {
169 fmpz_mod_poly_t a, res1, res2, res3, res4, t, f;
170 fmpz_t p;
171 fmpz_t exp1, exp2, exp3;
172
173 fmpz_init(p);
174 fmpz_set_ui(p, n_randtest_prime(state, 0));
175 fmpz_mod_ctx_set_modulus(ctx, p);
176
177 fmpz_init(exp1);
178 fmpz_init(exp2);
179 fmpz_randtest(exp1, state, 200);
180 if (fmpz_sgn(exp1) == -1) fmpz_neg(exp1, exp1);
181 fmpz_randtest(exp2, state, 200);
182 if (fmpz_sgn(exp2) == -1) fmpz_neg(exp2, exp2);
183
184 fmpz_mod_poly_init(a, ctx);
185 fmpz_mod_poly_init(f, ctx);
186 fmpz_mod_poly_init(res1, ctx);
187 fmpz_mod_poly_init(res2, ctx);
188 fmpz_mod_poly_init(res3, ctx);
189 fmpz_mod_poly_init(res4, ctx);
190 fmpz_mod_poly_init(t, ctx);
191
192 fmpz_mod_poly_randtest(a, state, n_randint(state, 50), ctx);
193 fmpz_mod_poly_randtest_not_zero(f, state, n_randint(state, 50) + 1, ctx);
194
195 fmpz_mod_poly_powmod_fmpz_binexp(res1, a, exp1, f, ctx);
196 fmpz_mod_poly_powmod_fmpz_binexp(res2, a, exp2, f, ctx);
197 fmpz_mod_poly_mulmod(res4, res1, res2, f, ctx);
198 fmpz_init(exp3);
199 fmpz_add(exp3, exp1, exp2);
200 fmpz_mod_poly_powmod_fmpz_binexp(res3, a, exp3, f, ctx);
201
202 result = (fmpz_mod_poly_equal(res4, res3, ctx));
203 if (!result)
204 {
205 flint_printf("FAIL:\n");
206 flint_printf("a:\n"); fmpz_mod_poly_print(a, ctx), flint_printf("\n\n");
207 flint_printf("f:\n"); fmpz_mod_poly_print(f, ctx), flint_printf("\n\n");
208 flint_printf("res3:\n"); fmpz_mod_poly_print(res3, ctx), flint_printf("\n\n");
209 flint_printf("res4:\n"); fmpz_mod_poly_print(res4, ctx), flint_printf("\n\n");
210 flint_abort();
211 }
212
213 fmpz_clear(p);
214 fmpz_mod_poly_clear(a, ctx);
215 fmpz_mod_poly_clear(f, ctx);
216 fmpz_mod_poly_clear(res1, ctx);
217 fmpz_mod_poly_clear(res2, ctx);
218 fmpz_mod_poly_clear(res3, ctx);
219 fmpz_mod_poly_clear(res4, ctx);
220 fmpz_mod_poly_clear(t, ctx);
221 fmpz_clear(exp1);
222 fmpz_clear(exp2);
223 fmpz_clear(exp3);
224 }
225
226 fmpz_mod_ctx_clear(ctx);
227 FLINT_TEST_CLEANUP(state);
228
229 flint_printf("PASS\n");
230 return 0;
231 }
232