Elliptic Curve Classroom (JAVA required)





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.


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