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.

This document was generated on August 27, 2013 using texi2html 5.0.