Basic Facts about Rings of Integers Modulo

2 Basic Facts about Rings of Integers Modulo n 

Most of the following facts are only needed in the constructions based on the factoring assumption. There, the basic structure used is the ring of integers modulo n, where n is a chosen number that is hopefully hard to factor. Particular attention is paid to quadratic residues and square roots, because the squaring function plays an important part in the following schemes. 

For any positive integer , the ring of integers modulo n is denoted by and its multiplicative group by Z . Elements of Z and their residue classes are not distinguished in the notation. 

The Chinese remainder theorem reduces the problem of determining the structure of rings Z to rings Z r for prime powers pL The most important theorem about the latter is lliat for p 2, each multiplicative group Z r is cyclic. 

A generator is also called a primitive root modulo p . The total number of generators is this is easy to see from the above-mentioned isomorphism to 

---