1 /*
2 Copyright (C) 2013 Tom Bachmann
3 Copyright (C) 2020 Daniel Schultz
4
5 This file is part of FLINT.
6
7 FLINT is free software: you can redistribute it and/or modify it under
8 the terms of the GNU Lesser General Public License (LGPL) as published
9 by the Free Software Foundation; either version 2.1 of the License, or
10 (at your option) any later version. See <https://www.gnu.org/licenses/>.
11 */
12
13 #ifndef FMPZ_MOD_POLYXX_H
14 #define FMPZ_MOD_POLYXX_H
15
16 #include "fmpz_mod_poly.h"
17
18 #include "fmpzxx.h"
19 #include "fmpz_polyxx.h"
20 #include "nmod_polyxx.h"
21
22 #include "flintxx/expression.h"
23 #include "flintxx/flint_classes.h"
24 #include "flintxx/flint_exception.h"
25 #include "flintxx/frandxx.h"
26 #include "flintxx/ltuple.h"
27 #include "flintxx/stdmath.h"
28 #include "flintxx/vector.h"
29
30
31 namespace flint {
32
33 ///////////////////////////////////////////////////////////////////////////////
34 // fmpz_mod_ctx_struct wrappers
35 ///////////////////////////////////////////////////////////////////////////////
36
37 class fmpz_modxx_ctx
38 {
39 private:
40 mutable fmpz_mod_ctx_t ctx;
41
42 public:
_ctx()43 fmpz_mod_ctx_t& _ctx() const {return ctx;}
44
modulus()45 fmpzxx_ref modulus() {return fmpzxx_ref::make(ctx->n);}
modulus()46 fmpzxx_srcref modulus() const {return fmpzxx_srcref::make(ctx->n);}
47
fmpz_modxx_ctx(fmpzxx_srcref p)48 fmpz_modxx_ctx(fmpzxx_srcref p)
49 {
50 fmpz_mod_ctx_init(ctx, p._fmpz());
51 }
52
fmpz_modxx_ctx(ulong p)53 fmpz_modxx_ctx(ulong p)
54 {
55 fmpz_mod_ctx_init_ui(ctx, p);
56 }
57
~fmpz_modxx_ctx()58 ~fmpz_modxx_ctx() {fmpz_mod_ctx_clear(ctx);}
59
set_modulus(fmpzxx_srcref p)60 void set_modulus(fmpzxx_srcref p)
61 {
62 fmpz_mod_ctx_set_modulus(ctx, p._fmpz());
63 }
64
set_modulus(ulong p)65 void set_modulus(ulong p)
66 {
67 fmpz_mod_ctx_set_modulus_ui(ctx, p);
68 }
69 };
70
71 class fmpz_modxx_ctx_srcref
72 {
73 private:
74 mutable fmpz_mod_ctx_struct* ctx;
75
fmpz_modxx_ctx_srcref(fmpz_mod_ctx_struct * c)76 fmpz_modxx_ctx_srcref(fmpz_mod_ctx_struct* c) : ctx(c) {}
77
78 public:
_ctx()79 fmpz_mod_ctx_struct* _ctx() const {return ctx;}
80
modulus()81 fmpzxx_ref modulus() {return fmpzxx_ref::make(ctx->n);}
modulus()82 fmpzxx_srcref modulus() const {return fmpzxx_srcref::make(ctx->n);}
83
fmpz_modxx_ctx_srcref(fmpz_modxx_ctx & c)84 fmpz_modxx_ctx_srcref(fmpz_modxx_ctx& c)
85 : ctx(c._ctx()) {}
86
fmpz_modxx_ctx_srcref(const fmpz_modxx_ctx & c)87 fmpz_modxx_ctx_srcref(const fmpz_modxx_ctx& c)
88 : ctx(c._ctx()) {}
89
make(fmpz_mod_ctx_struct * c)90 static fmpz_modxx_ctx_srcref make(fmpz_mod_ctx_struct* c)
91 {return fmpz_modxx_ctx_srcref(c);}
92 };
93
94 namespace traits {
95 template<class T> struct has_fmpz_modxx_ctx : mp::false_ { };
96
97 template<class T> struct is_fmpz_mod_expr
98 : has_fmpz_modxx_ctx<typename tools::evaluation_helper<T>::type> { };
99 } // traits
100
101 namespace detail {
102 struct has_fmpz_modxx_ctx_predicate
103 {
104 template<class T> struct type : traits::has_fmpz_modxx_ctx<T> { };
105 };
106 } // detail
107
108 namespace tools {
109 template<class Expr>
find_fmpz_modxx_ctx(const Expr & e)110 fmpz_modxx_ctx_srcref find_fmpz_modxx_ctx(const Expr& e)
111 {
112 return tools::find_subexpr<detail::has_fmpz_modxx_ctx_predicate>(e).get_ctx();
113 }
114 } // tools
115
116 namespace detail {
117
118 template<class T, class U>
119 struct fakemodtemplate : mp::enable_if<mp::equal_types<T, U> > { };
120 } // detail
121
122
123 ///////////////////////////////////////////////////////////////////////////////
124 // fmpz_mod_poly_struct wrappers
125 ///////////////////////////////////////////////////////////////////////////////
126
127 FLINT_DEFINE_BINOP(divrem_f)
FLINT_DEFINE_BINOP(gcd_euclidean_f)128 FLINT_DEFINE_BINOP(gcd_euclidean_f)
129 FLINT_DEFINE_BINOP(gcd_f)
130 FLINT_DEFINE_BINOP(radix)
131
132 FLINT_DEFINE_UNOP(fmpz_mod_polyxx_lead) // TODO standardise?
133 FLINT_DEFINE_BINOP(fmpz_mod_polyxx_get_coeff) // TODO standardise?
134
135 namespace detail {
136 template<class Poly>
137 struct fmpz_mod_poly_traits
138 {
139 typedef FLINT_UNOP_BUILD_RETTYPE(
140 fmpz_mod_polyxx_lead, fmpzxx, Poly) lead_ref_t;
141 typedef lead_ref_t lead_srcref_t;
142 static lead_ref_t lead(const Poly& p) {return fmpz_mod_polyxx_lead(p);}
143 };
144 } //detail
145
146 template<class Operation, class Data>
147 class fmpz_mod_polyxx_expression
148 : public expression<derived_wrapper<fmpz_mod_polyxx_expression>,
149 Operation, Data>
150 {
151 public:
152 typedef expression<derived_wrapper< ::flint::fmpz_mod_polyxx_expression>,
153 Operation, Data> base_t;
154 typedef detail::fmpz_mod_poly_traits<fmpz_mod_polyxx_expression>
155 poly_traits_t;
156
157 FLINTXX_DEFINE_BASICS(fmpz_mod_polyxx_expression)
FLINTXX_DEFINE_CTORS(fmpz_mod_polyxx_expression)158 FLINTXX_DEFINE_CTORS(fmpz_mod_polyxx_expression)
159 FLINTXX_DEFINE_C_REF(fmpz_mod_polyxx_expression, fmpz_mod_poly_struct, _poly)
160
161 public:
162
163 fmpz_modxx_ctx_srcref get_ctx() const {return this->_data().ctx;}
_ctx()164 fmpz_mod_ctx_struct* _ctx() const {return get_ctx()._ctx();}
165
estimate_ctx()166 fmpz_modxx_ctx_srcref estimate_ctx() const {
167 return tools::find_fmpz_modxx_ctx(*this);}
168
zero(fmpz_modxx_ctx_srcref ctx)169 static fmpz_mod_polyxx_expression zero(fmpz_modxx_ctx_srcref ctx)
170 {
171 return fmpz_mod_polyxx_expression(ctx);
172 }
173
one(fmpz_modxx_ctx_srcref ctx)174 static fmpz_mod_polyxx_expression one(fmpz_modxx_ctx_srcref ctx)
175 {
176 fmpz_mod_polyxx_expression res(ctx);
177 res.set_one();
178 return res;
179 }
180
181 // Create a temporary. The context will be estimated.
create_temporary()182 evaluated_t create_temporary() const
183 {
184 return evaluated_t(estimate_ctx());
185 }
186
randtest(fmpz_modxx_ctx_srcref ctx,frandxx & state,slong len)187 static fmpz_mod_polyxx_expression randtest(
188 fmpz_modxx_ctx_srcref ctx, frandxx& state, slong len)
189 {
190 fmpz_mod_polyxx_expression res(ctx);
191 fmpz_mod_poly_randtest(res._poly(), state._data(), len, ctx._ctx());
192 return res;
193 }
194
randtest_irreducible(fmpz_modxx_ctx_srcref ctx,frandxx & state,slong len)195 static fmpz_mod_polyxx_expression randtest_irreducible(
196 fmpz_modxx_ctx_srcref ctx, frandxx& state, slong len)
197 {
198 fmpz_mod_polyxx_expression res(ctx);
199 fmpz_mod_poly_randtest_irreducible(res._poly(), state._data(), len, ctx._ctx());
200 return res;
201 }
202
randtest_not_zero(fmpz_modxx_ctx_srcref ctx,frandxx & state,slong len)203 static fmpz_mod_polyxx_expression randtest_not_zero(
204 fmpz_modxx_ctx_srcref ctx, frandxx& state, slong len)
205 {
206 fmpz_mod_polyxx_expression res(ctx);
207 fmpz_mod_poly_randtest_not_zero(res._poly(), state._data(), len, ctx._ctx());
208 return res;
209 }
210
211 // These only make sense with immediates
modulus()212 fmpzxx_srcref modulus() const {return get_ctx().modulus();}
213
214 // These only make sense with target immediates
realloc(slong alloc)215 void realloc(slong alloc) {fmpz_mod_poly_realloc(_poly(), alloc, _ctx());}
fit_length(slong len)216 void fit_length(slong len) {fmpz_mod_poly_fit_length(_poly(), len, _ctx());}
_normalise()217 void _normalise() {_fmpz_mod_poly_normalise(_poly());}
set_coeff(slong n,ulong c)218 void set_coeff(slong n, ulong c) {fmpz_mod_poly_set_coeff_ui(_poly(), n, c, _ctx());}
219 template<class Fmpz>
220 typename mp::enable_if<traits::is_fmpzxx<Fmpz> >::type
set_coeff(slong j,const Fmpz & c)221 set_coeff(slong j, const Fmpz& c)
222 {
223 fmpz_mod_poly_set_coeff_fmpz(_poly(), j, c.evaluate()._fmpz(), _ctx());
224 }
truncate(slong n)225 void truncate(slong n) {fmpz_mod_poly_truncate(_poly(), n, _ctx());}
zero_coeffs(slong i,slong j)226 void zero_coeffs(slong i, slong j) {fmpz_mod_poly_zero_coeffs(_poly(), i, j, _ctx());}
227
set_randtest(frandxx & state,slong len)228 void set_randtest(frandxx& state, slong len)
229 {fmpz_mod_poly_randtest(_poly(), state._data(), len, _ctx());}
set_randtest_irreducible(frandxx & state,slong len)230 void set_randtest_irreducible(frandxx& state, slong len)
231 {fmpz_mod_poly_randtest_irreducible(_poly(), state._data(), len, _ctx());}
set_randtest_not_zero(frandxx & state,slong len)232 void set_randtest_not_zero(frandxx& state, slong len)
233 {fmpz_mod_poly_randtest_not_zero(_poly(), state._data(), len, _ctx());}
234
235 template<class Poly>
remove(const Poly & p)236 slong remove(const Poly& p)
237 {
238 return fmpz_mod_poly_remove(_poly(), p.evaluate()._poly(), _ctx());
239 }
240
set_zero()241 void set_zero() {fmpz_mod_poly_zero(_poly(), _ctx());}
242
243 // unified coefficient access
lead()244 typename poly_traits_t::lead_ref_t lead()
245 {
246 return poly_traits_t::lead(*this);
247 }
lead()248 typename poly_traits_t::lead_srcref_t lead() const
249 {
250 return poly_traits_t::lead(*this);
251 }
252
253 // these cause evaluation
length()254 slong length() const
255 {
256 auto e = this->evaluate();
257 return fmpz_mod_poly_length(e._poly(), e._ctx());
258 }
degree()259 slong degree() const
260 {
261 auto e = this->evaluate();
262 return fmpz_mod_poly_degree(e._poly(), e._ctx());
263 }
is_zero()264 bool is_zero() const
265 {
266 auto e = this->evaluate();
267 return fmpz_mod_poly_is_zero(e._poly(), e._ctx());
268 }
is_one()269 bool is_one() const
270 {
271 auto e = this->evaluate();
272 return fmpz_mod_poly_is_one(e._poly(), e._ctx());
273 }
is_squarefree()274 bool is_squarefree() const
275 {
276 auto e = this->evaluate();
277 return fmpz_mod_poly_is_squarefree(e._poly(), e._ctx());
278 }
is_irreducible()279 bool is_irreducible() const
280 {
281 auto e = this->evaluate();
282 return fmpz_mod_poly_is_irreducible(e._poly(), e._ctx());
283 }
is_irreducible_ddf()284 bool is_irreducible_ddf() const
285 {
286 auto e = this->evaluate();
287 return fmpz_mod_poly_is_irreducible_ddf(e._poly(), e._ctx());
288 }
is_irreducible_rabin()289 bool is_irreducible_rabin() const
290 {
291 auto e = this->evaluate();
292 return fmpz_mod_poly_is_irreducible_rabin(e._poly(), e._ctx());
293 }
294
295 // Lazy members
296 FLINTXX_DEFINE_MEMBER_BINOP_(get_coeff, fmpz_mod_polyxx_get_coeff)
297 FLINTXX_DEFINE_MEMBER_BINOP_(operator(), compeval)
298
299 FLINTXX_DEFINE_MEMBER_UNOP(derivative)
300 FLINTXX_DEFINE_MEMBER_UNOP(invmod)
301 FLINTXX_DEFINE_MEMBER_UNOP(make_monic)
302 FLINTXX_DEFINE_MEMBER_UNOP(sqr)
303
304 FLINTXX_DEFINE_MEMBER_BINOP(compose_divconquer)
305 FLINTXX_DEFINE_MEMBER_BINOP(compose_horner)
306 FLINTXX_DEFINE_MEMBER_BINOP(div_basecase)
307 FLINTXX_DEFINE_MEMBER_BINOP(divrem)
308 FLINTXX_DEFINE_MEMBER_BINOP(divrem_basecase)
309 FLINTXX_DEFINE_MEMBER_BINOP(divrem_divconquer)
310 FLINTXX_DEFINE_MEMBER_BINOP(divrem_f)
311 FLINTXX_DEFINE_MEMBER_BINOP(gcd)
312 FLINTXX_DEFINE_MEMBER_BINOP(gcd_euclidean)
313 FLINTXX_DEFINE_MEMBER_BINOP(gcd_euclidean_f)
314 FLINTXX_DEFINE_MEMBER_BINOP(gcd_f)
315 FLINTXX_DEFINE_MEMBER_BINOP(gcdinv)
316 FLINTXX_DEFINE_MEMBER_BINOP(invmod)
317 FLINTXX_DEFINE_MEMBER_BINOP(inv_series_newton)
318 FLINTXX_DEFINE_MEMBER_BINOP(shift_left)
319 FLINTXX_DEFINE_MEMBER_BINOP(shift_right)
320 FLINTXX_DEFINE_MEMBER_BINOP(pow)
321 FLINTXX_DEFINE_MEMBER_BINOP(radix)
322 FLINTXX_DEFINE_MEMBER_BINOP(rem_basecase)
323 FLINTXX_DEFINE_MEMBER_BINOP(xgcd)
324 FLINTXX_DEFINE_MEMBER_BINOP(xgcd_euclidean)
325
326 FLINTXX_DEFINE_MEMBER_3OP(compose_mod)
327 FLINTXX_DEFINE_MEMBER_3OP(compose_mod_brent_kung)
328 FLINTXX_DEFINE_MEMBER_3OP(compose_mod_horner)
329 FLINTXX_DEFINE_MEMBER_3OP(mullow)
330 FLINTXX_DEFINE_MEMBER_3OP(mulmod)
331 FLINTXX_DEFINE_MEMBER_3OP(powmod_binexp)
332 FLINTXX_DEFINE_MEMBER_3OP(pow_trunc)
333 FLINTXX_DEFINE_MEMBER_3OP(pow_trunc_binexp)
334 };
335
336 namespace detail {
337 struct fmpz_mod_poly_data;
338 }
339
340 typedef fmpz_mod_polyxx_expression<operations::immediate,
341 detail::fmpz_mod_poly_data> fmpz_mod_polyxx;
342 typedef fmpz_mod_polyxx_expression<operations::immediate,
343 flint_classes::ref_data<fmpz_mod_polyxx, fmpz_mod_poly_struct> >
344 fmpz_mod_polyxx_ref;
345 typedef fmpz_mod_polyxx_expression<operations::immediate, flint_classes::srcref_data<
346 fmpz_mod_polyxx, fmpz_mod_polyxx_ref, fmpz_mod_poly_struct> > fmpz_mod_polyxx_srcref;
347
348 namespace traits {
349 template<> struct has_fmpz_modxx_ctx<fmpz_mod_polyxx> : mp::true_ { };
350 template<> struct has_fmpz_modxx_ctx<fmpz_mod_polyxx_ref> : mp::true_ { };
351 template<> struct has_fmpz_modxx_ctx<fmpz_mod_polyxx_srcref> : mp::true_ { };
352 } // traits
353
354 namespace flint_classes {
355 template<>
356 struct ref_data<fmpz_mod_polyxx, fmpz_mod_poly_struct>
357 {
358 typedef void IS_REF_OR_CREF;
359 typedef fmpz_mod_polyxx wrapped_t;
360
361 typedef fmpz_mod_poly_struct* data_ref_t;
362 typedef const fmpz_mod_poly_struct* data_srcref_t;
363
364 fmpz_mod_poly_struct* inner;
365 fmpz_modxx_ctx_srcref ctx;
366
367 template<class T>
368 ref_data(T& o, typename detail::fakemodtemplate<T, fmpz_mod_polyxx>::type* = 0)
369 : inner(o._data().inner), ctx(o._data().ctx) {}
370
371 static ref_data make(fmpz_mod_poly_struct* f, fmpz_modxx_ctx_srcref ctx)
372 {
373 return ref_data(f, ctx);
374 }
375
376 private:
377 ref_data(fmpz_mod_poly_struct* fp, fmpz_modxx_ctx_srcref c) : inner(fp), ctx(c) {}
378 };
379
380 template<class Ref>
381 struct srcref_data<fmpz_mod_polyxx, Ref, fmpz_mod_poly_struct>
382 {
383 typedef void IS_REF_OR_CREF;
384 typedef fmpz_mod_polyxx wrapped_t;
385
386 typedef const fmpz_mod_poly_struct* data_ref_t;
387 typedef const fmpz_mod_poly_struct* data_srcref_t;
388
389 const fmpz_mod_poly_struct* inner;
390 fmpz_modxx_ctx_srcref ctx;
391
392 template<class T>
393 srcref_data(const T& o,
394 typename detail::fakemodtemplate<T, fmpz_mod_polyxx>::type* = 0)
395 : inner(o._data().inner), ctx(o._data().ctx) {}
396 template<class T>
397 srcref_data(T o, typename detail::fakemodtemplate<T, Ref>::type* = 0)
398 : inner(o._data().inner), ctx(o._data().ctx) {}
399
400 static srcref_data make(const fmpz_mod_poly_struct* f, fmpz_modxx_ctx_srcref ctx)
401 {
402 return srcref_data(f, ctx);
403 }
404
405 private:
406 srcref_data(const fmpz_mod_poly_struct* fp, fmpz_modxx_ctx_srcref c)
407 : inner(fp), ctx(c) {}
408 };
409 } // flint_classes
410
411 #define FMPZ_MOD_POLYXX_COND_S FLINTXX_COND_S(fmpz_mod_polyxx)
412 #define FMPZ_MOD_POLYXX_COND_T FLINTXX_COND_T(fmpz_mod_polyxx)
413
414 namespace detail {
415 template<>
416 struct fmpz_mod_poly_traits<fmpz_mod_polyxx_srcref>
417 {
418 typedef fmpzxx_srcref lead_srcref_t;
419 typedef fmpzxx_srcref lead_ref_t;
420
421 template<class P>
422 static lead_srcref_t lead(P p)
423 {return lead_srcref_t::make(fmpz_mod_poly_lead(p._poly(), p._ctx()));}
424 };
425 template<>
426 struct fmpz_mod_poly_traits<fmpz_mod_polyxx_ref>
427 {
428 typedef fmpzxx_ref lead_ref_t;
429 typedef fmpzxx_ref lead_srcref_t;
430
431 template<class P>
432 static lead_ref_t lead(P p)
433 {return lead_ref_t::make(fmpz_mod_poly_lead(p._poly(), p._ctx()));}
434 };
435 template<>
436 struct fmpz_mod_poly_traits<fmpz_mod_polyxx>
437 {
438 typedef fmpzxx_ref lead_ref_t;
439 typedef fmpzxx_srcref lead_srcref_t;
440
441 template<class P>
442 static lead_ref_t lead(P& p)
443 {return lead_ref_t::make(fmpz_mod_poly_lead(p._poly(), p._ctx()));}
444 template<class P>
445 static lead_srcref_t lead(const P& p)
446 {return lead_srcref_t::make(fmpz_mod_poly_lead(p._poly(), p._ctx()));}
447 };
448
449 struct fmpz_mod_poly_data
450 {
451 typedef fmpz_mod_poly_t& data_ref_t;
452 typedef const fmpz_mod_poly_t& data_srcref_t;
453
454 fmpz_modxx_ctx_srcref ctx;
455 fmpz_mod_poly_t inner;
456
457 fmpz_mod_poly_data(fmpz_modxx_ctx_srcref c)
458 : ctx(c)
459 {
460 fmpz_mod_poly_init(inner, ctx._ctx());
461 }
462
463 fmpz_mod_poly_data(fmpz_modxx_ctx_srcref c, slong alloc)
464 : ctx(c)
465 {
466 fmpz_mod_poly_init2(inner, alloc, ctx._ctx());
467 }
468
469 fmpz_mod_poly_data(const fmpz_mod_poly_data& o)
470 : ctx(o.ctx)
471 {
472 fmpz_mod_poly_init2(inner, o.inner->length, ctx._ctx());
473 fmpz_mod_poly_set(inner, o.inner, ctx._ctx());
474 }
475
476 fmpz_mod_poly_data(fmpz_mod_polyxx_srcref c)
477 : ctx(c.get_ctx())
478 {
479 fmpz_mod_poly_init2(inner, c.length(), ctx._ctx());
480 fmpz_mod_poly_set(inner, c._poly(), ctx._ctx());
481 }
482
483 ~fmpz_mod_poly_data() {fmpz_mod_poly_clear(inner, ctx._ctx());}
484 };
485
486 struct is_fmpz_mod_polyxx_predicate
487 {
488 template<class T> struct type : FMPZ_MOD_POLYXX_COND_S<T> { };
489 };
490 } // detail
491
492 namespace traits {
493 template<class T> struct is_fmpz_mod_polyxx : mp::or_<
494 traits::is_T_expr<T, fmpz_mod_polyxx>,
495 flint_classes::is_source<fmpz_mod_polyxx, T> > { };
496 }
497
498 namespace rules {
499
500 FLINT_DEFINE_DOIT_COND2(assignment,
501 FMPZ_MOD_POLYXX_COND_T, FMPZ_MOD_POLYXX_COND_S,
502 fmpz_mod_poly_set(to._poly(), from._poly(), to._ctx()))
503
504 FLINT_DEFINE_DOIT_COND2(assignment,
505 FMPZ_MOD_POLYXX_COND_T, traits::is_unsigned_integer,
506 fmpz_mod_poly_set_ui(to._poly(), from, to._ctx()))
507
508 FLINT_DEFINE_DOIT_COND2(assignment,
509 FMPZ_MOD_POLYXX_COND_T, FMPZXX_COND_S,
510 fmpz_mod_poly_set_fmpz(to._poly(), from._fmpz(), to._ctx()))
511
512 FLINT_DEFINE_DOIT_COND2(assignment,
513 FMPZ_MOD_POLYXX_COND_T, FMPZ_POLYXX_COND_S,
514 fmpz_mod_poly_set_fmpz_poly(to._poly(), from._poly(), to._ctx()))
515
516 FLINTXX_DEFINE_CONVERSION_TMP(fmpz_polyxx, fmpz_mod_polyxx,
517 fmpz_mod_poly_get_fmpz_poly(to._poly(), from._poly(), from._ctx()))
518
519 FLINTXX_DEFINE_SWAP(fmpz_mod_polyxx,
520 fmpz_mod_poly_swap(e1._poly(), e2._poly()))
521
522 FLINTXX_DEFINE_EQUALS(fmpz_mod_polyxx,
523 fmpz_mod_poly_equal(e1._poly(), e2._poly(), e1._ctx()))
524
525 FLINT_DEFINE_BINARY_EXPR_COND2(fmpz_mod_polyxx_get_coeff_op,
526 fmpzxx, FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
527 fmpz_mod_poly_get_coeff_fmpz(to._fmpz(), e1._poly(), e2, e1._ctx()))
528
529 FLINT_DEFINE_PRINT_COND(FMPZ_MOD_POLYXX_COND_S,
530 fmpz_mod_poly_fprint(to, from._poly(), from._ctx()))
531
532 FLINT_DEFINE_PRINT_PRETTY_COND_2(FMPZ_MOD_POLYXX_COND_S, const char*,
533 fmpz_mod_poly_fprint_pretty(to, from._poly(), extra, from._ctx()))
534
535 // be careful with fread as it writes to the possibly shared ctx
536 FLINT_DEFINE_READ_COND(FMPZ_MOD_POLYXX_COND_T,
537 fmpz_mod_poly_fread(from, to._poly(), to._ctx()))
538
539 FLINT_DEFINE_BINARY_EXPR_COND2(plus,
540 fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
541 fmpz_mod_poly_add(to._poly(), e1._poly(), e2._poly(), to._ctx()))
542
543 FLINT_DEFINE_BINARY_EXPR_COND2(minus,
544 fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
545 fmpz_mod_poly_sub(to._poly(), e1._poly(), e2._poly(), to._ctx()))
546
547 FLINT_DEFINE_CBINARY_EXPR_COND2(times,
548 fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S, FMPZXX_COND_S,
549 fmpz_mod_poly_scalar_mul_fmpz(to._poly(), e1._poly(), e2._fmpz(), to._ctx()))
550
551 FLINT_DEFINE_BINARY_EXPR_COND2(times, fmpz_mod_polyxx,
552 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
553 fmpz_mod_poly_mul(to._poly(), e1._poly(), e2._poly(), to._ctx()))
554
555 // TODO expose the temporary
556 FLINT_DEFINE_BINARY_EXPR_COND2(divided_by, fmpz_mod_polyxx,
557 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
558 fmpz_mod_polyxx tmp(to.get_ctx());
559 fmpz_mod_poly_divrem(to._poly(), tmp._poly(), e1._poly(), e2._poly(), to._ctx()))
560
561 FLINT_DEFINE_UNARY_EXPR_COND(negate,
562 fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S,
563 fmpz_mod_poly_neg(to._poly(), from._poly(), to._ctx()))
564
565 FLINT_DEFINE_UNARY_EXPR_COND(fmpz_mod_polyxx_lead_op,
566 fmpzxx, FMPZ_MOD_POLYXX_COND_S,
567 fmpz_set(to._fmpz(), fmpz_mod_poly_lead(from._poly(), from._ctx())))
568
569 FLINT_DEFINE_BINARY_EXPR_COND2(shift_left_op,
570 fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
571 fmpz_mod_poly_shift_left(to._poly(), e1._poly(), e2, to._ctx()))
572
573 FLINT_DEFINE_BINARY_EXPR_COND2(shift_right_op,
574 fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
575 fmpz_mod_poly_shift_right(to._poly(), e1._poly(), e2, to._ctx()))
576
577 FLINT_DEFINE_UNARY_EXPR_COND(make_monic_op,
578 fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S,
579 fmpz_mod_poly_make_monic(to._poly(), from._poly(), to._ctx()))
580
581 FLINT_DEFINE_THREEARY_EXPR_COND3(mullow_op, fmpz_mod_polyxx,
582 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
583 fmpz_mod_poly_mullow(to._poly(), e1._poly(), e2._poly(), e3, to._ctx()))
584
585 FLINT_DEFINE_THREEARY_EXPR_COND3(mulmod_op, fmpz_mod_polyxx,
586 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
587 fmpz_mod_poly_mulmod(to._poly(), e1._poly(), e2._poly(), e3._poly(), to._ctx()))
588
589 FLINT_DEFINE_UNARY_EXPR_COND(sqr_op, fmpz_mod_polyxx, FMPZ_MOD_POLYXX_COND_S,
590 fmpz_mod_poly_sqr(to._poly(), from._poly(), to._ctx()))
591
592 FLINT_DEFINE_BINARY_EXPR_COND2(modulo, fmpz_mod_polyxx,
593 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
594 fmpz_mod_poly_rem(to._poly(), e1._poly(), e2._poly(), to._ctx()))
595
596 FLINT_DEFINE_THREEARY_EXPR_COND3(powmod_binexp_op, fmpz_mod_polyxx,
597 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer, FMPZ_MOD_POLYXX_COND_S,
598 fmpz_mod_poly_powmod_ui_binexp(to._poly(), e1._poly(), e2, e3._poly(), to._ctx()))
599
600 FLINT_DEFINE_THREEARY_EXPR_COND3(powmod_binexp_op, fmpz_mod_polyxx,
601 FMPZ_MOD_POLYXX_COND_S, FMPZXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
602 fmpz_mod_poly_powmod_fmpz_binexp(to._poly(), e1._poly(), e2._fmpz(), e3._poly(), to._ctx()))
603
604 FLINT_DEFINE_THREEARY_EXPR_COND3(pow_trunc_op, fmpz_mod_polyxx,
605 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer, traits::fits_into_slong,
606 fmpz_mod_poly_pow_trunc(to._poly(), e1._poly(), e2, e3, to._ctx()))
607
608 FLINT_DEFINE_THREEARY_EXPR_COND3(pow_trunc_binexp_op, fmpz_mod_polyxx,
609 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer, traits::fits_into_slong,
610 fmpz_mod_poly_pow_trunc_binexp(to._poly(), e1._poly(), e2, e3, to._ctx()))
611
612 FLINT_DEFINE_BINARY_EXPR_COND2(pow_op, fmpz_mod_polyxx,
613 FMPZ_MOD_POLYXX_COND_S, traits::is_unsigned_integer,
614 fmpz_mod_poly_pow(to._poly(), e1._poly(), e2, to._ctx()))
615
616 namespace rdetail {
617 typedef make_ltuple<mp::make_tuple<fmpz_mod_polyxx, fmpz_mod_polyxx>::type>::type
618 fmpz_mod_polyxx_pair;
619 typedef make_ltuple<mp::make_tuple<
620 fmpzxx, fmpz_mod_polyxx, fmpz_mod_polyxx>::type>::type
621 fmpz_mod_poly_divrem_f_rt;
622 } // rdetail
623
624 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_basecase_op, rdetail::fmpz_mod_polyxx_pair,
625 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
626 fmpz_mod_poly_divrem_basecase(
627 to.template get<0>()._poly(), to.template get<1>()._poly(),
628 e1._poly(), e2._poly(), e1._ctx()))
629
630 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_divconquer_op, rdetail::fmpz_mod_polyxx_pair,
631 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
632 fmpz_mod_poly_divrem_divconquer(
633 to.template get<0>()._poly(), to.template get<1>()._poly(),
634 e1._poly(), e2._poly(), e1._ctx()))
635
636 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_op, rdetail::fmpz_mod_polyxx_pair,
637 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
638 fmpz_mod_poly_divrem_divconquer(
639 to.template get<0>()._poly(), to.template get<1>()._poly(),
640 e1._poly(), e2._poly(), e1._ctx()))
641
642 FLINT_DEFINE_BINARY_EXPR_COND2(divrem_f_op, rdetail::fmpz_mod_poly_divrem_f_rt,
643 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
644 fmpz_mod_poly_divrem_f(
645 to.template get<0>()._fmpz(), to.template get<1>()._poly(),
646 to.template get<2>()._poly(), e1._poly(), e2._poly(), e1._ctx()))
647
648 FLINT_DEFINE_BINARY_EXPR_COND2(div_basecase_op, fmpz_mod_polyxx,
649 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
650 fmpz_mod_poly_div_basecase(to._poly(), e1._poly(), e2._poly(), to._ctx()))
651
652 FLINT_DEFINE_BINARY_EXPR_COND2(rem_basecase_op, fmpz_mod_polyxx,
653 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
654 fmpz_mod_poly_rem_basecase(to._poly(), e1._poly(), e2._poly(), to._ctx()))
655
656 FLINT_DEFINE_BINARY_EXPR_COND2(inv_series_newton_op, fmpz_mod_polyxx,
657 FMPZ_MOD_POLYXX_COND_S, traits::fits_into_slong,
658 fmpz_mod_poly_inv_series_newton(to._poly(), e1._poly(), e2, to._ctx()))
659
660 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_op, fmpz_mod_polyxx,
661 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
662 fmpz_mod_poly_gcd(to._poly(), e1._poly(), e2._poly(), to._ctx()))
663
664 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_euclidean_op, fmpz_mod_polyxx,
665 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
666 fmpz_mod_poly_gcd_euclidean(to._poly(), e1._poly(), e2._poly(), to._ctx()))
667
668 namespace rdetail {
669 typedef make_ltuple<mp::make_tuple<
670 fmpz_mod_polyxx, fmpz_mod_polyxx, fmpz_mod_polyxx>::type>::type
671 fmpz_mod_polyxx_triple;
672 } // rdetail
673
674 FLINT_DEFINE_BINARY_EXPR_COND2(xgcd_op, rdetail::fmpz_mod_polyxx_triple,
675 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
676 fmpz_mod_poly_xgcd(to.template get<0>()._poly(), to.template get<1>()._poly(),
677 to.template get<2>()._poly(), e1._poly(), e2._poly(), e1._ctx()))
678
679 FLINT_DEFINE_BINARY_EXPR_COND2(xgcd_euclidean_op, rdetail::fmpz_mod_polyxx_triple,
680 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
681 fmpz_mod_poly_xgcd_euclidean(to.template get<0>()._poly(),
682 to.template get<1>()._poly(),
683 to.template get<2>()._poly(), e1._poly(), e2._poly(), e1._ctx()))
684
685 namespace rdetail {
686 typedef make_ltuple<mp::make_tuple<fmpzxx, fmpz_mod_polyxx>::type>::type
687 fmpz_mod_gcd_f_rt;
688 } // rdetail
689
690 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_f_op, rdetail::fmpz_mod_gcd_f_rt,
691 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
692 fmpz_mod_poly_gcd_f(to.template get<0>()._fmpz(),
693 to.template get<1>()._poly(), e1._poly(), e2._poly(), e1._ctx()))
694
695 FLINT_DEFINE_BINARY_EXPR_COND2(gcd_euclidean_f_op, rdetail::fmpz_mod_gcd_f_rt,
696 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
697 fmpz_mod_poly_gcd_euclidean_f(to.template get<0>()._fmpz(),
698 to.template get<1>()._poly(), e1._poly(), e2._poly(), e1._ctx()))
699
700 FLINT_DEFINE_BINARY_EXPR_COND2(gcdinv_op, rdetail::fmpz_mod_polyxx_pair,
701 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
702 fmpz_mod_poly_gcdinv(
703 to.template get<0>()._poly(), to.template get<1>()._poly(),
704 e1._poly(), e2._poly(), e1._ctx()))
705
706 FLINT_DEFINE_BINARY_EXPR_COND2(invmod_op, fmpz_mod_polyxx,
707 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
708 execution_check(fmpz_mod_poly_invmod(to._poly(), e1._poly(), e2._poly(), to._ctx()),
709 "invmod", "fmpz_mod_polyxx"))
710
711 FLINT_DEFINE_UNARY_EXPR_COND(derivative_op, fmpz_mod_polyxx,
712 FMPZ_MOD_POLYXX_COND_S,
713 fmpz_mod_poly_derivative(to._poly(), from._poly(), to._ctx()))
714
715 FLINT_DEFINE_BINARY_EXPR_COND2(evaluate_op, fmpzxx,
716 FMPZ_MOD_POLYXX_COND_S, FMPZXX_COND_S,
717 fmpz_mod_poly_evaluate_fmpz(to._fmpz(), e1._poly(), e2._fmpz(), e1._ctx()))
718
719 FLINT_DEFINE_BINARY_EXPR_COND2(compose_op, fmpz_mod_polyxx,
720 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
721 fmpz_mod_poly_compose(to._poly(), e1._poly(), e2._poly(), to._ctx()))
722
723 FLINT_DEFINE_BINARY_EXPR_COND2(compose_divconquer_op, fmpz_mod_polyxx,
724 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
725 fmpz_mod_poly_compose_divconquer(to._poly(), e1._poly(), e2._poly(), to._ctx()))
726
727 FLINT_DEFINE_BINARY_EXPR_COND2(compose_horner_op, fmpz_mod_polyxx,
728 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
729 fmpz_mod_poly_compose_horner(to._poly(), e1._poly(), e2._poly(), to._ctx()))
730
731 FLINT_DEFINE_THREEARY_EXPR_COND3(compose_mod_op, fmpz_mod_polyxx,
732 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
733 fmpz_mod_poly_compose_mod(to._poly(), e1._poly(), e2._poly(), e3._poly(), to._ctx()))
734
735 FLINT_DEFINE_THREEARY_EXPR_COND3(compose_mod_horner_op, fmpz_mod_polyxx,
736 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
737 fmpz_mod_poly_compose_mod_horner(to._poly(), e1._poly(), e2._poly(), e3._poly(), to._ctx()))
738
739 FLINT_DEFINE_THREEARY_EXPR_COND3(compose_mod_brent_kung_op, fmpz_mod_polyxx,
740 FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S, FMPZ_MOD_POLYXX_COND_S,
741 fmpz_mod_poly_compose_mod_brent_kung(to._poly(), e1._poly(), e2._poly(), e3._poly(), to._ctx()))
742
743 } // rules
744
745 ///////////////////////////////////////////////////////////////////////////////
746 // fmpz_mod_poly_vecxx (for radix conversion)
747 ///////////////////////////////////////////////////////////////////////////////
748 namespace detail {
749 struct fmpz_mod_poly_vector_data
750 {
751 slong size;
752 fmpz_mod_poly_struct** array;
753 fmpz_modxx_ctx_srcref ctx;
754
755 fmpz_mod_poly_vector_data(slong n, fmpz_modxx_ctx_srcref c)
756 : size(n), ctx(c)
757 {
758 array = new fmpz_mod_poly_struct*[n];
759 for(slong i = 0;i < n;++i)
760 {
761 array[i] = new fmpz_mod_poly_struct();
762 fmpz_mod_poly_init(array[i], ctx._ctx());
763 }
764 }
765
766 ~fmpz_mod_poly_vector_data()
767 {
768 for(slong i = 0;i < size;++i)
769 {
770 fmpz_mod_poly_clear(array[i], ctx._ctx());
771 delete array[i];
772 }
773 delete[] array;
774 }
775
776 fmpz_mod_poly_vector_data(const fmpz_mod_poly_vector_data& o)
777 : size(o.size), ctx(o.ctx)
778 {
779 array = new fmpz_mod_poly_struct*[size];
780 for(slong i = 0;i < size;++i)
781 {
782 array[i] = new fmpz_mod_poly_struct();
783 fmpz_mod_poly_init(array[i], ctx._ctx());
784 fmpz_mod_poly_set(array[i], o.array[i], ctx._ctx());
785 }
786 }
787
788 fmpz_mod_polyxx_ref at(slong i)
789 {return fmpz_mod_polyxx_ref::make(array[i], ctx);}
790 fmpz_mod_polyxx_srcref at(slong i) const
791 {return fmpz_mod_polyxx_srcref::make(array[i], ctx);}
792
793 bool equals(const fmpz_mod_poly_vector_data& o) const
794 {
795 if(size != o.size)
796 return false;
797 for(slong i = 0;i < size;++i)
798 if(!fmpz_mod_poly_equal(array[i], o.array[i], ctx._ctx()))
799 return false;
800 return true;
801 }
802 };
803
804 struct fmpz_mod_poly_vector_traits
805 : wrapped_vector_traits<fmpz_mod_polyxx, slong, fmpz_mod_polyxx_ref,
806 fmpz_mod_polyxx_srcref, fmpz_mod_poly_struct*>
807 {
808 template<class Expr>
809 static typename Expr::evaluated_t create_temporary(const Expr& e)
810 {
811 return typename Expr::evaluated_t(e.size(), tools::find_fmpz_modxx_ctx(e));
812 }
813 };
814 } // detail
815
816 // TODO would it make more sense to have this have its own class?
817 typedef vector_expression<
818 detail::fmpz_mod_poly_vector_traits, operations::immediate,
819 detail::fmpz_mod_poly_vector_data> fmpz_mod_poly_vecxx;
820 // TODO references
821
822 template<>
823 struct enable_vector_rules<fmpz_mod_poly_vecxx> : mp::false_ { };
824
825 namespace rules {
826 // TODO hack to make code look like references are implemented
827 template<class T> struct FMPZ_MOD_POLY_VECXX_COND_S
828 : mp::equal_types<T, fmpz_mod_poly_vecxx> { };
829 #define FMPZ_MOD_POLY_VECXX_COND_T FMPZ_MOD_POLY_VECXX_COND_S
830
831 // TODO references
832 FLINT_DEFINE_GET(equals, bool, fmpz_mod_poly_vecxx, e1._data().equals(e2._data()))
833 } // rules
834
835
836 ///////////////////////////////////////////////////////////////////////////////
837 // radix conversion
838 ///////////////////////////////////////////////////////////////////////////////
839
840 class fmpz_mod_poly_radixxx
841 {
842 private:
843 fmpz_mod_poly_radix_t inner;
844
845 // not copyable
846 fmpz_mod_poly_radixxx(const fmpz_mod_poly_radixxx&);
847
848 public:
849 template<class Fmpz_mod_poly>
850 fmpz_mod_poly_radixxx(const Fmpz_mod_poly& r, slong deg,
851 typename mp::enable_if<
852 traits::is_fmpz_mod_polyxx<Fmpz_mod_poly> >::type* = 0)
853 {
854 auto e = r.evaluate();
855 fmpz_mod_poly_radix_init(inner, e._poly(), deg, e._ctx());
856 }
857
858 ~fmpz_mod_poly_radixxx() {fmpz_mod_poly_radix_clear(inner);}
859
860 fmpz_mod_poly_radix_t& _data() {return inner;}
861 const fmpz_mod_poly_radix_t& _data() const {return inner;}
862
863 slong degR() const {return inner->degR;}
864 };
865
866 namespace traits {
867 template<class T> struct is_fmpz_mod_poly_radixxx
868 : mp::equal_types<T, fmpz_mod_poly_radixxx> { };
869 } // traits
870
871 namespace vectors {
872 template<>
873 struct outsize<operations::radix_op>
874 {
875 template<class Expr>
876 static unsigned get(const Expr& e)
877 {
878 return e._data().first().degree() / e._data().second().degR() + 1;
879 }
880 };
881 }
882
883 namespace rules {
884 FLINT_DEFINE_BINARY_EXPR_COND2(radix_op, fmpz_mod_poly_vecxx,
885 FMPZ_MOD_POLYXX_COND_S, traits::is_fmpz_mod_poly_radixxx,
886 fmpz_mod_poly_radix(to._array(), e1._poly(), e2._data(), e1._ctx()))
887 }
888 } // flint
889
890 #include "fmpz_mod_poly_factorxx.h"
891
892 #endif
893