Go to the first, previous, next, last section, table of contents.

7. Modular integers

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.

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.
cl_boolean 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 (cl_ostream stream, const cl_MI& x)
cl_ostream operator<< (cl_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.

Go to the first, previous, next, last section, table of contents.