Definition: Let us consider $G$ a set and a binary operation * over $G$ such that:

(closure) $\forall g_1,g_2\in G$, then $g_1*g_2\in G$.
(identity) $\exists e \in G$ such that $\forall g\in G$ $g*e=g=e*g$.
(inverse) $\forall g\in G$ $\exists y \in G$ such that for $g*y=e=y*g$.
(associativity) $\forall g_1,g_2,g_3\in G$, then $$(g_1*g_2)*g_3=g_1*(g_2*g_3)\in G.$$

The pair $(G,*)$ is a group.

Definition: A group $(G,*)$ is abelian if

(commutativity) $\forall g_1,g_2\in G$, then $$g_1*g_2=g_2*g_2\in G.$$

$(\mathbb Z, +)$ is an abelian group.
$(\mathbb R, +)$ is an abelian group.
$(\mathbb N, +)$ is NOT group.
$(\mathbb Z, \cdot)$ is NOT group.
$(\mathbb R, \cdot)$ is NOT group.
$(\mathbb R \setminus \{0\}, \cdot)$ is an abelian group.
If $(V,+,*) $ is a vector space over the field $k$. Then, $(V,+)$ is an abelian group.
Let $M(n, \mathbb R)$ be the set of square matrices of dimension $n$ with the element-wise sum is an abelian group. $M(n, \mathbb R)$ with the product is NOT a group.
Let $GL(n, \mathbb R)$ be the set of invertible square matrices of dimension $n$ with the product is a group, but it is not abelian.
$\mathbb Z_N : =\{0,1,\dots,N-1\}$ with the operation $+ \mod N$ is an abelian group.

Excercise: write down the proofs.

Definition: Let $(G,*)$ be group. A subset $H\subseteq G$ is a subgroup if $(H,*)$ is a group.

The groups $(\{e\},*)$ and $(G,*)$ are trivial subgroups of $(G,*)$.

Proposition: Let $G$ be a group and $a,b,c\in G$. If $ac=bc$, then $a=b$.

Example: $( \mathbb Z_{24}, \cdot)$ is not a group.

In [1]:

print(( 15*2 )% 24 == (3*2) %24, 15 % 24 == 3 % 24 ) 

True False

Group Notation and Exponentiation¶

Let $(G,*)$ be group, $g,h\in G$ and $m \in \mathbb N^+$. It is usually convenient to encode the $*$ with a more familiar notations such as multiplication and sum.

Multiplicative notation: we set $g\cdot h=g*h$, we denote the identity as $1$ and the inverse as $g^{-1}$, and $g*g*g\dots*g$ the $m$-times operation as $g^m$.

Additive notation: we set $g+ h=g*h$, we denote the identity as $0$ and the inverse as $-g$, and $g*g*g\dots*g$ $m$-times operation as $m\cdot g$.

Exercise: Can you guess what is $g^{m}\cdot g^{m'}$? $mg +{m'}g$? $g^{-b}$?

Additive: $mg = m \cdot g = g+g+\dots+g$ $\Rightarrow$ if $g,h \in G$ and $m, m' \in \mathbb Z$:
- $(mg) + (m'g) = (m + m')g$;
- $m(m'g) = (mm')g$;
- $1 \cdot g = g$;
- $(mg) + (mh) = m(g + h)$, only if abelian.
Multiplicative: $g^m = g \cdot g \cdots g$ $\Rightarrow$ if $g,h \in G$ and $m,
```
  m' \in \mathbb Z$:
```
- $g^m \cdot g^{m'} = g^{m+m'}$;
- $(g^m)^{m'} = g^{mm'}$;
- $g^1 =g$;
- $g^m \cdot h^m = (gh)^m$, only if abelian.

CompFact: if the group operation can be computed in polynomial time then so can exponentiation.

We can verify for some values that $m\cdot (a+b) \mod N= m\cdot a+m\cdot b\mod N$, and other properties.

In [2]:

N=11
m=9
a=3
b=5
print(m*a%N, m*b%N )
print((m*(a+b))%N )

5 1
6

In [4]:

k=6
print(m*(k*a)%N, (m*k)*a % N )

8 8

Proposition: Let $(G,\cdot)$ be group and $g\in G $. Then $$ <g>= \{g^k : k\in \mathbb Z\}$$ is a subgroup of $G$.

If there exists an element $g$ such that $G=<g>$, we say that $G$ is cyclic and $g$ is a generator of $G$.

In [5]:

N=24
g=1
for k in range(100): print(k*g%N, end=',') 

0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,0,1,2,3,

In [6]:

G={k*g%N for k in range(100)}
print(G)

{0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23}

In [7]:

g=4
for k in range(100): print(k*g%N, end=',')

0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,16,20,0,4,8,12,

In [8]:

print(24*g%N) 
print(6*g%N) 

0
0

In [9]:

h=5
for k in range(100): print(k*h%N, end=',') 

