This class implements polynomials \(P(x)\) in \(\mathbb Z_m[X]\) defined as. More...
#include <latmrg/PolyPE.h>
Public Member Functions | |
| PolyPE () | |
| Minimal constructor: this object is set to the 0 polynomial. More... | |
| const ModInt< Int >::PolX & | getVal () |
| bool | isPrimitive (const IntPrimitivity< Int > &fm, const IntFactorization< Int > &fr) |
Returns true if the modulus \(f(x)\) is a primitive polynomial modulo \(m\). More... | |
| bool | isPrimitive (const IntFactorization< Int > &r) |
Given the factorization of \(r\), this method returns true if conditions 2 and 3 above are satisfied by the modulus \(f(x)\). More... | |
| void | powerMod (const Int &j) |
| Sets \(v = x^j \mod f(x) (\bmod m)\). More... | |
| void | setVal (long j) |
| void | setVal (const IntVec &C) |
| Initializes this object to \(C\). More... | |
| void | setVal (std::string &str) |
Initializes this object to the polynomial in str. More... | |
| std::string | toString () const |
| Returns this object as a string. More... | |
| void | toVector (IntVec &c) |
| Returns the coefficients of this polynomial as a vector \(C\) of \(k\) components, where \(k\) is the degree of the modulus \(f(x)\). More... | |
Static Public Member Functions | |
| static const ModInt< Int >::PolX & | getF () |
| Returns the modulus polynomial \(f(x)\). More... | |
| static long | getK () |
| Returns the degree of the modulus \(f(x)\). More... | |
| static const Int & | getM () |
| Returns a read-only reference to \(m\). More... | |
| static void | reverse (IntVec &c, long k, int kind) |
Given a vector \(C = [c_0, c_1, …, c_{k-1}, c_k]\), this function reorders the components of \(C\) in the form \(C = [c_k, c_{k-1}, ..., c_1, c_0]\) for kind = 1, and in the form \(C = [-c_k, -c_{k-1}, …, -c_1, 1]\) for kind = 2. More... | |
| static void | setF (const typename ModInt< Int >::IntVecP &C) |
Initializes the modulus polynomial \(f(x) = c_0 + c_1x +c_2x^2 + \cdots+ c_kx^k\) of degree \(k\) for this class from the coefficients \(c_i = \)C[i] of vector C of dimension \(k + 1\). More... | |
| static void | setF (const IntVec &C) |
Same as above, but instead from a IntVec. More... | |
| static void | setM (const Int &m) |
| Initializes the modulus \(m\) for this class. More... | |
Private Types | |
| typedef NTL::vector< Int > | IntVec |
Static Private Attributes | |
| static long | m_k |
| Degree of the modulus polynomial \(f\). More... | |
| static Int | m_m |
| Modulus of congruence. More... | |
| static ModInt< Int >::PolX | m_x |
| The polynomial \(f(x) = x\). More... | |
Detailed Description
template<typename Int>
class LatMRG::PolyPE< Int >
This class implements polynomials \(P(x)\) in \(\mathbb Z_m[X]\) defined as.
\[ P(x) = c_0 + c_1x^1 + c_2 x^2 + \cdots+ c_nx^n \tag{eq.poly1} \]
with degree \(n\) and integer coefficients \(c_i\) in \(\mathbb Z_m\). The arithmetic operations on objects of this class are done modulo \(m\) and modulo a polynomial \(f(x)\) of degree \(k\). Thus all polynomials will be reduced modulo \(f(x)\). In LatMRG, the modulus polynomial \(f(x)\) is usually written in the form
\[ f(x) = x^k - a_1x^{k-1} - \cdots- a_{k-1} x - a_k, \tag{eq.poly2} \]
and is associated with the recurrence
\[ x_n = (a_1x_{n-1} + a_2x_{n-2} + \cdots+ a_k x_{n-k}) \bmod m. \tag{eq.rec2} \]
The two functions setM and setF must be called to initialize the modulus \(m\) and the modulus polynomial \(f(x)\) before doing any arithmetic operations on PolyPE objects, otherwise the results are unpredictable.
Type Int is used to represent polynomial coefficients. It may be chosen as long for \(m < 2^{50}\) (on 64-bit machines), or as the big integer type ZZ otherwise. The possible associated types IntVec are long* and vec_ZZ. Type PolE for the polynomials may be chosen as zz_pE when \(m < 2^{50}\), or it may be set to ZZ_pE which is implemented with the big integer type ZZ_p.
Member Typedef Documentation
◆ IntVec
|
private |
Constructor & Destructor Documentation
◆ PolyPE()
| LatMRG::PolyPE< Int >::PolyPE | ( | ) |
Minimal constructor: this object is set to the 0 polynomial.
Member Function Documentation
◆ getF()
|
inlinestatic |
Returns the modulus polynomial \(f(x)\).
◆ getK()
|
inlinestatic |
Returns the degree of the modulus \(f(x)\).
◆ getM()
|
inlinestatic |
Returns a read-only reference to \(m\).
◆ getVal()
|
inline |
◆ isPrimitive() [1/2]
| bool LatMRG::PolyPE< Int >::isPrimitive | ( | const IntPrimitivity< Int > & | fm, |
| const IntFactorization< Int > & | fr | ||
| ) |
Returns true if the modulus \(f(x)\) is a primitive polynomial modulo \(m\).
For this to be true, assuming that \(f(x)\) has the form (eq.poly2) above, the three following conditions must be satisfied:
- None
- \([(-1)^{k+1} a_k]^{(m-1)/q} \bmod m \neq1\) for each prime factor \(q\) of \(m - 1\);
- None
- \(x^r \bmod(f(x),m) = (-1)^{k+1} a_k \bmod m\);
- None
- \(x^{r/q} \bmod(f(x), m) \) has positive degree for each prime factor \(q\) of \(r\), with \(1<q< r\);
where \(r = (m^k - 1)/(m - 1)\). The factorizations of \(m-1\) and \(r\) must be in fm and fr respectively. Condition 1 is the same as saying that \((-1)^{k+1} a_k\) is a primitive root of \(m\). Condition 3 is automatically satisfied when \(r\) is prime.
◆ isPrimitive() [2/2]
| bool LatMRG::PolyPE< Int >::isPrimitive | ( | const IntFactorization< Int > & | r | ) |
Given the factorization of \(r\), this method returns true if conditions 2 and 3 above are satisfied by the modulus \(f(x)\).
It does not check condition 1, assuming it to be true.
◆ powerMod()
| void LatMRG::PolyPE< Int >::powerMod | ( | const Int & | j | ) |
Sets \(v = x^j \mod f(x) (\bmod m)\).
◆ reverse()
|
static |
Given a vector \(C = [c_0, c_1, …, c_{k-1}, c_k]\), this function reorders the components of \(C\) in the form \(C = [c_k, c_{k-1}, ..., c_1, c_0]\) for kind = 1, and in the form \(C = [-c_k, -c_{k-1}, …, -c_1, 1]\) for kind = 2.
For other values of kind, it has no effect.
◆ setF() [1/2]
|
static |
Initializes the modulus polynomial \(f(x) = c_0 + c_1x +c_2x^2 + \cdots+ c_kx^k\) of degree \(k\) for this class from the coefficients \(c_i = \)C[i] of vector C of dimension \(k + 1\).
This function must be called before doing any arithmetic operations on PolyPE objects, otherwise the results are unpredictable.
◆ setF() [2/2]
|
static |
Same as above, but instead from a IntVec.
◆ setM()
|
static |
Initializes the modulus \(m\) for this class.
This must be called before doing any operations on PolyPE objects, otherwise the results are unpredictable.
◆ setVal() [1/3]
| void LatMRG::PolyPE< Int >::setVal | ( | long | j | ) |
◆ setVal() [2/3]
| void LatMRG::PolyPE< Int >::setVal | ( | const IntVec & | C | ) |
Initializes this object to \(C\).
◆ setVal() [3/3]
| void LatMRG::PolyPE< Int >::setVal | ( | std::string & | str | ) |
Initializes this object to the polynomial in str.
◆ toString()
| std::string LatMRG::PolyPE< Int >::toString | ( | ) | const |
Returns this object as a string.
◆ toVector()
| void LatMRG::PolyPE< Int >::toVector | ( | IntVec & | c | ) |
Returns the coefficients of this polynomial as a vector \(C\) of \(k\) components, where \(k\) is the degree of the modulus \(f(x)\).
Member Data Documentation
◆ m_k
|
staticprivate |
Degree of the modulus polynomial \(f\).
◆ m_m
|
staticprivate |
Modulus of congruence.
◆ m_x
|
staticprivate |
The polynomial \(f(x) = x\).
The documentation for this class was generated from the following file:
- include/latmrg/PolyPE.h
