The usual way to perform arithmetic in a (small, prime) finite field
is to create the appropriate ring via the pseudo-constructors
NewZZmod
(or NewQuotientRing
if you prefer) which are
documented in QuotientRing
. These functions will automatically
choose a suitable underlying implementation, and you should normally
use them.
In some special circumstances, you may wish to choose explicitly the
underlying implementation. CoCoALib offers three distinct
implementations of small prime finite fields: RingFp
, and
RingFpLog
and RingFpDouble
(described here). Of these
RingFpDouble
may offer the highest limit on the characteristic
(e.g. on 32-bit machines) -- this file describes how to create a
RingFpDouble
implementation.
To create a ring
of this specific type use one of the pseudo-constructors:
NewRingFpDouble(p) -- p a machine integer or BigInt NewRingFpDouble(I) -- I an ideal of Z NewRingFpDouble(p, res) -- p a machine integer, res is either ``GlobalSettings::SymmResidues`` or ``GlobalSettings::NonNegResidues``
These pseudo-constructors are for creating small prime finite fields; they
will fail if the characteristic is not prime or is too large: the error
signalled by throwing a CoCoA::ErrorInfo
whose code is
CoCoA::ERR::BadSmallFpChar
. You can test whether an argument is
suitable by calling IsGoodFoRingFpDouble
.
In the directory examples/
there is a small example program showing
how small finite fields (with known implementation) can be created and
used: ex-RingFp2.C
.
The default convention for printing residues is specified when you create
the GlobalManager
; you can also specify explicitly which convention to
use by giving a second argument to the pseudo-ctor NewRingFp
. Note
that the internal representation is always least non-negative
regardless of the output convention chosen.
If you seek a means for fast arithmetic in small finite fields consult
the documentation about SmallFpImpl
, SmallFpLogImpl
, and
SmallFpDoubleImpl
. All arithmetic on elements of a RingFp
is actually carried out by a SmallFpImpl
object.
The class RingFpDoubleImpl
is a low-level implementation of (small
prime) finite fields; it is not intended for direct use by casual CoCoA
library users. Internally values are represented using double
s:
this may permit a higher maximum characteristic on some computers
(e.g. 32-bitters).
The class RingFpDoubleImpl
is intended to represent small, prime
finite fields. The constructor is more complicated than one might
expect; this is because the RingFpDoubleImpl
object must store a
little extra information to fulfil its role as a QuotientRing
.
Currently, the characteristic must be prime (otherwise it wouldn't be a
field). Furthermore, the characteristic p must also be small enough
that all integers up to p*(p-1) can be represented exactly as double
s.
Creating a RingFpDoubleImpl
takes almost constant time (except for the
primality check). An error is signalled (i.e. a CoCoA::ErrorInfo
is
thrown) if the characteristic is too large or not prime.
Extreme efficiency is NOT one of the main features of this version:
contrast with SmallFpDoubleImpl
.
The class RingFpDoubleImpl
derives from QuotientRingBase
,
which in turn is derived from RingBase
: see QuotientRing
and
ring
for more details. Note that there is no RingFpDouble
class; a RingFpDoubleImpl
object can only be accessed as a
QuotientRing
.
Note the use of "argument checking" static member functions in the ctor:
this is because const
data members must be initialized before the main
body of the ctor is entered.
A member typedef specifies the type used internally for representing
the value of an element of a RingFpDoubleImpl
: currently this is just
SmallFpDoubleImpl::value_t
which is double
.
Essentially all operations are delegated to the class SmallFpDoubleImpl
.
The two classes are separate so that the inline operations of
SmallFpDoubleImpl
can be accessed directly in certain other special case
implementations (e.g. polynomials with coeffs in a small finite field). See the
documentation on SmallFpDoubleImpl
for details.
The data members are those of a QuotientRingBase
(which are used only
for answering queries about a QuotientRing
), plus the characteristic
of the field (held as an value_t
in myModulusValue
), and an auto-pointer
to a copy of the zero and one elements of the ring.
The zero and one elements of the ring is held in an auto_ptr<> for consistency with the implementation of other rings -- in this simple class it is not really necessary for exception safety.
The largest permitted modulus for a RingFpImpl
may depend on the
platform. If IEEE doubles are used then moduli up to 67108859 are
permitted -- refer to SmallFpDoubleImpl
for details.
Although it may seem wasteful to use heap memory for the values of
elements in a RingFpDoubleImpl
, trying to make them "inline" leads to
lots of problems -- see RingFp
for more details.
Can reduction modulo p be made faster?
Run-time performance is disappointing.
I wonder if this code will ever prove useful to anyone.