Algebraic structures in math

2026-03-14

Covers the basics of algebraic structures of abstract mathematics, mostly meant as a beginner's guide to the notes on cryptography schemes.

Algebraic structures in math

Group

A set with a multiplication operation and an identity element, such that:

Multiplication is closed
Multiplication is commutative
Multiplication is associative
Identity element exists
Inverses are within the set

It could be addition also btw.

Ring

A set with two operations addition and multiplication where both of them satisfy the above properties, with the exception that the inverse of multiplication need not be in the same set.

Field

This is nothing but a set that has the operations addition and multiplication, under constraints that those operations have inverses and identities.

Both need to be associative
Both need to be commutative
It must have distinct identity elements for both
The additive/multiplicative inverses exist in the same set
It satisfies distributivity

Notably, integers are not a field, but a ring.

Finite fields

They are also known as Galois Fields.

Important

Finite fields only exist if they have $p^m$ elements, where $p$ is a prime and $m$ is a positive integer.

Fields where $m$ is 1, are also known as prime fields, while extension fields are those that have the exponent greater than that.

Prime field arithmetic

The elements of a prime fields are from the modulo set of $p$ .
Addition, subtraction, multiplication work in the congruence, the same way they work in the usual way.
Division works by multiplying with the modulo inverse of the number with which we're dividing.

Extension Field Arithmetic

We're specifically dealing with $GF(2^m)$

Element representation:

Polynomials of degree $m - 1$ .
The coefficients are elements of $GF(2)$ , basically 0 and 1.
Since all coefficients are effectively bits, the elements can be represented by $m$ bit integers.

Operations:

Addition and subtraction are like regular polynomials, you just take the mod of coefficients with 2, effectively making it an XOR.
Multiplication: just do regular polynomial multiplication and then divide by an irreducible polynomial.
Inverse is defined the same way, you find the polynomials that gives you 1 when multipliplied by the polynomial.

Note

Doesn't matter which irreducible polynomial it is, they are all reduced to the same isomorphic field.

Field

This is nothing but a set that has the operations addition and multiplication, under constraints that those operations have inverses and identities.

Both need to be associative

Both need to be commutative

It must have distinct identity elements for both

The additive/multiplicative inverses exist in the same set

It satisfies distributivity

Notably, integers are not a field, but a ring.

Extension Field Arithmetic

We're specifically dealing with

GF(2^m)

Element representation:

Polynomials of degree

m - 1

The coefficients are elements of

GF(2)

, basically 0 and 1.

Since all coefficients are effectively bits, the elements can be represented by

m

bit integers.

Operations:

Addition and subtraction are like regular polynomials, you just take the mod of coefficients with 2, effectively making it an XOR.

Multiplication: just do regular polynomial multiplication and then divide by an irreducible polynomial.

Inverse is defined the same way, you find the polynomials that gives you 1 when multipliplied by the polynomial.

Note

Doesn't matter which irreducible polynomial it is, they are all reduced to the same isomorphic field.