For The Love of Cycling — ℤₙ* The Multiplicative group for ℤₙ modulo n

For The Love of Cycling — ℤₙ* The Multiplicative group for ℤₙ modulo n

Okay … let me ask you. For the numbers up to 10, which numbers do not share any factors with 10? Remember that 10 has factors of 2 and 5, so you can’t use any number which have any of these factors.

Let’s try … 1 … that’s okay.
Let’s try … 2 … nope! It is 2 ｘ1. Reject!
Let’s try … 3 … that’s okay.
Let’s try … 4 .. nope. It is 2 ｘ2. Reject!
Let’s try … 5 … nope. It is 5 ｘ 1. Reject!
Let’s try … 6 … It is 3 ｘ2. Reject!
Let’s try … 7… that’s okay.
Let’s try … 8… It is 2 ｘ2ｘ2. Reject!
Let’s try … 9… that’s okay.

And so we get 1, 3, 7 and 9 [here]. This has the name of the multiplicative group for ℤₙ modulo n.

Sometimes the symbols used on cryptography are a little difficult to understand, but often they are not too difficult, as the operations themselves are quite simple. If you can get to grips with the modulus operator, the rest is fairly easy.

In number theory, ℤₙ is the set of non-negative integers less than n ({0,1,2,3…n-1}). ℤₙ* is then a subnet of this which is the multiplicative group for ℤₙ modulo n. The set ℤₙ* is the set of integers between 1 and n that are relatively prime to n (ie they do not share any factors). If n is prime, then ℤₙ* is the values up to (n − 1). Note that is is also shown as (ℤ/nℤ)ˣ.

If we want g to be generated from multiplicative group for ℤₙ modulo n, we would define:

g ∈ ℤₙ*

If we want g to be generated from multiplicative group for ℤₙ modulo n², we would define:

g ∈ ℤₙ₂*

An example is [here].

For example, if we have 9, then the ℤₙ* group is:

Multiplicative group for Zn is:
1 2 4 5 7 8

because 3 is a factor of 9 (3ｘ3), along with 6 (2ｘ3).

For 91 (7 ｘ13) we get:

Multiplicative group for Zn is:
1 2 3 4 5 6 8 9 10 11 12 15 16 17 18 19 20 22 23 24 25 27 29 30 31 32 33 34 36 37 38 40 41 43 44 45 46 47 48 50 51 53 54 55 57 58 59 60 61 62 64 66 67 68 69 71 72 73 74 75 76 79 80 81 82 83 85 86 87 88 89 90 
The number of values is:  72

We can see that factors of 7 are not included, such as 14, 21, etc, and also factors of 13, such as 26, 39, and so on.

If the value is a prime number, all the values will be included up to (n-1), as it will not share any factors. For example, 97 is a prime number:

Value is:	97
Multiplicative group for Zn is:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 
The number of values is:  96

The following is an outline of the code:

number=1763*1763

import sys

count=0
def gcd(a,b):
    while b > 0:
        a, b = b, a % b
    return a

print "Value is:\t",number
print "Multiplicative group for Zn up to 100 is:"

for i in range(1,100):
	if (gcd(number,i)==1): 
		print i,
		count=count+1

print "\nThe number of values is: ",count

In this case we basically just use the greatest common denominator (GCD) function to determine if the value has a shared factor with our input.

But what is n is a prime number. What do you think we will get? Well, all the numbers are going to be possible up to n-1, as n will not share any values with any of them:

Value is: 7
Multiplicative group for Zn is:
1 2 3 4 5 6 
The number of values is: 6

When N is a prime number … something special happens .. we start to cycle

In discrete logarithms we often use the form:

Y = Gˣ (mod N)

The great property of this is that if we select g from ℤₙ* and where n is a prime number the result will be cyclic (where we keep repeating the output in a sequence). For N=7, we can select 2,3,4,5 or 6, so let’s select 6:

>>> print 6**1 % 7
6
>>> print 6**2 % 7
1
>>> print 6**3 % 7
6
>>> print 6**4 % 7
1

The output is then {6,1,6,1 …}

Sometimes, though, something special happens, and we get a sequence from 0 to N-1. So let’s select N=11, we pick a g value of 2:

Y =2¹ (mod 11) = 2
Y = 2² (mod 11) = 4
Y = 2³ (mod 11) = 8
Y =2⁴ (mod 11) = 5
Y =2⁵ (mod 11) = 10
Y =2⁶ (mod 11) = 9
Y =2⁷ (mod 11) = 7
Y =2⁸ (mod 11) = 3
Y =2⁹ (mod 11) = 6
Y = 2¹⁰ (mod 11) = 1
Y =2¹¹ (mod 11) = 2 (repeat)
Y =2¹² (mod 11) = 4 (repeat)

and so we cycle back.

We now have a repeating sequence for the values of 1 to N-1 {2, 4, 8, 5, 10, 9, 7, 3, 6, 1, 2, 4, 8 …}. This is defined as a cyclic group G of order n with a generator g, and is used within discrete logarithms, such as the value we use for the Diffie-Hellman method. We thus find our the prime number we are using, and then find a value of g that allowed for this cyclic group.

The cyclic group for a prime is written as (ℤ/nℤ)*. Thus for every prime number, there are values of g which provide us with this special group [here].

Conclusions

I appreciate that this article was maybe a bit heavy for you to read on the bus into work, but let the ideas settle for a while, and come back to it later. A good idea is to grab a pen and paper, and just doodle, or get out Python and try things yourself.