Group Theory

Groups $G$ are algebraic structures which are set and has a binary operation $⨁$ that combines two elements $a,b$ of the set to produce a third element $a⨁b$ in the set. The operation is said to have following properties:

1. Closure: $a\oplus b=c\in G$
2. Associative: $(a\oplus b)\oplus c=a\oplus (b\oplus c)$
3. Existence of Identity element: $a\oplus 0=0\oplus a=a$
4. Existence of unique inverse element for every element of the set: $a\oplus b=0$

Example: $\mathbb{Z}$ is an abelian group while $\mathbb{N}$ is not a group as it doesn’t satisfy inverse element property.

Prove uniqueness of inverse.

Take two elements $b\ne c\in G$ such that $a\cdot b=1$ and $a\cdot c=1$. Prove with contradiction $b=c$.

• A set with only closure and associativity, is called Semigroup.
• Monoid has Closure, associativity, Identity.

Groups which satisfy an additional property: commutativity on the set of elements are known as Abelian groups.

One very obvious question that comes to mind is Why abelian varieties are so significant in cryptography?

First these structures provide perfect abstractions to instantiations of them like a group of integers $\mathbb{Z}$, and due to this abstraction, we can prove theorems for these structures that won’t be possible without introducing their properties like commutativity in abelian groups.¹

Now, set underlying the group can have finite elements, namely Finite Groups. For example: ${\mathbb{Z}}_5$, having elements $0,1,2,3,4$.

Prove in a finite group: $g^m=1$.

Isomorphism in groups: Two groups are isomorphic to each other if there exists a map from $f:G\to H$, and written as $G\simeq H$.

• $f$ is bijection
• group operation commutes: $f(g_1{\oplus }_G{g}_2)=f(g_1){\oplus }_{H}f(g_2)$

Direct product in groups: Given two group $G({\oplus }_G),H({\oplus }_H)$, direct group is written as $G\times H:(g,h)$ where $g\in G,h\in H$, containing $|G|\cdot |H|$ elements, and group operation is applied component wise: $(g,h)\oplus (g^{\prime },h^{\prime })=(g{\oplus }_G{g}^{\prime }),(h{\oplus }_H{h}^{\prime })$.

Using this, crt is proven.

Subgroup

Subset $H$ of $G$ satisfying group axioms. Expressed as $H\le G$.

• Improper or Trivial subgroups: $G$ itself and identity element.
• Proper subgroups: all other subgroups.

Theorem:

• Non empty subset $H\subset G$ is a subgroup iff H’s operation is multiplication.
• For subgroup $H\le G$ and $h\in G$, $hH=H=Hh$. Can be generalised to any set $S\subset H⟹SH=H=HS$.

Lagrange's theorem: states that for any finite group $G$, order of every subgroup $H$ divides order of group $G$. Formally, for $H$ being subgroup of $G$, $|G|=n|H|$, for some integer $n$.

Proof: Take an element $r_1\in G,r_1\notin H$, then $|r_{1}H|=|H|$. Since $r_{1}H,H$ are disjoint, then $|r_{1}H\cup H|=2|H|$. Take $n$ such subgroups of $G$, such that $|r_{1}H\cup r_{2}H\cup \cdots \cup r_{n}H|=n|H|=G$.

Corollary: let $G$ be a group, and $g\in G$, then order of $g$ divides $|G|$.

Theorem: If $H_1,H_2,\dots$ are subgroups, then $H_1\cap H_2\cap \dots$ is subgroup of each of $H_1,H_2,\dots$.

• Independent elements: $g_i\notin ⟨g_1,\dots ,g_{i-1},g_{i+1},\dots ,g_m⟩$, i.e. $g_i$ isn’t generated by any of the other elements.
• Every finite group has independent set of generators which can be used to define relations.
• Defining relation: Relation defined using independent elements.

\usepackage{tikz-cd}
\begin{document}
\begin{tikzcd}
    T
    \arrow[drr, bend left, "x"]
    \arrow[ddr, bend right, "y"]
    \arrow[dr, dotted, "{(x,y)}" description] & & \\
    K & X \times_Z Y \arrow[r, "p"] \arrow[d, "q"]
    & X \arrow[d, "f"] \\
    & Y \arrow[r, "g"]
    & Z
\end{tikzcd}
\quad \quad
\begin{tikzcd}[row sep=2.5em]
A' \arrow[rr,"f'"] \arrow[dr,swap,"a"] \arrow[dd,swap,"g'"] &&
  B' \arrow[dd,swap,"h'" near start] \arrow[dr,"b"] \\
& A \arrow[rr,crossing over,"f" near start] &&
  B \arrow[dd,"h"] \\
C' \arrow[rr,"k'" near end] \arrow[dr,swap,"c"] && D' \arrow[dr,swap,"d"] \\
& C \arrow[rr,"k"] \arrow[uu,<-,crossing over,"g" near end]&& D
\end{tikzcd}
\end{document}

Cyclic Groups

Finite groups that can be represented as $g,g⨁g,\cdots$, i.e. a generator $g$, which can create the complete set with the group operation.

Fundamental theorem of finite cyclic groups: if $\mathbb{G}$ is a finite cyclic group such that $|G|=n$, and $k:k|n$, then, $\mathbb{G}[k]$ refers to unique finite cyclic subgroup of $\mathbb{G}$ with order $k$. Proof of above theorem follows from Lagrange’s theorem.

Theorem: Every group of composite order has proper subgroups.

Cauchy’s theorem: states that let $G$ be a finite group, and $p$ a prime dividing $|G|$, then $G$ contains a subgroup of order $p$.

Note: when the group is abelian, i.e. the group operation supports commutativity, the group operation is written mostly additively.

Questions:

• Define and give example of an additive group. Similarly for multiplicative group.
• take a finite group for above example. Modulus can be a prime, composite prime, prime power. give order for all of them.
• define direct product of groups $G\times H$. Prove that for groups $G_1,G_2$, intersection of groups form a subgroup of each base group.

Cofactor

It’s the ratio of order of the curve group and order of the subgroup $hr=n$. Usually, cofactor should be very small in order to avoid subgroup attacks on discrete logarithms. But in pairing-based cryptography, the cofactors of $G_1$, $G_2$ and $G_T$ can be very large.

By multiplying by the cofactor, a point on the curve is mapped to the appropriate group known as cofactor clearing. Cofactors for $G_1$ and $G_2$ are as follows:

• $h_1=(\text{x}-1{)}^2/3$
• $h_2=$

References

• Ben Lynn’s notes
• Forney’s Finite Field introduction
• Ben Lynn’s Number theory notes

Footnotes

1. link contains beautiful answers about why these different varieties of a mathematical structure is needed. ↩