[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7. Modular integers


[ < ] [ > ]   [ << ] [ Up ] [ >> ]         [Top] [Contents] [Index] [ ? ]

7.1 Modular integer rings

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] [ ? ]

7.2 Functions on modular integers

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.