In abstract algebra, a ring is a set with two operations (usually addition and multiplication) where addition forms an abelian group and multiplication is associative and distributes over addition. A group is a set with a single operation that satisfies closure, associativity, identity, and inverse properties.
Integers and Modular Arithmetic
The set of integers \( \{ \dots, -2, -1, 0, 1, 2, \dots \} \) is denoted by the symbol \( \mathbb{Z} \), i.e., \( \mathbb{Z} = \{ \dots, -2, -1, 0, 1, 2, \dots \} \), and is called the ring of integers or an additive group. The group of integers modulo \( n \) is a subset of \( \mathbb{Z} \) and is denoted by \( \mathbb{Z}/n\mathbb{Z} \), but we use the shorthand \( \mathbb{Z}_{n} \). This subset contains the following elements (because we compute modulo \( n \)):
\( \mathbb{Z}_{n} = \{ 0, 1, 2, \dots, n - 1 \}\)
Notice that whenever we perform addition or multiplication in \( \mathbb{Z}_{n} \), we always compute the result modulo \( n \) to obtain an integer in \( \mathbb{Z}_{n} \). To illustrate this, let us look at \( n = 5 \):
\( \mathbb{Z}_{5} = \{ 0, 1, 2, 3, 4 \}\)
When adding \( 3 \) and \( 4 \) in \( \mathbb{Z}_{5} \), we do the following: \( (3 + 4) \: mod \: 5 = 7 \: mod \: 5 = 2 \). Likewise, when multiplying \( 3 \) by \( 4 \) in \( \mathbb{Z}_{5} \), we have: \( (3 \cdot 4) \: mod \: 5 = 12 \: mod \: 5 = 2 \).
Units and Multiplicative Groups
An integer \( a \) in \( \mathbb{Z}_{n} \) has an inverse if the greatest common divisor of \( a \) and \( n \) is 1, i.e., \( \gcd(a, n) = 1 \) (see "The extended Euclidean algorithm" for more information). The integer \( a \) is then called a unit. The set of units (all integers with an inverse in \( \mathbb{Z}_{n} \)) is denoted by \( (\mathbb{Z}/n\mathbb{Z})^{*} \). Again, we use the shorthand \( \mathbb{Z}_{n}^{*} \). If \( a_{1} \) and \( a_{2} \) are units, then their product \( (a_{1} \cdot a_{2}) \: mod \: n \) is also always a unit (i.e., \( a_{1} \cdot a_{2} \) is in the group \( \mathbb{Z}_{n}^{*} \)), but the sum \( (a_{1} + a_{2}) \: mod \: n \) may NOT be a unit (i.e., \( a_{1} + a_{2} \) is in \( \mathbb{Z}_{n} \) but may not be in \( \mathbb{Z}_{n}^{*} \)). We see the difference in the two sets \( \mathbb{Z}_{8} \) and \( \mathbb{Z}_{8}^{*} \):
- \( \mathbb{Z}_{8} = \{ 0, 1, 2, 3, 4, 5, 6, 7 \}\)
- \( \mathbb{Z}_{8}^{*} = \{ 1, 3, 5, 7 \} \)
If we choose \( n \) to be a prime number \( p \), then for all integers \( a \) except 0 in \( \mathbb{Z}_{p} \), we have \( \gcd(a, p) = 1 \), which means that \( \mathbb{Z}_{p}^{*} \) contains all integers from \( \mathbb{Z}_{p} \) except 0, i.e.:
\( \mathbb{Z}_{p}^{*} = \{ 1, 2, 3, \dots, p - 1 \}\)
For example, for \( p=7 \), the only difference between the two sets \( \mathbb{Z}_{7} \) and \( \mathbb{Z}_{7}^{*} \) is the integer 0:
- \( \mathbb{Z}_{7} = \{ 0, 1, 2, 3, 4, 5, 6 \}\)
- \( \mathbb{Z}_{7}^{*} = \{ 1, 2, 3, 4, 5, 6 \} \)
Euler's Phi Function
The number of elements in \( \mathbb{Z}_{n}^{*} \) is denoted by \( \phi(n) \), named after the famous Swiss mathematician Euler, and is called Euler's phi function. As we saw previously, if \( n \) is a prime number \( p \), then \( \phi(p) = p-1 \). The number of elements in a group \( G \) is also called the order of \( G \) and is written as \( \left| G \right| \). The order of:
- \( \mathbb{Z}_{n} \) is \( \left| \mathbb{Z}_{n} \right| = n \) where \( n \) is a composite number
- \( \mathbb{Z}_{n}^{*} \) is \( \left| \mathbb{Z}_{n}^{*} \right| = \phi(n) \) where \( n \) is a composite number
- \( \mathbb{Z}_{n}^{*} \) is \( \left| \mathbb{Z}_{n}^{*} \right| = \phi(n) = (p-1) \cdot (q-1) \) where \( n = p \cdot q \) and \( p \) and \( q \) are prime numbers
- \( \mathbb{Z}_{p}^{*} \) is \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \) where \( p \) is a prime number
Euler's phi function \(\phi(n)\) can be computed efficiently when the prime factorization of \(n\) is known:
For a prime power \(p^k\): \(\phi(p^k) = p^k - p^{k-1} = p^k(1 - \frac{1}{p})\)
For a product of prime powers: \(\phi(n) = n \prod_{p|n} (1 - \frac{1}{p})\)
For example, \(\phi(36) = \phi(2^2 \cdot 3^2) = 36 \cdot (1 - \frac{1}{2}) \cdot (1 - \frac{1}{3}) = 36 \cdot \frac{1}{2} \cdot \frac{2}{3} = 12\)
Modular Exponentiation Rules
If, for example, we choose the elements \( x \), \( a \), and \( b \) from the group \( \mathbb{Z}_{p}^{*} \) and want to compute \( x^{a + b} \: mod \: p \), then in the exponent we actually compute \( a + b \) modulo the order of the group, i.e., \( a + b \: mod \: (p-1) \) because \( \left| \mathbb{Z}_{p}^{*} \right| = \phi(p) = p-1 \). So, what we actually compute is \( x^{a + b \: mod \: (p-1)} \: mod \: p \). The same is true if we had chosen one of the other groups: we always compute modulo the order of the group in the exponent. Therefore, next time you look at an equation from a cryptosystem and wonder why they suddenly compute, for example, modulo \( p-1 \) instead of modulo \( p \), it is because the equation is used in the exponent of some integer.
Units are particularly important in cryptography because they have multiplicative inverses, allowing operations like division in modular arithmetic. The existence of these inverses is crucial for many cryptographic algorithms, including RSA, where we need to find values \(e\) and \(d\) such that \(e \cdot d \equiv 1 \pmod{\phi(n)}\).
Important Theorems
Fermat's Little Theorem: If \(p\) is a prime number and \(a\) is not divisible by \(p\), then \(a^{p-1} \equiv 1 \pmod{p}\).
Euler's Theorem: For any coprime integers \(a\) and \(n\), \(a^{\phi(n)} \equiv 1 \pmod{n}\). This generalizes Fermat's Little Theorem and forms the mathematical foundation of the RSA cryptosystem.
Applications in Cryptography
- RSA: Uses the fact that \(m^{ed} \equiv m \pmod{n}\) when \(ed \equiv 1 \pmod{\phi(n)}\)
- Diffie-Hellman: Operates in the multiplicative group \(\mathbb{Z}_p^*\) where \(p\) is prime
- ElGamal: Relies on modular exponentiation in \(\mathbb{Z}_p^*\)
- Digital Signatures: Many schemes use properties of these groups for verification