SmallFpImpl is a very low level implementation class for fast
arithmetic in a small, prime finite field. It is not intended for use
by casual CoCoALib users, who should instead see the documentation in
QuotientRing (in particular the function
NewZZmod), or possibly the
SmallFpImpl offers the possibility of highly efficient
arithmetic in small prime finite fields. This efficiency comes at a
cost: the interface is rather unnatural and intolerant of mistakes. The
emphasis is unequivocally on speed rather than safety or convenience.
The full speed of
SmallFpImpl depends on many of its functions being
inlined. The values to be manipulated must be of type
This is an unsigned machine integer type, and the values
may be used normally (but other values must be reduced before being used).
All operations on values must be effected by calling member functions
SmallFpImpl class. Here is a brief summary.
SmallFpImpl::IsGoodCtorArg(p); // true iff ctor SmallFpImpl(p) will succeed SmallFpImpl::ourMaxModulus(); // largest permitted modulus SmallFpImpl ModP(p, convention); // create SmallFpImpl object long n; BigInt N; BigRat q; SmallFpImpl::value_t a, b, c; ModP.myModulus(); // value of p (as a long) ModP.myReduce(n); // reduce mod p ModP.myReduce(N); // reduce mod p ModP.myReduce(q); // reduce mod p ModP.myExport(a); // returns a preimage (of type long) according to symm/non-neg convention. ModP.myNegate(a); // -a mod p ModP.myAdd(a, b); // (a+b)%p; ModP.mySub(a, b); // (a-b)%p; ModP.myMul(a, b); // (a*b)%p; ModP.myDiv(a, b); // (a*inv(b))%p; where inv(b) is inverse of b ModP.myPower(a, n); // (a^n)%p; where ^ means "to the power of" ModP.myIsZeroAddMul(a,b,c) // a = (a+b*c)%p; result is (a==0)
myExport the choice between least non-negative and symmetric
residues is determined by the convention specified when constructing
SmallFpImpl object. This convention may be either
The normal mod p arithmetic operations listed above always produce a normalized result. In some loops it may be possible to compute several iterations before having to normalize the result. The following three functions help implement such a delayed normalization strategy.
ModP.myNormalize(a); -- FULL normalization of a ModP.myHalfNormalize(a); -- *fast*, PARTIAL normalization of a ModP.myMaxIters();
The value of
myMaxIters() is the largest number of unnormalized
products (of normalized values) which may be added to a partially
normalized value before risking overflow. The partial normalization
operation is quick (at most a comparison and a subtraction).
Naturally, the final result must be fully normalized. See example
ex-SmallFp1.C for a working implementation.
Most functions are implemented inline, and no sanity checks are
performed (except when
CoCoA_DEBUG is enabled). The constructor
does do some checking.
SmallFpImpl::value_t must be an unsigned integral type; it is a
typedef to a type specified in
CoCoA/config.H -- this should allow
fairly easy platform-specific customization.
This code is valid only if the square of
myModulus can be represented
SmallFpImpl::value_t; the constructor checks this condition.
Most functions do not require
myModulus to be prime, though division
becomes only a partial map if it is composite; and the function
myIsDivisible is correct only if
myModulus is prime. Currently the
constructor rejects non-prime moduli.
The code assumes that each value modulo p is represented as the least
non-negative residue (i.e. the values are represented as integers in
the range 0 to p-1 inclusive). This decision is linked to the fact
SmallFpImpl::value_t is an unsigned type.
myIterLimit are to allow efficient
exploitation of non-reduced multiplication (e.g. when trying to
compute an inner product modulo p). See example program
The return type of
int even though the result is
always non-negative -- I do not like
Should there be a