Algorithmic Algebra - A Classical Introduction to Cryptography: Applications for Communications Security - page 159

6.2.2 Definition of Z n

We have already mentioned the group Z n . The structure of this group is however richer.
It actually has a ring structure.

We already mentioned its additive structure of an Abelian group. We can similarly
define the multiplication by

( a , b ) → a × b mod n .

Once again, we do not suggest writing it a + b since it may introduce confusion.

This is actually a “pedestrian way” to define Z n . A more intellectual one consists
of saying that Z n is the quotient ring of ring Z by the principal ideal n Z generated by n .
We have seen that we can make a quotient of an Abelian group by one of its subgroups.
For rings, we quotient by ideals. An ideal is a subset I such that

1. I is a subgroup for the addition;
2. for any a ∈ I and any b ∈ R ,wehave ab ∈ I .

In this case, quotients are defined similarly as for groups. The multiplication of the
class of a by the class of b is simply the class of ab . An arbitrary set A can generate
an ideal

: it is simply the set of all ring elements which can be written as a finite
combination a 1 x 1 +···+

A

A . When A is
reduced to a single element, the ideal is principal . The principal ideal generated by n
is thus simply the set of all integers for which n is a factor. Making a quotient by this
ideal simply means that we further consider all multiples of n as zero elements: we
thus reduce modulo n . Classes of residues modulo n are uniquely represented by their
representative in

a n x n with a 1 ,..., a n ∈ R and x 1 ,..., x n ∈

{ 0 , 1 ,..., n − 1 } .

Since we will later make an extensive use of Z n , it is important to get familiar with
it. We will use examples with n

= 35. As a computation example, we can see that

27 + 19 mod 35 = 11

+ =

because 27 46 and for 46 mod 35, we make the Euclidean division of 46 by

35. We get a quotient of 1 with a remainder of 11 (indeed, 46

19

= 1 × 35 + 11), thus

46 mod 35 = 11. As another example, we have

17 × 22 mod 35 = 24

because 17 × 22 = 374 and the quotient of 374 by 35 is 10 with a remainder of 24

(indeed, 374 = 10 × 35 + 24).