### Modular Integers.

There are many ways to implement the rings and even more for the fields (where is a prime). Let us restrict to the fields . Here are some examples.
• For in the range we can use single integers. Multiplication and addition can be made in word operations. N.B. multiplication requires a two single integers buffer unless in the range . Exponentiation and computation of inverses require a bit more of works but are still in word operations. For instance here's an ALDOR code for the division of two integers modulo a third one
       mod_/(i: %, j: %, n: %): % == {
local c0, d0, c1, d1: %;
(c0, d0) := (j, n);
(c1, d1) := (1, 0);
while not zero? d0 repeat {
q := c0 quo d0;
(c0, d0) := (d0, c0 - q*d0);
(c1, d1) := (d1, c1 - q*d1)
}
if c0 ~= 1 then error "inverse does not exist";
if c1 < 0  then c1 := c1 + n;
mod_*(i, c1, n);

• The set of the nonzero elements of is a cyclic group. In other words, there exists a generator such that every nonzero is a power of called the discrete logarithm of . Hence we can use discrete logarithms to represent nonzero elements of . Then exponentiation and computation of inverses become much more easy (for inverses we use Little Fermat Theorem) than with the previous encoding. However addition requires the use of tables of logarithms and exponentiations, for efficiency. Again all arithmetic operations are in word operations.

Marc Moreno Maza
2008-01-07