What Is Order of Element

EC Cryptography Tutorials - Herong's Tutorial Examples

∟What Is Order of Element

This section describes the order of a given element in a finite Abelian Group, which is defined as the least positive integer n, such that the scalar multiplication of n and P is 0, where 0 is the identity element.

What Is the Order of an Element in a Finite Abelian Group? The order of an element P in a finite Abelian Group is the least positive integer n, such that the scalar multiplication of n and P is 0, where 0 is the identity element.

The above definition is based on the following fact:

For any given element P in a finite Abelian Group, a positive integer m exists, such that the scalar multiplication of m and P is 0. Here is the proof:

Given element P in an finite Abelian Group G
a positive integer m exists, such that mP = 0.

Proof:
   Since G is finite, we must have 2 distinct integers i and j, such that
      iP = jP
   Otherwise, we will have infinite elements in G.

   If j > i, we found m: m = j-i and m>0:
      mP = (j-i)P = 0, because iP = jP

   If i > j, we found m: m = i-j and m>0:
      mP = (i-j)P = 0, because iP = jP

Group Example 1 - Here is the additive Abelian group of integers: 0, 1, 2, ..., 23 and the addition operation with modular reduction of 24.

Order of Element Example 1.1 - The order of integer 3 is 8, because:

P = 3
2P = 6
3P = 9
4P = 12
5P = 15
6P = 18
7P = 21
8P = 0

Order of Element Example 1.2 - The order of integer 4 is 6, because:

P = 4
2P = 8
3P = 12
4P = 16
5P = 20
6P = 0
...

Group Example 2 - Let's look at the multiplicative Abelian group of the Binary Field GF(3^2)/(x^2+1).

The element set has 9 binary polynomials: 0, 1, 2, x, x+1, x+2, 2x, 2x+1, 2x+2.
The addition operation is the normal algebra addition with coefficients reduced by modulo 3.
The identity element is the binary polynomial: 0.