Math Basics

2026-11-18 · math number-theory abstract-algebra probability

notes / Cryptography

Number Theory

Integers

Modular Arithmetic

GCD

def gcd(a, b):
  if a < b:
    swap(a, b)
  while a > b:
    r = a % b
    if r == 0:
      break
    else:
      a = b
      b = r
  return b

a=q.m+rgcd(a,m)=gcd(a−q.m,m)=gcd(r,m)=gcd(m,r)

Abstract Algebra

Groups

group (G,) consists of set G and binary operation on G satisfying three axioms

  • (associative) a(bc)=(ab)c∀a,b,c,∈G
  • (identity) 1∈G such that a1=1a=a∀a∈G
  • (inverse) a−1∈G such that aa−1=a−1a=1∀a∈G

Let G be a group s.t. (ab)i=aibi for three consecutive integers i∈ℕ,∀a,b∈G. Show that G is Abelian

Sol: (ab)i=aibi(ab)i+1=ai+1bi+1⟹aibiab=ai+1bi+1multiplying with (ai+1)−1⟹biab=abi+1⟹bia=abisimilarly (ab)i+1=ai+1bi+1(ab)i+2=ai+2bi+2ai+1bi+1ab=ai+2bi+2bi+1ab=abi+2bi+1a=abi+1nowba=ab

Rings

ring (R,+,×)

  • (R,+) is an abelian group
  • (associative) operation × is associative
  • (identity) operation × has an identity
  • (distributive) × is distributive over +. a×(b+c)=(a×b)+(a×c)

Fields

Field (F,+,×)

  • (F,+) is a group
  • (F</mo>{0},×) is a group
  • distributivity holds

i.e rings with both additive group and multiplicative group

THEOREM

A field with order m only exists if m is a prime power i.e. m=pn for some positive integer n and prime integer p. p is called the characteristic of the finite field

Galois Fields

Prime Fields

These are fields of prime power

e.g. ℤm is the ring {ℤ,+(modm),×(modm)}. if m is prime then ℤm is a prime field.

e.g. GF(2) is the smallest finite field = {0,1}

  • Arithmetic is addition modulo 2 ≡ XOR
  • Multiplication modulo 2 is just logical AND

Extension Fields

In AES the finite field contains 256 elements =GF(28) (prime power)

Clearly this is not a prime field so we can't directly use XOR and AND.

  • We will call this an extension field and represent its elements as polynomials with defined polynomial arithmetic
  • coefficients of the polynomials belong to GF(2)
  • the maximum degree of GF(2m) is m−1 for m coefficients

Addition and Subtraction in GF(2m)

bitwise XOR

  • (x7+x6+x4+1)+(x4+x2+1)=(x7+x6+x2)

Note

subtraction of two polynomials gives the same result as addition

Multiplication in GF(2m)

  • standard polynomial multiplication
  • coefficients mod 2
  • reduce since degree probably increased
    • divide by irreducible polynomial (prime number equivalent of a polynomial)

C(x)≡A(x)⋅B(x)modP(x)

where P(x) is an irreducible polynomial

Note

for AES the irreducible polynomial P(x)=x8+x4+x3+x+1 is used

Inversion in GF(2m)

The main algorithm is the extended euclidean algorithm. AES uses LUTs

Information Theory

Surprise Function

s(x)=log2(1Pr[X==x])

  • s(x) is the information content of a single message
  • you want to be more surprised if a "rare" symbol is observed
  • logarithm because information should be additive

Shannon Entropy: average information content

H(x)=∑x∈XPr[X==x]⋅log21Pr[X==x]

  • 0≤H(x)≤log2n
  • sub-additivity: H(X,Y)≤H(X)+H(Y)
  • chain-rule: H(X,Y)=H(X|Y)+H(Y)=H(Y|X)+H(X)
    • conditioning can only decrease uncertainty

linked from