Modular Integers.

There are many ways to implement the rings ${\mbox{${\mathbb{Z}}$}}/m{\mbox{${\mathbb{Z}}$}}$ and even more for the fields ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ (where $p$ is a prime). Let us restrict to the fields ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ . Here are some examples.

• For $p$ in the range $[2, 2^{N} - 1]$ we can use single integers. Multiplication and addition can be made in ${\cal O}(1)$ word operations. N.B. multiplication requires a two single integers buffer unless $p$ in the range $[2, 2^{N-1} - 1]$ . Exponentiation and computation of inverses require a bit more of works but are still in ${\cal O}(1)$ 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 ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ is a cyclic group. In other words, there exists a generator $g \in {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ such that every nonzero $x \in {\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ is a power of $g$ called the discrete logarithm of $x$ . Hence we can use discrete logarithms to represent nonzero elements of ${\mbox{${\mathbb{Z}}$}}/p{\mbox{${\mathbb{Z}}$}}$ . 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 ${\cal O}(1)$ word operations.