The Group Zp*

The group Z_p*

Cryptosystems using arithmetic in Z_p* include the Diffie-Hellman Key Agreement Protocol and the Digital Signature Algorithm (DSA).
The multiplicative group Z_p* 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 Z₁₁* uses the integers from 1 to 10. Multiplication in Z₁₁* finishes by taking the remainder when the result is divided by 11. Here are some examples of multiplication in Z₁₁*:
4 7 mod 11
= 28 mod 11
= 6
9 5 mod 11
= 45 mod 11
= 1.
Thus in Z₁₁^*, 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 Z₁₁*, 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 Z_n* only if gcd(x,n) = 1. Only when n is a prime number p will all elements in Z_n* have a multiplicative inverse. Thus Z_p* is a group only when p is a prime number.
Other operations

While multiplication is the main operation in the multiplicative group Z_p*, 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 Z₁₁*, 7 / 9 = 7 9^-1 = 7 5 mod 11 = 35 mod 11 = 2.
It is also possible to define exponentiation in Z_p* as repeated multiplication. For example, the exponentiation 7³ in Z₁₁ can be achieved by multiplying 7 7 7 mod 11 = 343 mod 11 = 2.

Certicom is a trademark of the Certicom Corp. Copyright Certicom Corp. 1997. All rights reserved.

Comments or Questions about this site? Please contact info@certicom.ca

The group Z_p* Cryptosystems using arithmetic in Z_p* include the Diffie-Hellman Key Agreement Protocol and the Digital Signature Algorithm (DSA). The multiplicative group Z_p* 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 Z₁₁* uses the integers from 1 to 10. Multiplication in Z₁₁* finishes by taking the remainder when the result is divided by 11. Here are some examples of multiplication in Z₁₁: 4 7 mod 11 = 28 mod 11 = 6 9 5 mod 11 = 45 mod 11 = 1. Thus in Z₁₁^, 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 Z₁₁*, 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 Z_n* only if gcd(x,n) = 1. Only when n is a prime number p will all elements in Z_n* have a multiplicative inverse. Thus Z_p* is a group only when p is a prime number. Other operations While multiplication is the main operation in the multiplicative group Z_p, 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 Z₁₁, 7 / 9 = 7 9^-1 = 7 5 mod 11 = 35 mod 11 = 2. It is also possible to define exponentiation in Z_p as repeated multiplication. For example, the exponentiation 7³ in Z₁₁ can be achieved by multiplying 7 7 7 mod 11 = 343 mod 11 = 2.
Certicom is a trademark of the Certicom Corp. Copyright Certicom Corp. 1997. All rights reserved.
			Comments or Questions about this site? Please contact info@certicom.ca

The group Zp*

Multiplicative Inverses

Other operations

The group Z_p*