0,5,10,15,20,1,6,11,16,21,2,7,12,17,22,3,8,13,18,23,4,9,14,19,0,5,10,15,20,1,6,11,16,21,2,7,12,17,22,3,8,13,18,23,4,9,14,19,0,5,10,15,20,1,6,11,16,21,2,7,12,17,22,3,8,13,18,23,4,9,14,19,0,5,10,15,20,1,6,11,16,21,2,7,12,17,22,3,8,13,18,23,4,9,14,19,0,5,10,15,

In [10]:

print(6*h%N)
print(24*h%N) 

6
0

Definition: Let $(G,*)$ be group. $|G|$ is the order of the group, and if $|G|$ is finite we say that $G$ is a finite group.

Lemma 1: Let $(G,\cdot)$ be a finite group with $m = |G|$, the order of the group. Then for any element $g\in G$, $g^m = 1$. Moreover, for any element $x\in \mathbb Z$, $g^x = g^{[x\mod m]}$.

Example: $\mathbb Z_N=\{0,1,\dots,N-1\}$ with the operation $+ \mod N$ is an abelian group of order $N$. Then for any $g \in \mathbb Z_N$ we have $ Ng=0 \mod N $. Moreover for any element $x\in \mathbb Z$ we have $x\cdot g = [x\mod N]\cdot g \mod N$.

The Group $\mathbb Z_N^*$¶

$\mathbb Z_N=\{0,1,\dots,N-1\}$ with the operation $[+ \mod N]$ is an abelian group. However, $\mathbb Z_N$ with $[\cdot \mod N]$ is not a group. (Why?)

Let us consider $N=12$ and the multiplication $[\cdot \mod 12]$. We can observe:

(closure) $\forall a,b\in \mathbb Z_{12}$, then $a\cdot b = [a\cdot b \mod N] \in \mathbb Z_{12}$.
(identity? NO ) For all $\forall a\in \mathbb Z_{12}$ such that $a\ne0$ we have $g\cdot 1=g=1\cdot g$.
- But $\mathbb Z_{12}-\{0\}$ is close respect to $\cdot$ and 1 can act as identity!

(inverse?NO) Not every element of $\mathbb Z_{12}-\{0\}$ is invertible, e.g. 4 and 3.

However, we can consider the set of elements of $\mathbb Z_{N}$ which are invertible mod $N$. That can be characterized as $$\mathbb Z_{N}^{*} := \{a \in \mathbb Z_{N}: gcd(N,a)=1\} $$

In [11]:

from math import gcd
N=12
ZNs=[a for a in range(N) if gcd(a,N)==1 ]
print(ZNs)

[1, 5, 7, 11]

In [12]:

for a in ZNs: 
    print([a*b % N for b in ZNs])

[1, 5, 7, 11]
[5, 1, 11, 7]
[7, 11, 1, 5]
[11, 7, 5, 1]

In [13]:

p=13
Zps=[a for a in range(p) if gcd(a,p)==1 ]
print(Zps)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

Theorem: Let $N > 1$ be an integer. Then $\mathbb Z_{N}^{*}$ is an abelian group under multiplication modulo N .

Proof:

(identity) [$\exists e \in G$ such that $\forall g\in G$ $g*e=g=e*g$.] $gcd(N,1)=1 \Rightarrow 1 \in \mathbb Z_{N}^{*}$. Since $\forall a\in \mathbb Z_{N}^*$ we have $g\cdot 1=g=1\cdot g$, 1 is the identity.
(inverse) [$\forall g\in G$ $\exists y \in G$ such that for $g*y=e=y*g$.] By definition all the elements are invertible.
(associativity) and (commutativity) follows from the properties of the integers and the definition of product.
(closure) [$\forall g_1,g_2\in G$, then $g_1*g_2\in G$.] $\forall a,b\in \mathbb Z_{N}^{*}$, then $a\cdot b = [a\cdot b \mod N] \in \mathbb Z_{N}$. We have to show that $a\cdot b$ is invertible. For this purpose we show that $[ b^{-1}\cdot a^{-1} \mod N]$ is its inverse:

$$[a\cdot b \mod N][ b^{-1}\cdot a^{-1} \mod N]=[(a\cdot b)\cdot (b^{-1}\cdot a^{-1}) \mod N]=$$ $$=[a(\cdot b\cdot b^{-1})\cdot a^{-1} \mod N]=[a\cdot 1 \cdot a^{-1} \mod N]=$$ $$=[(a\cdot 1) \cdot a^{-1} \mod N]=[a\cdot a^{-1} \mod N]=[1\mod N]=1$$

Q.E.D.

Remark: We used a lot that being invertible and gcd equal one are equivalent, but this is not obvious! Moreover, can you name all the property we used in the last equation?

Euler phi function¶

For an integer $N>1$ the Euler phi function is $$\phi(N)= |\{a \in \mathbb Z_{N}: gcd(N,a)=1\}|=|\mathbb Z_{N}^{*}|$$

If $p$ is prime $\phi(p)=p-1$. Indeed, every non-zero element of $\mathbb Z_{p}$ is coprime with $p$.
If $N$ is the product of two distinct primes $p,q$, $\phi(N)=(p-1)(q-1)$.

