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:

- Closure: $a⊕b=c∈G$
- Associative: $(a⊕b)⊕c=a⊕(b⊕c)$
- Existence of Identity element: $a⊕0=0⊕a=a$
- Existence of
**unique**inverse element for every element of the set: $a⊕b=0$

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

Prove uniqueness of inverse.

Take two elements $b=c∈G$ such that $a⋅b=1$ and $a⋅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 $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.

^{1}

Now, set underlying the group can have finite elements, namely Finite Groups. For example: $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→H$, and written as $G≃H$.

- $f$ is bijection
- group operation commutes: $f(g_{1}⊕_{G}g_{2})=f(g_{1})⊕_{H}f(g_{2})$

Direct product in groups: Given two group $G(⊕_{G}),H(⊕_{H})$, direct group is written as $G×H:(g,h)$ where $g∈G,h∈H$, containing $∣G∣⋅∣H∣$ elements, and group operation is applied component wise: $(g,h)⊕(g_{′},h_{′})=(g⊕_{G}g_{′}),(h⊕_{H}h_{′})$.

Using this, crt is proven.

## Subgroup

Subset $H$ of $G$ satisfying group axioms. Expressed as $H≤G$.

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

Theorem:

- Non empty subset $H⊂G$ is a subgroup iff H’s operation is multiplication.
- For subgroup $H≤G$ and $h∈G$, $hH=H=Hh$. Can be generalised to any set $S⊂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}∈G,r_{1}∈/H$, then $∣r_{1}H∣=∣H∣$. Since $r_{1}H,H$ are disjoint, then $∣r_{1}H∪H∣=2∣H∣$. Take $n$ such subgroups of $G$, such that $∣r_{1}H∪r_{2}H∪⋯∪r_{n}H∣=n∣H∣=G$.

Corollary: let $G$ be a group, and $g∈G$, then order of $g$ divides $∣G∣$.

Theorem: If $H_{1},H_{2},…$ are subgroups, then $H_{1}∩H_{2}∩…$ is subgroup of each of $H_{1},H_{2},…$.

- Independent elements: $g_{i}∈/⟨g_{1},…,g_{i−1},g_{i+1},…,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.

## Cyclic Groups

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

Fundamental theorem of finite cyclic groups: if $G$ is a finite cyclic group such that $∣G∣=n$, and $k:k∣n$, then, $G[k]$ refers to unique finite cyclic subgroup of $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×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}=(x−1)_{2}/3$
- $h_{2}=$