The group Zp*

 

The group Zp* Cryptosystems using arithmetic in Zp* include the Diffie-Hellman Key Agreement Protocol and the Digital Signature Algorithm (DSA). The multiplicative group Zp* uses only the integers between 1 and p - 1 (p is a prime number), and its basic operation is multiplication. Multiplication ends by taking the remainder on division by p; this ensures closure. The multiplicative group Z11* uses the integers from 1 to 10. Multiplication in Z11* finishes by taking the remainder when the result is divided by 11. Here are some examples of multiplication in Z11*: 4 7 mod 11 = 28 mod 11 = 6 9 5 mod 11 = 45 mod 11 = 1. Thus in Z11*, 4 7 = 6 and 9 5 = 1. Notice that both the calculations shown have answers between 1 and 10. Multiplicative Inverses Each number x in a multiplicative group has a multiplicative inverse element in the group; that is an integer x-1 such that x x-1 = 1 in the group. In Z11*, 9-1 = 5 since 9 5 mod 11 = 1. In a multiplicative group, each element must have a multiplicative inverse. Consider the integers modulo the (composite) number 15. It is possible to define multiplication on the numbers from 1 to 14, always finishing with reduction modulo 15. With this system, the number 6 has no inverse, since there is no number y such that 6 y mod 15 = 1:
	6 0 mod 15 = 0		6 1 mod 15 = 6		6 2 mod 15 = 12			6 3 mod 15 = 3		6 4 mod 15 = 9
	6 5 mod 15 = 0		6 6 mod 15 = 6		6 7 mod 15 = 12			6 8 mod 15 = 3		6 9 mod 15 = 9
	6 10 mod 15 = 0		6 11 mod 15 = 6		6 12 mod 15 = 12			6 13 mod 15 = 3		6 14 mod 15 = 9.
	The reason for this is that gcd(6,15) = 3 > 1; a number x has a multiplicative inverse in Zn* only if gcd(x,n) = 1. Only when n is a prime number p will all elements in Zn* have a multiplicative inverse. Thus Zp* is a group only when p is a prime number. Other operations While multiplication is the main operation in the multiplicative group Zp*, other operations can be derived from multiplication. For example, the division x / y can be performed as the multiplication x (y-1) mod p. In Z11*, 7 / 9 = 7 9-1 = 7 5 mod 11 = 35 mod 11 = 2. It is also possible to define exponentiation in Zp* as repeated multiplication. For example, the exponentiation 73 in Z11 can be achieved by multiplying 7 7 7 mod 11 = 343 mod 11 = 2.