Theorem: If $N= \prod_{j=1}^k p_j^{e_j}$ with $p_1<\dots<p_k$ prime integers and $e_1,\dots e_k\in\mathbb N^+$, $$ \phi(N)= \prod_{j=1}^k p_j^{e_j-1}(p_j-1).$$

Therefore, the order of $\mathbb Z_{N}^{*}$ can be computed using this formula if we know the factorisation of $N$.

CompOpenQuest: Given $N$, can we compute $\phi(N)$??

In [14]:

p=13
Zps=[a for a in range(p) if gcd(a,p)==1 ]
print(Zps)
print(len(Zps)==p-1)

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
True

In [15]:

N=21
ZNs=[a for a in range(N) if gcd(a,N)==1 ]
print(ZNs)
print(len(ZNs)==(3-1)*(7-1))

[1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]
True

We can derive from Lemma 1 the following:

Corollary Let $N>1$ be an integer and $a\in \mathbb Z_{N}^{*}$. Then $$ a^{\phi(N)}=1 \mod N.$$

Corollary Let $p>1$ be a prime integer and $a\in \mathbb Z_{p}^{*}$. Then $$ a^{p-1}=1 \mod p.$$

In [16]:

N=21
phiN=(3-1)*(7-1)
ZNs=[a for a in range(N) if gcd(a,N)==1 ]
for g in ZNs: print(g**phiN %N, end=',') 

1,1,1,1,1,1,1,1,1,1,1,1,

In [17]:

p=13
phip=p-1
Zps=[a for a in range(p) if gcd(a,p)==1 ]
for g in Zps: print(g**phip %p, end=',') 

1,1,1,1,1,1,1,1,1,1,1,1,

Example (cyclic subgroups)¶

We want to generate a cyclic subgroup $G=<g>$ of $\mathbb Z_N^*$. From Lemma 1 we know in advance that the group as at most $\phi(N)$ elements.

In [18]:

N=21
phiN=(3-1)*(7-1)
print(phiN)
ZNs=[a for a in range(N) if gcd(a,N)==1 ]
print(len(ZNs)==phiN)

12
True

In [19]:

ZNs

Out[19]:

[1, 2, 4, 5, 8, 10, 11, 13, 16, 17, 19, 20]

In [20]:

g=4
G={g**k%N for k in range(227)}
print(G)

{16, 1, 4}

Computational aspects¶

Modelling $\mathbb Z_N$ via python classes¶

$\mathbb Z_N=\{0,1,\dots,N-1\}$ with the operation $+ \mod N$ is an abelian group.

Ex: 1) Define the group via python classes.

2) Write functions to verify that your class is a group._

Definition¶

We want to represent $\mathbb Z_N$ as python class.

In [21]:

class group_element:
    def __init__(self, el, G ):
        self.el=el
        self.group=G
        self.can_rep=G.can_rep(el)
    def __repr__(self):
        return "{0}".format(self.can_rep)
    def __add__(self,other):
        return G.sum(self,other)
    def __sub__(self, other):
        return G.sum(self,G.inverse(other))
    def __eq__(self, other):
        return self.can_rep==other.can_rep

In [22]:

class ZZn:
    def __init__(self, n):
        self.order = n
        self.set={i for i in range(n)}
    def sum(self,a,b):
        return group_element((a.can_rep+b.can_rep)%self.order,self)
    def can_rep(self,a):
        return a%self.order
    def inverse(self,a):
        return group_element(-a.can_rep%self.order,self)
    def __repr__(self):
        return "Group (ZZn,+) of order {0}".format(self.order)
    def __eq__(self, other):
        return self.order==other.order
    def __call__(self, a):
        return group_element(a,G)

In [23]:

G=ZZn(24)
print(G)
G

Group (ZZn,+) of order 24

Out[23]:

Group (ZZn,+) of order 24

In [24]:

a=G(8)-G(9)
b=G(8)-G(-9)
print(a,b)

23 17

In [25]:

print(a.group)

Group (ZZn,+) of order 24

We want to verify:

(identity) $\exists e \in G$ such that $\forall g\in G$ $g*e=g=e*g$.

In [28]:

def identity_G(e,G):
    R=G.set
    for g in R: 
        if G(g) + G(e)!= G(g) or G(g)!= G(g)+ G(e):  
            return False
    return True

print(identity_G(0,G),identity_G(24,G),identity_G(5,G))

True True False

We want to verify:

(associativity) $\forall g_1,g_2,g_3\in G$, then $(g_1*g_2)*g_3=g_1*(g_2*g_3)\in G$.

In [29]:

def associativity(G):
    R=G.set
    for x in R:
        for y in R:
            for z in R: 
                if ((G(x) + G(y))+G(z)) != (G(x) + (G(y)+G(z))): return False
    return True

associativity(G)                    

Out[29]:

True

Groups¶

Group Notation and Exponentiation¶

Example¶

Cyclic groups¶

Example¶

Finite groups¶

The Group $\mathbb Z_N^*$¶

Euler phi function¶

Example¶

Example¶

Example (cyclic subgroups)¶

Computational aspects¶

Modelling $\mathbb Z_N$ via python classes¶

Definition¶

Verification¶