[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
7.1 Modular integer rings | ||
7.2 Functions on modular integers |
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
CLN implements modular integers, i.e. integers modulo a fixed integer N.
The modulus is explicitly part of every modular integer. CLN doesn't
allow you to (accidentally) mix elements of different modular rings,
e.g. (3 mod 4) + (2 mod 5)
will result in a runtime error.
(Ideally one would imagine a generic data type cl_MI(N)
, but C++
doesn't have generic types. So one has to live with runtime checks.)
The class of modular integer rings is
Ring cl_ring <cln/ring.h> | | Modular integer ring cl_modint_ring <cln/modinteger.h> |
and the class of all modular integers (elements of modular integer rings) is
Modular integer cl_MI <cln/modinteger.h> |
Modular integer rings are constructed using the function
cl_modint_ring find_modint_ring (const cl_I& N)
This function returns the modular ring `Z/NZ'. It takes care
of finding out about special cases of N
, like powers of two
and odd numbers for which Montgomery multiplication will be a win,
and precomputes any necessary auxiliary data for computing modulo N
.
There is a cache table of rings, indexed by N
(or, more precisely,
by abs(N)
). This ensures that the precomputation costs are reduced
to a minimum.
Modular integer rings can be compared for equality:
bool operator== (const cl_modint_ring&, const cl_modint_ring&)
bool operator!= (const cl_modint_ring&, const cl_modint_ring&)
These compare two modular integer rings for equality. Two different calls
to find_modint_ring
with the same argument necessarily return the
same ring because it is memoized in the cache table.
[ < ] | [ > ] | [ << ] | [ Up ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
Given a modular integer ring R
, the following members can be used.
cl_I R->modulus
This is the ring's modulus, normalized to be nonnegative: abs(N)
.
cl_MI R->zero()
This returns 0 mod N
.
cl_MI R->one()
This returns 1 mod N
.
cl_MI R->canonhom (const cl_I& x)
This returns x mod N
.
cl_I R->retract (const cl_MI& x)
This is a partial inverse function to R->canonhom
. It returns the
standard representative (>=0
, <N
) of x
.
cl_MI R->random(random_state& randomstate)
cl_MI R->random()
This returns a random integer modulo N
.
The following operations are defined on modular integers.
cl_modint_ring x.ring ()
Returns the ring to which the modular integer x
belongs.
cl_MI operator+ (const cl_MI&, const cl_MI&)
Returns the sum of two modular integers. One of the arguments may also be a plain integer.
cl_MI operator- (const cl_MI&, const cl_MI&)
Returns the difference of two modular integers. One of the arguments may also be a plain integer.
cl_MI operator- (const cl_MI&)
Returns the negative of a modular integer.
cl_MI operator* (const cl_MI&, const cl_MI&)
Returns the product of two modular integers. One of the arguments may also be a plain integer.
cl_MI square (const cl_MI&)
Returns the square of a modular integer.
cl_MI recip (const cl_MI& x)
Returns the reciprocal x^-1
of a modular integer x
. x
must be coprime to the modulus, otherwise an error message is issued.
cl_MI div (const cl_MI& x, const cl_MI& y)
Returns the quotient x*y^-1
of two modular integers x
, y
.
y
must be coprime to the modulus, otherwise an error message is issued.
cl_MI expt_pos (const cl_MI& x, const cl_I& y)
y
must be > 0. Returns x^y
.
cl_MI expt (const cl_MI& x, const cl_I& y)
Returns x^y
. If y
is negative, x
must be coprime to the
modulus, else an error message is issued.
cl_MI operator<< (const cl_MI& x, const cl_I& y)
Returns x*2^y
.
cl_MI operator>> (const cl_MI& x, const cl_I& y)
Returns x*2^-y
. When y
is positive, the modulus must be odd,
or an error message is issued.
bool operator== (const cl_MI&, const cl_MI&)
bool operator!= (const cl_MI&, const cl_MI&)
Compares two modular integers, belonging to the same modular integer ring, for equality.
bool zerop (const cl_MI& x)
Returns true if x
is 0 mod N
.
The following output functions are defined (see also the chapter on input/output).
void fprint (std::ostream& stream, const cl_MI& x)
std::ostream& operator<< (std::ostream& stream, const cl_MI& x)
Prints the modular integer x
on the stream
. The output may depend
on the global printer settings in the variable default_print_flags
.
[ << ] | [ >> ] | [Top] | [Contents] | [Index] | [ ? ] |
This document was generated by Richard B. Kreckel on January, 19 2008 using texi2html 1.76.