1 /*
2 Copyright (C) 2011 Sebastian Pancratz
3 Copyright (C) 2012 Andres Goens
4 Copyright (C) 2013 Mike Hansen
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 <http://www.gnu.org/licenses/>.
12 */
13
14 #ifndef FQ_H
15 #define FQ_H
16
17 #ifdef FQ_INLINES_C
18 #define FQ_INLINE FLINT_DLL
19 #define FQ_TEMPLATES_INLINE FLINT_DLL
20 #else
21 #define FQ_INLINE static __inline__
22 #define FQ_TEMPLATES_INLINE static __inline__
23 #endif
24
25 #include "fmpz_mod_poly.h"
26 #include "fmpz_mod_mat.h"
27 #include "ulong_extras.h"
28
29 /* Data types and context ****************************************************/
30
31 #ifdef __cplusplus
32 extern "C" {
33 #endif
34
35 typedef fmpz_poly_t fq_t;
36 typedef fmpz_poly_struct fq_struct;
37
38 typedef struct
39 {
40 fmpz p;
41
42 int sparse_modulus;
43
44 fmpz *a;
45 slong *j;
46 slong len;
47
48 fmpz_mod_poly_t modulus;
49 fmpz_mod_poly_t inv;
50
51 char *var;
52 }
53 fq_ctx_struct;
54
55 typedef fq_ctx_struct fq_ctx_t[1];
56
57 FLINT_DLL void fq_ctx_init(fq_ctx_t ctx, const fmpz_t p, slong d, const char *var);
58
59 FLINT_DLL int _fq_ctx_init_conway(fq_ctx_t ctx, const fmpz_t p, slong d, const char *var);
60
61 FLINT_DLL void fq_ctx_init_conway(fq_ctx_t ctx, const fmpz_t p, slong d, const char *var);
62
63 FLINT_DLL void fq_ctx_init_modulus(fq_ctx_t ctx,
64 fmpz_mod_poly_t modulus,
65 const char *var);
66
67 FLINT_DLL void fq_ctx_randtest(fq_ctx_t ctx, flint_rand_t state);
68
69 FLINT_DLL void fq_ctx_randtest_reducible(fq_ctx_t ctx, flint_rand_t state);
70
71 FLINT_DLL void fq_ctx_clear(fq_ctx_t ctx);
72
fq_ctx_modulus(const fq_ctx_t ctx)73 FQ_INLINE const fmpz_mod_poly_struct* fq_ctx_modulus(const fq_ctx_t ctx)
74 {
75 return ctx->modulus;
76 }
77
fq_ctx_degree(const fq_ctx_t ctx)78 FQ_INLINE slong fq_ctx_degree(const fq_ctx_t ctx)
79 {
80 return ctx->modulus->length - 1;
81 }
82
83 #define fq_ctx_prime(ctx) (&((ctx)->p))
84
fq_ctx_order(fmpz_t f,const fq_ctx_t ctx)85 FQ_INLINE void fq_ctx_order(fmpz_t f, const fq_ctx_t ctx)
86 {
87 fmpz_set(f, fq_ctx_prime(ctx));
88 fmpz_pow_ui(f, f, fq_ctx_degree(ctx));
89 }
90
fq_ctx_fprint(FILE * file,const fq_ctx_t ctx)91 FQ_INLINE int fq_ctx_fprint(FILE * file, const fq_ctx_t ctx)
92 {
93 int r;
94
95 r = flint_fprintf(file, "p = ");
96 if (r <= 0)
97 return r;
98
99 r = fmpz_fprint(file, fq_ctx_prime(ctx));
100 if (r <= 0)
101 return r;
102
103 r = flint_fprintf(file, "\nd = %wd\n", fq_ctx_degree(ctx));
104 if (r <= 0)
105 return r;
106
107 r = flint_fprintf(file, "f(X) = ");
108 if (r <= 0)
109 return r;
110
111 r = fmpz_mod_poly_fprint_pretty(file, ctx->modulus, "X");
112 if (r <= 0)
113 return r;
114
115 r = flint_fprintf(file, "\n");
116
117 return r;
118 }
119
fq_ctx_print(const fq_ctx_t ctx)120 FQ_INLINE void fq_ctx_print(const fq_ctx_t ctx)
121 {
122 fq_ctx_fprint(stdout, ctx);
123 }
124
125
126 /* Memory managment *********************************************************/
127
fq_init(fq_t rop,const fq_ctx_t ctx)128 FQ_INLINE void fq_init(fq_t rop, const fq_ctx_t ctx)
129 {
130 fmpz_poly_init(rop);
131 }
132
fq_init2(fq_t rop,const fq_ctx_t ctx)133 FQ_INLINE void fq_init2(fq_t rop, const fq_ctx_t ctx)
134 {
135 fmpz_poly_init2(rop, fq_ctx_degree(ctx));
136 }
137
fq_clear(fq_t rop,const fq_ctx_t ctx)138 FQ_INLINE void fq_clear(fq_t rop, const fq_ctx_t ctx)
139 {
140 fmpz_poly_clear(rop);
141 }
142
143 FQ_INLINE
_fq_sparse_reduce(fmpz * R,slong lenR,const fq_ctx_t ctx)144 void _fq_sparse_reduce(fmpz *R, slong lenR, const fq_ctx_t ctx)
145 {
146 const slong d = ctx->j[ctx->len - 1];
147
148 FMPZ_VEC_NORM(R, lenR);
149
150 if (lenR > d)
151 {
152 slong i, k;
153
154 for (i = lenR - 1; i >= d; i--)
155 {
156 for (k = ctx->len - 2; k >= 0; k--)
157 {
158 fmpz_submul(R + ctx->j[k] + i - d, R + i, ctx->a + k);
159 }
160 fmpz_zero(R + i);
161 }
162 }
163
164 _fmpz_vec_scalar_mod_fmpz(R, R, FLINT_MIN(d, lenR), fq_ctx_prime(ctx));
165 }
166
_fq_dense_reduce(fmpz * R,slong lenR,const fq_ctx_t ctx)167 FQ_INLINE void _fq_dense_reduce(fmpz* R, slong lenR, const fq_ctx_t ctx)
168 {
169 fmpz *q, *r;
170
171 if (lenR < ctx->modulus->length)
172 {
173 _fmpz_vec_scalar_mod_fmpz(R, R, lenR, fq_ctx_prime(ctx));
174 return;
175 }
176
177 q = _fmpz_vec_init(lenR - ctx->modulus->length + 1);
178 r = _fmpz_vec_init(ctx->modulus->length - 1);
179
180 _fmpz_mod_poly_divrem_newton_n_preinv(q, r, R, lenR,
181 ctx->modulus->coeffs, ctx->modulus->length,
182 ctx->inv->coeffs, ctx->inv->length,
183 fq_ctx_prime(ctx));
184
185 _fmpz_vec_set(R, r, ctx->modulus->length - 1);
186 _fmpz_vec_clear(q, lenR - ctx->modulus->length + 1);
187 _fmpz_vec_clear(r, ctx->modulus->length - 1);
188
189 }
190
191
_fq_reduce(fmpz * R,slong lenR,const fq_ctx_t ctx)192 FQ_INLINE void _fq_reduce(fmpz* R, slong lenR, const fq_ctx_t ctx)
193 {
194 if (ctx->sparse_modulus)
195 _fq_sparse_reduce(R, lenR, ctx);
196 else
197 _fq_dense_reduce(R, lenR, ctx);
198 }
199
fq_reduce(fq_t rop,const fq_ctx_t ctx)200 FQ_INLINE void fq_reduce(fq_t rop, const fq_ctx_t ctx)
201 {
202 _fq_reduce(rop->coeffs, rop->length, ctx);
203 rop->length = FLINT_MIN(rop->length, ctx->modulus->length - 1);
204 _fmpz_poly_normalise(rop);
205 }
206
207 /* Basic arithmetic **********************************************************/
208
209 FLINT_DLL void fq_add(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx);
210
211 FLINT_DLL void fq_sub(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx);
212
213 FLINT_DLL void fq_sub_one(fq_t rop, const fq_t op1, const fq_ctx_t ctx);
214
215 FLINT_DLL void fq_neg(fq_t rop, const fq_t op1, const fq_ctx_t ctx);
216
217 FLINT_DLL void fq_mul(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx);
218
219 FLINT_DLL void fq_mul_fmpz(fq_t rop, const fq_t op, const fmpz_t x, const fq_ctx_t ctx);
220
221 FLINT_DLL void fq_mul_si(fq_t rop, const fq_t op, slong x, const fq_ctx_t ctx);
222
223 FLINT_DLL void fq_mul_ui(fq_t rop, const fq_t op, ulong x, const fq_ctx_t ctx);
224
225 FLINT_DLL void fq_div(fq_t rop, const fq_t op1, const fq_t op2, const fq_ctx_t ctx);
226
227 FLINT_DLL void fq_sqr(fq_t rop, const fq_t op, const fq_ctx_t ctx);
228
229 FLINT_DLL void fq_inv(fq_t rop, const fq_t op1, const fq_ctx_t ctx);
230
231 FLINT_DLL void fq_gcdinv(fq_t rop, fq_t inv, const fq_t op, const fq_ctx_t ctx);
232
233 FLINT_DLL void _fq_pow(fmpz *rop, const fmpz *op, slong len, const fmpz_t e,
234 const fq_ctx_t ctx);
235
236 FLINT_DLL void fq_pow(fq_t rop, const fq_t op1, const fmpz_t e, const fq_ctx_t ctx);
237
238 FLINT_DLL void fq_pow_ui(fq_t rop, const fq_t op, const ulong e, const fq_ctx_t ctx);
239
240 FLINT_DLL void fq_pth_root(fq_t rop, const fq_t op1, const fq_ctx_t ctx);
241
242 /* Randomisation *************************************************************/
243
244 FLINT_DLL void fq_randtest(fq_t rop, flint_rand_t state, const fq_ctx_t ctx);
245
246 FLINT_DLL void fq_randtest_dense(fq_t rop, flint_rand_t state, const fq_ctx_t ctx);
247
248 FLINT_DLL void fq_randtest_not_zero(fq_t rop, flint_rand_t state, const fq_ctx_t ctx);
249
250 FLINT_DLL void fq_rand(fq_t rop, flint_rand_t state, const fq_ctx_t ctx);
251
252
253 /* Comparison ****************************************************************/
254
fq_equal(const fq_t op1,const fq_t op2,const fq_ctx_t ctx)255 FQ_INLINE int fq_equal(const fq_t op1, const fq_t op2, const fq_ctx_t ctx)
256 {
257 return fmpz_poly_equal(op1, op2);
258 }
259
fq_is_zero(const fq_t op,const fq_ctx_t ctx)260 FQ_INLINE int fq_is_zero(const fq_t op, const fq_ctx_t ctx)
261 {
262 return fmpz_poly_is_zero(op);
263 }
264
fq_is_one(const fq_t op,const fq_ctx_t ctx)265 FQ_INLINE int fq_is_one(const fq_t op, const fq_ctx_t ctx)
266 {
267 return fmpz_poly_is_one(op);
268 }
269
270 FLINT_DLL int fq_is_invertible(const fq_t op, const fq_ctx_t ctx);
271
272 /* Assignments and conversions ***********************************************/
273
fq_set(fq_t rop,const fq_t op,const fq_ctx_t ctx)274 FQ_INLINE void fq_set(fq_t rop, const fq_t op, const fq_ctx_t ctx)
275 {
276 fmpz_poly_set(rop, op);
277 }
278
fq_set_fmpz(fq_t rop,const fmpz_t x,const fq_ctx_t ctx)279 FQ_INLINE void fq_set_fmpz(fq_t rop, const fmpz_t x, const fq_ctx_t ctx)
280 {
281 fmpz_poly_set_fmpz(rop, x);
282 fq_reduce(rop, ctx);
283 }
284
fq_set_ui(fq_t rop,const ulong x,const fq_ctx_t ctx)285 FQ_INLINE void fq_set_ui(fq_t rop, const ulong x, const fq_ctx_t ctx)
286 {
287 fmpz_poly_set_ui(rop, x);
288 fq_reduce(rop, ctx);
289 }
290
fq_set_si(fq_t rop,const slong x,const fq_ctx_t ctx)291 FQ_INLINE void fq_set_si(fq_t rop, const slong x, const fq_ctx_t ctx)
292 {
293 fmpz_poly_set_si(rop, x);
294 fq_reduce(rop, ctx);
295 }
296
fq_swap(fq_t op1,fq_t op2,const fq_ctx_t ctx)297 FQ_INLINE void fq_swap(fq_t op1, fq_t op2, const fq_ctx_t ctx)
298 {
299 fmpz_poly_swap(op1, op2);
300 }
301
fq_zero(fq_t rop,const fq_ctx_t ctx)302 FQ_INLINE void fq_zero(fq_t rop, const fq_ctx_t ctx)
303 {
304 fmpz_poly_zero(rop);
305 }
306
fq_one(fq_t rop,const fq_ctx_t ctx)307 FQ_INLINE void fq_one(fq_t rop, const fq_ctx_t ctx)
308 {
309 fmpz_poly_one(rop);
310 }
311
fq_gen(fq_t rop,const fq_ctx_t ctx)312 FQ_INLINE void fq_gen(fq_t rop, const fq_ctx_t ctx)
313 {
314 if (ctx->modulus->length == 2)
315 {
316 fmpz_poly_fit_length(rop, 1);
317 fmpz_invmod(rop->coeffs, ctx->modulus->coeffs + 1, fq_ctx_prime(ctx));
318 fmpz_neg(rop->coeffs, rop->coeffs);
319 fmpz_mul(rop->coeffs, rop->coeffs, ctx->modulus->coeffs);
320 fmpz_mod(rop->coeffs, rop->coeffs, fq_ctx_prime(ctx));
321 }
322 else
323 {
324 fmpz_poly_zero(rop);
325 fmpz_poly_set_coeff_ui(rop, 0, 0);
326 fmpz_poly_set_coeff_ui(rop, 1, 1);
327 }
328 }
329
330 /* Output ********************************************************************/
331
332 FQ_INLINE
fq_fprint(FILE * file,const fq_t op,const fq_ctx_t ctx)333 int fq_fprint(FILE * file, const fq_t op, const fq_ctx_t ctx)
334 {
335 return fmpz_poly_fprint(file, op);
336 }
337
338 FQ_INLINE
fq_print(const fq_t op,const fq_ctx_t ctx)339 void fq_print(const fq_t op, const fq_ctx_t ctx)
340 {
341 fmpz_poly_print(op);
342 }
343
344 FQ_INLINE
fq_fprint_pretty(FILE * file,const fq_t op,const fq_ctx_t ctx)345 int fq_fprint_pretty(FILE * file, const fq_t op, const fq_ctx_t ctx)
346 {
347 return fmpz_poly_fprint_pretty(file, op, ctx->var);
348 }
349
350 FQ_INLINE
fq_print_pretty(const fq_t op,const fq_ctx_t ctx)351 int fq_print_pretty(const fq_t op, const fq_ctx_t ctx)
352 {
353 return fmpz_poly_print_pretty(op, ctx->var);
354 }
355
356 FLINT_DLL char * fq_get_str(const fq_t op, const fq_ctx_t ctx);
357
358 FLINT_DLL char * fq_get_str_pretty(const fq_t op, const fq_ctx_t ctx);
359
360 /* Special functions *********************************************************/
361
362 FLINT_DLL void _fq_trace(fmpz_t rop, const fmpz *op, slong len, const fq_ctx_t ctx);
363
364 FLINT_DLL void fq_trace(fmpz_t rop, const fq_t op, const fq_ctx_t ctx);
365
366 FLINT_DLL void _fq_frobenius(fmpz *rop, const fmpz *op, slong len, slong e,
367 const fq_ctx_t ctx);
368
369 FLINT_DLL void fq_frobenius(fq_t rop, const fq_t op, slong e, const fq_ctx_t ctx);
370
371 FLINT_DLL void _fq_norm(fmpz_t rop, const fmpz *op, slong len, const fq_ctx_t ctx);
372
373 FLINT_DLL void fq_norm(fmpz_t rop, const fq_t op, const fq_ctx_t ctx);
374
375
376 /* Bit packing ******************************************************/
377
378 FLINT_DLL void fq_bit_pack(fmpz_t f, const fq_t op, flint_bitcnt_t bit_size,
379 const fq_ctx_t ctx);
380
381 FLINT_DLL void fq_bit_unpack(fq_t rop, const fmpz_t f, flint_bitcnt_t bit_size,
382 const fq_ctx_t ctx);
383
384 /* Inlines *******************************************************************/
385
386 FLINT_DLL void __fq_ctx_prime(fmpz_t p, fq_ctx_t ctx);
387
388 #ifdef T
389 #undef T
390 #endif
391
392 #define T fq
393 #define CAP_T FQ
394 #define B fmpz_mod
395 #include "fq_templates.h"
396 #undef B
397 #undef CAP_T
398 #undef T
399
400 #ifdef __cplusplus
401 }
402 #endif
403
404 #endif
405
406