The class SmallFpLogImpl
is NOT INTENDED for use by "casual" CoCoALib
users. If you wish to compute in finite fields see the documentation in
QuotientRing.txt (in particular the function NewZmod
), or possibly the
documentation in RingFp
, RingFpLog
, and RingFpDouble
.
Compared to SmallFpImpl
the only difference is an implementation
detail: multiplication and division are achieved using discrete log
tables -- this may be fractionally faster on some processors.
Note that the cost of construction of a SmallFpLogImpl(p)
object for
larger primes may be quite considerable (linear in p), and the resulting
object may occupy quite a lot of space (e.g. probably about 6*p bytes).
A SmallFpLogImpl
object cannot be used as a CoCoA ring
, even though the
implementation is rather reminiscent of a ring implementation class.
ALL OPERATIONS on values must be effected by calling member functions
of the SmallFpLogImpl
class. Here is a brief summary.
SmallFpImpl ModP(p,convention); // create SmallFpImpl object int n; BigInt N; SmallFpImpl::value_t a, b, c; ModP.myModulus(); // value of p (as a long) ModP.myReduceMod(n); // reduce mod p ModP.myAssign(a, b); // a = b; ModP.myAssign(a, n); // a = n%p; (reduce mod p) ModP.myAssign(a, N); // a = N%p; (reduce mod p) ModP.myNegate(a, b); // a = -b; ModP.myAdd(a, b, c); // a = (b+c)%p; ModP.mySub(a, b, c); // a = (b-c)%p; ModP.myMul(a, b, c); // a = (b*c)%p; ModP.myDiv(a, b, c); // a = (b*inv(c))%p; where inv(c) is inverse of c ModP.myPower(a, b, c); // a = (b^c)%p; where ^ means "to the power of" ModP.myIsZeroAddMul(a,b,c) // a = (a+b*c)%p; result is (a==0) ModP.myIsZero(a); // a == 0 ModP.myIsOne(a); // a == 1 ModP.myIsMinusOne(a); // a == -1 ModP.myIsInteger(N, a); // N = a (find a preimage) ModP.myIsEqual(a, b); // a == b
For myExport
the choice between least non-negative and symmetric
residues is determined by the convention specified when constructing
the SmallFpLogImpl
object. This cnvention may be either
GlobalSettings::SymmResidues
or
GlobalSettings::NonNegResidues
.
The only clever bit is the "economical" construction of the log/exp tables in the constructor where we exploit the fact that myRoot to the power (p-1)/2 must be equal to -1.
This implementation uses discrete log/exp tables to effect multiplication and division quickly. Note that the residues themselves (i.e. the values of the ring elements) are held as machine integers whose value is the least non-negative representative of the residue class (i.e. in the range 0 to p-1). In particular, although log tables are used, we do NOT use a "logarithmic representation".
The choice of C++ vectors for the log/exp tables was dictated by a desire to offer exception safety, especially avoiding memory leakage should an exception occur.
The log/exp tables are stored in C++ vectors: aside from their construction during the RingFpLogImpl constructor, these vectors are never modified, and are used only for table look-up. The C++ vectors are resized in the body of the constructor to avoid large memory requests when overly large characteristics are supplied as argument.
Besides these tables SmallFpLogImpl
also remembers the characteristic in
myModulus
; myRoot
is the primitive root used to generate the log/exp
tables. The two values myShift
and myIterLimit
may be useful for fast
implementations which want to use unnormalized multiplication: myShift
is
the greatest multiple of the characteristic not exceeding half the biggest
value a value_t
can contain, while myIterLimit
is greatest number of
unnormalized products which can be summed without exceeding half the
largest value which fits into a value_t
. The constructor ensures that
myIterLimit
is strictly greater than zero.
As the code currently stands, the modulus must also be small enough that
it can fit into an FpTableElem
(an unsigned short
), and that its square
can fit into a value_t
. Using short
s in the tables gave slightly better
run-time performance in our tests. Furthermore, to permit use of
unnormalized products in some algorithms, twice the square of the
characteristic must fit into a value_t
(i.e. myIterLimit
must be greater
than zero). The constructor for a RingFpLogImpl
checks the size
restrictions on the characteristic.
Note that the log table has a slot with index 0 which is never written to nor read from. The exp table is double size so that multiplication can be achieved more easily: the highest slot which could ever be used is that with index 2p-3 (in division), but the constructor fills two extra slots (as this makes the code simpler/neater).
The only slick part of the implementation is the filling of the tables in the constructor, where some effort is made to avoid doing more reductions modulo p than necessary. Note that the primitive root is always calculated (potentially costly!); there is no memorized global table of primitive roots anywhere.
It is not as fast as I hoped -- perhaps cache effects? There seem to be better ways of calculating quickly: e.g. to compute an inner product it is best simply to compute it without modulus and perform a single reduction at the end (provided overflow cannot occur).