1 // polys.h : defines interface to NTL polynomials
2 //////////////////////////////////////////////////////////////////////////
3 //
4 // Copyright 1990-2012 John Cremona
5 //
6 // This file is part of the eclib package.
7 //
8 // eclib is free software; you can redistribute it and/or modify it
9 // under the terms of the GNU General Public License as published by the
10 // Free Software Foundation; either version 2 of the License, or (at your
11 // option) any later version.
12 //
13 // eclib is distributed in the hope that it will be useful, but WITHOUT
14 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 // for more details.
17 //
18 // You should have received a copy of the GNU General Public License
19 // along with eclib; if not, write to the Free Software Foundation,
20 // Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301, USA
21 //
22 //////////////////////////////////////////////////////////////////////////
23
24 // allow for multiple includes
25 #ifndef _ECLIB_POLYS_H
26 #define _ECLIB_POLYS_H
27
28 // NB --warning! In NTL there is a universal modulus set by a single
29 // call to ZZ_p::init(q).
30
31 #include <eclib/gf.h> // scalars
32 #include <eclib/bigrat.h>
33
34 #include <NTL/ZZ_pX.h>
35 #include <NTL/ZZ_pXFactoring.h>
36
37 #define ZPoly ZZX
38 #define PolyCoeff(f,i) coeff((f),(i))
39 #define ZPolySetX(f) SetX(f);
40 #define SetDegree(f,d)
41 #define Degree(f) deg((f))
42
43 #define FqPoly ZZ_pX
44 #define NewFqPoly(field,name) FqPoly name
45 #define FqPolySetField(f,field) // do nothing
46 #define FqPolyAssignGF(f,c) f=((c))
47 #define FqPolyAssignZ(f,c) f=(to_ZZ_p(c))
48 #define FqPolyAssign0(f) f=to_ZZ_p(0)
49 #define FqPolyAssign1(f) f=to_ZZ_p(1)
50 #define FqPolyEval(f,c) eval((f),to_ZZ_p(c))
51 #define FqPolyAssignX(f) SetX(f)
52 #define GetField(f) (galois_field(ZZ_p::modulus()))
53
54 vector<bigint> rootsmod(const vector<bigint>& coeffs, bigint p);
55 vector<gf_element> roots(const FqPoly& f);
56 vector<bigrational> roots(const vector<bigint>& coeffs);
57 vector<bigrational> roots(const ZPoly& f);
58 vector<bigint> introots(const ZPoly& f);
59
60 vector<bigint> Introotscubic(const bigint& a, const bigint& b, const bigint& c);
61 vector<bigint> Introotsquartic(const bigint& a, const bigint& b, const bigint& c,
62 const bigint& d);
63
64
65
66 // find the number of roots of X^3 + bX^2 + cX + d = 0 (mod p)
67 int nrootscubic(const bigint& bb, const bigint& cc, const bigint& dd, const bigint& p);
68
69 FqPoly reduce(const ZPoly& f, const galois_field& Fq);
70
reduce(const ZPoly & f,const bigint & q)71 inline FqPoly reduce(const ZPoly& f, const bigint& q)
72 {return reduce(f,galois_field(q));}
73
74
75
76 #endif // #define _POLYS_
77