key cryptography (PKC). Let m and x be two integers, with m being nonzero. Define [x/m] as the integer part of the division of x by m. If we consider, for instance, m=3a and the ratios 2/3 = 0.66, 4/3 = 1.33,6/3 = 2 and 11/3 = 3.66, we, thus, obtain [2/3] = 0, [4/3] = 1, [6/3] = 2, and [11/3] = 3. It is then possible to express any integer number x in the form: x = m[x/m]+r, where r stands for residue. With the previous examples, we have: 2 = 3[2/3]+ 4 = 3[4/3] 1 6 = 3[6/3] 0 11=3[11/3] + 2. We observe that the residues are positive integers that range from r =0tor=m - 1. We can define such residues in the form r=x - m[x/m]. By convention, one designates the residues according to any of the following equivalent notations: r = x mod m x = r[m] ==r(mod m), which reads as, "r equals x modulo m," or "X equals r modulo m," it being understood which one is the residue. Here, we shall mainly use the second definition, with the convention that "mod m" carries over the entire right-hand side expression or even the full line (this to avoid a parenthesis inflation, unless parentheses are introduced Modular arithmetic and Euler's theorem otherwise). The following are basic examples: (3 4) mod 6 = 7 mod 6 = 1 (8 7) mod 15 = 15 mod 15 = 0 (7 4) mod 4 = 3 mod 4 = 3 (2x3) mod 4 = 6 mod 4 = 2 (7 x 9) mod 11 = 63 mod 11 = 8. In modular arithmetic, addition and multiplication are commutative, associative, and distributive operations, meaning the following properties: (a b) mod m = (a mod m) + (b mod m) mod m, (a X b) mod m = (a mod m) x (b mod m) mod m, [a x (b + c)] mod m = (axb) mod m + (a X c) mod m) mod m. Here are two other obvious or less trivial properties (k = integer): (-a) mod m = (m - a) mod m = [(m 1) X a] mod m, (kxm) mod m = 0, (T10) mod (k X m) = kx (a mod m). (T11) While addition and multiplication are straightforward in modular arithmetic, division is not. For instance, what is the residue r as defined through r = (11/5) mod 3? In modular arithmetic, r should be the number that satisfies 5 X1 = 11 mod3 = 2. The onl