³⁸ views
ubuntu2404

Kernel: SageMath 10.7

Finite Rings and Fields in SageMath

Introduction

Finite rings and fields are algebraic structures with a finite number of elements. They play a crucial role in many areas of mathematics and computer science, including:

Coding theory and error correction
Cryptography and secure communications
Combinatorics and design theory
Computer algebra and symbolic computation

A finite field (also called a Galois field) is a field with finitely many elements. Remarkably, for each prime power $q = p^n$ , there exists exactly one finite field with $q$ elements (up to isomorphism), denoted $\mathbb{F}_q$ or $\mathrm{GF}(q)$ .

A finite ring is a ring with finitely many elements. The most common example is $\mathbb{Z}/n\mathbb{Z}$ , the integers modulo $n$ .

Historical Context

Finite fields were first studied systematically by Évariste Galois in 1830, shortly before his tragic death at age 20 in a duel. His work remained unpublished for 14 years. The classification theorem stating that finite fields exist only for prime power orders, and that they are unique up to isomorphism, is one of the fundamental results in algebra. Carl Friedrich Gauss had earlier studied modular arithmetic, laying the groundwork for finite field theory.

Integers Modulo n: $\mathbb{Z}/n\mathbb{Z}$

The most basic finite ring is $\mathbb{Z}/n\mathbb{Z}$ , the integers modulo $n$ . This ring consists of equivalence classes $\{0, 1, 2, \ldots, n-1\}$ with addition and multiplication performed modulo $n$ .

When $n$ is prime, $\mathbb{Z}/n\mathbb{Z}$ is actually a field.

In [1]:

# Create the ring Z/12Z
R = Integers(12)
print("Ring:", R)
print("Order (number of elements):", R.order())
print("Is it a field?", R.is_field())
print("Characteristic:", R.characteristic())

Out[1]:

Ring: Ring of integers modulo 12
Order (number of elements): 12
Is it a field? False
Characteristic: 12

In [2]:

# Arithmetic in Z/12Z
R = Integers(12)
a = R(7)
b = R(10)

print(f"a = {a}")
print(f"b = {b}")
print(f"a + b = {a + b}")
print(f"a * b = {a * b}")
print(f"a^2 = {a^2}")

Out[2]:

a = 7
b = 10
a + b = 5
a * b = 10
a^2 = 1

In [3]:

# Units in Z/12Z (elements with multiplicative inverses)
R = Integers(12)
print("Units in Z/12Z:")
units = R.unit_group()
print("Unit group:", units)
print("Order of unit group:", units.order())
print("\nList of units:")
for u in R.list_of_elements_of_multiplicative_group():
    print(f"{u} is a unit")

Out[3]:

Units in Z/12Z:
Unit group: Multiplicative Abelian group isomorphic to C2 x C2
Order of unit group: 4

List of units:
1 is a unit
5 is a unit
7 is a unit
11 is a unit

Prime Fields: $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$

When $n = p$ is prime, $\mathbb{Z}/p\mathbb{Z}$ is a field. This is the simplest type of finite field, containing exactly $p$ elements.

Fermat's Little Theorem: For any $a \in \mathbb{F}_p$ with $a \neq 0$ , we have $a^{p-1} = 1$ .

In [4]:

# Create the field F_7
F = GF(7)  # GF stands for Galois Field
print("Field:", F)
print("Order:", F.order())
print("Is it a field?", F.is_field())
print("Characteristic:", F.characteristic())
print("\nAll elements:", list(F))

Out[4]:

Field: Finite Field of size 7
Order: 7
Is it a field? True
Characteristic: 7

All elements: [0, 1, 2, 3, 4, 5, 6]

In [5]:

# Verify Fermat's Little Theorem in F_7
F = GF(7)
print("Verifying Fermat's Little Theorem: a^6 = 1 for all a ≠ 0 in F_7")
print()
for a in F:
    if a != 0:
        result = a^6
        print(f"{a}^6 = {result}")

Out[5]:

Verifying Fermat's Little Theorem: a^6 = 1 for all a ≠ 0 in F_7

1^6 = 1
2^6 = 1
3^6 = 1
4^6 = 1
5^6 = 1
6^6 = 1

In [6]:

# Division in a finite field
F = GF(11)
a = F(7)
b = F(3)

print(f"a = {a}")
print(f"b = {b}")
print(f"a + b = {a + b}")
print(f"a - b = {a - b}")
print(f"a * b = {a * b}")
print(f"a / b = {a / b}")
print(f"\nVerification: (a/b) * b = {(a/b) * b}")

Out[6]:

a = 7
b = 3
a + b = 10
a - b = 4
a * b = 10
a / b = 6

Verification: (a/b) * b = 7

Extension Fields: $\mathbb{F}_{p^n}$

For a prime $p$ and positive integer $n > 1$ , we can construct finite fields of order $p^n$ . These are called extension fields of $\mathbb{F}_p$ .

The field $\mathbb{F}_{p^n}$ can be constructed as: $\mathbb{F}_{p^n} \cong \mathbb{F}_p[x] / \langle f(x) \rangle$

where $f(x)$ is an irreducible polynomial of degree $n$ over $\mathbb{F}_p$ .

In [7]:

# Create the field F_9 = F_{3^2}
F = GF(9, 'a')  # The 'a' is the name of the generator
print("Field:", F)
print("Order:", F.order())
print("Characteristic:", F.characteristic())
print("Degree over prime field:", F.degree())

a = F.gen()  # Get the generator
print(f"\nGenerator: a = {a}")
print(f"Minimal polynomial of a: {a.minimal_polynomial()}")

Out[7]:

Field: Finite Field in a of size 3^2
Order: 9
Characteristic: 3
Degree over prime field: 2

Generator: a = a
Minimal polynomial of a: x^2 + 2*x + 2

In [8]:

# List all elements of F_9
F = GF(9, 'a')
a = F.gen()

print("All elements of F_9:")
for element in F:
    print(element)

Out[8]:

All elements of F_9:
0
a
a + 1
2*a + 1
2
2*a
2*a + 2
a + 2
1

In [9]:

# Arithmetic in F_9
F = GF(9, 'a')
a = F.gen()

# Elements can be expressed as polynomials in a
x = 2 + a
y = 1 + 2*a

print(f"x = {x}")
print(f"y = {y}")
print(f"x + y = {x + y}")
print(f"x * y = {x * y}")
print(f"x / y = {x / y}")
print(f"x^2 = {x^2}")

Out[9]:

x = a + 2
y = 2*a + 1
x + y = 0
x * y = a + 1
x / y = 2
x^2 = 2*a + 2

Multiplicative Structure and Primitive Elements

The multiplicative group $\mathbb{F}_q^*$ of a finite field is cyclic. A generator of this group is called a primitive element or primitive root.

For $\mathbb{F}_q$ , the multiplicative group has order $q-1$ , so every non-zero element $a$ satisfies $a^{q-1} = 1$ .

In [10]:

# Find a primitive element in F_7
F = GF(7)
print("Multiplicative group of F_7 has order:", F.order() - 1)

# Find a primitive element (generator)
g = F.multiplicative_generator()
print(f"\nPrimitive element: g = {g}")

print(f"\nPowers of g = {g}:")
for i in range(1, 7):
    print(f"g^{i} = {g^i}")

Out[10]:

Multiplicative group of F_7 has order: 6

Primitive element: g = 3

Powers of g = 3:
g^1 = 3
g^2 = 2
g^3 = 6
g^4 = 4
g^5 = 5
g^6 = 1

In [11]:

# Primitive element in an extension field F_16
F = GF(16, 'a')
a = F.gen()

print("Field:", F)
print("Multiplicative group order:", F.order() - 1)

g = F.multiplicative_generator()
print(f"\nPrimitive element: g = {g}")

print("\nFirst 15 powers of g (should give all non-zero elements):")
for i in range(1, 16):
    print(f"g^{i} = {g^i}")

Out[11]:

Field: Finite Field in a of size 2^4
Multiplicative group order: 15

Primitive element: g = a

First 15 powers of g (should give all non-zero elements):
g^1 = a
g^2 = a^2
g^3 = a^3
g^4 = a + 1
g^5 = a^2 + a
g^6 = a^3 + a^2
g^7 = a^3 + a + 1
g^8 = a^2 + 1
g^9 = a^3 + a
g^10 = a^2 + a + 1
g^11 = a^3 + a^2 + a
g^12 = a^3 + a^2 + a + 1
g^13 = a^3 + a^2 + 1
g^14 = a^3 + 1
g^15 = 1

Frobenius Endomorphism

In a finite field $\mathbb{F}_{p^n}$ , the Frobenius endomorphism is the map $\phi: x \mapsto x^p$ .

This map has remarkable properties:

It is a field homomorphism: $\phi(x + y) = \phi(x) + \phi(y)$ and $\phi(xy) = \phi(x)\phi(y)$
It has order $n$ : applying it $n$ times gives the identity
The fixed points are exactly $\mathbb{F}_p$

The Frobenius map is named after Ferdinand Georg Frobenius, though it was studied earlier by others in the context of finite fields.

In [12]:

# Demonstrate the Frobenius endomorphism in F_9
F = GF(9, 'a')
a = F.gen()
p = F.characteristic()

print(f"Field: {F}")
print(f"Characteristic p = {p}")
print(f"\nFrobenius map: x → x^{p}")
print()

# Test on a few elements
elements = [F(0), F(1), F(2), a, 1+a, 2+a]
for x in elements:
    frobenius = x^p
    print(f"φ({x}) = {frobenius}")

Out[12]:

Field: Finite Field in a of size 3^2
Characteristic p = 3

Frobenius map: x → x^3

φ(0) = 0
φ(1) = 1
φ(2) = 2
φ(a) = 2*a + 1
φ(a + 1) = 2*a + 2
φ(a + 2) = 2*a

In [13]:

# Verify Frobenius is a homomorphism
F = GF(9, 'a')
a = F.gen()
p = F.characteristic()

x = 1 + a
y = 2 + 2*a

print("Verifying φ(x + y) = φ(x) + φ(y):")
print(f"φ({x} + {y}) = {(x+y)^p}")
print(f"φ({x}) + φ({y}) = {x^p} + {y^p} = {x^p + y^p}")
print(f"Equal? {(x+y)^p == x^p + y^p}")

print("\nVerifying φ(xy) = φ(x)φ(y):")
print(f"φ({x} * {y}) = {(x*y)^p}")
print(f"φ({x}) * φ({y}) = {x^p} * {y^p} = {x^p * y^p}")
print(f"Equal? {(x*y)^p == x^p * y^p}")

Out[13]:

Verifying φ(x + y) = φ(x) + φ(y):
φ(a + 1 + 2*a + 2) = 0
φ(a + 1) + φ(2*a + 2) = 2*a + 2 + a + 1 = 0
Equal? True

Verifying φ(xy) = φ(x)φ(y):
φ(a + 1 * 2*a + 2) = 1
φ(a + 1) * φ(2*a + 2) = 2*a + 2 * a + 1 = 1
Equal? True

Polynomials over Finite Fields

We can work with polynomials having coefficients in finite fields. This is crucial for constructing extension fields and for applications in coding theory.

In [14]:

# Create a polynomial ring over F_5
F = GF(5)
R.<x> = PolynomialRing(F)

print("Polynomial ring:", R)

# Create some polynomials
f = x^2 + 2*x + 3
g = x + 4

print(f"\nf(x) = {f}")
print(f"g(x) = {g}")
print(f"f(x) + g(x) = {f + g}")
print(f"f(x) * g(x) = {f * g}")

Out[14]:

Polynomial ring: Univariate Polynomial Ring in x over Finite Field of size 5

f(x) = x^2 + 2*x + 3
g(x) = x + 4
f(x) + g(x) = x^2 + 3*x + 2
f(x) * g(x) = x^3 + x^2 + x + 2

In [15]:

# Find irreducible polynomials over F_3
F = GF(3)
R.<x> = PolynomialRing(F)

print("Irreducible polynomials of degree 2 over F_3:")
count = 0
for c0 in F:
    for c1 in F:
        f = x^2 + c1*x + c0
        if f.is_irreducible():
            print(f"  {f}")
            count += 1
            
print(f"\nTotal: {count} irreducible quadratics over F_3")

Out[15]:

Irreducible polynomials of degree 2 over F_3:
  x^2 + 1
  x^2 + x + 2
  x^2 + 2*x + 2

Total: 3 irreducible quadratics over F_3

In [16]:

# Factorization over finite fields
F = GF(7)
R.<x> = PolynomialRing(F)

f = x^4 - 1
print(f"f(x) = {f}")
print(f"Factorization: {f.factor()}")

g = x^3 + x + 1
print(f"\ng(x) = {g}")
print(f"Is irreducible? {g.is_irreducible()}")

Out[16]:

f(x) = x^4 + 6
Factorization: (x + 1) * (x + 6) * (x^2 + 1)

g(x) = x^3 + x + 1
Is irreducible? True

Constructing Extension Fields via Quotient Rings

We can explicitly construct extension fields as quotient rings $\mathbb{F}_p[x] / \langle f(x) \rangle$ where $f(x)$ is irreducible.

In [17]:

# Construct F_8 = F_2[x]/(x^3 + x + 1)
F2 = GF(2)
R.<x> = PolynomialRing(F2)
f = x^3 + x + 1

print(f"Base field: {F2}")
print(f"Irreducible polynomial: {f}")
print(f"Is irreducible? {f.is_irreducible()}")

# Create the quotient ring
F8 = R.quotient(f, 'a')
print(f"\nQuotient field: {F8}")
print(f"Order: {F8.order()}")

Out[17]:

Base field: Finite Field of size 2
Irreducible polynomial: x^3 + x + 1
Is irreducible? True

Quotient field: Univariate Quotient Polynomial Ring in a over Finite Field of size 2 with modulus x^3 + x + 1
Order: 8

In [18]:

# Work with elements in the quotient field
F2 = GF(2)
R.<x> = PolynomialRing(F2)
F8 = R.quotient(x^3 + x + 1, 'a')
a = F8.gen()

print(f"Generator: a = {a}")
print(f"a^3 = {a^3}")
print(f"Since x^3 + x + 1 = 0, we have a^3 = a + 1 = {a + 1}")

# List all elements
print("\nAll elements of F_8:")
for element in F8:
    print(element)

Out[18]:

Generator: a = a
a^3 = a + 1
Since x^3 + x + 1 = 0, we have a^3 = a + 1 = a + 1

All elements of F_8:
0
1
a
a + 1
a^2
a^2 + 1
a^2 + a
a^2 + a + 1

Discrete Logarithm Problem

Given a primitive element $g$ in a finite field $\mathbb{F}_q$ and an element $h \in \mathbb{F}_q^*$ , the discrete logarithm problem is to find the integer $k$ such that $g^k = h$ .

This problem is believed to be computationally hard for large fields, making it the foundation for many cryptographic systems. However, for small fields, SageMath can compute discrete logarithms efficiently.

In [19]:

# Discrete logarithm in F_11
F = GF(11)
g = F.multiplicative_generator()

print(f"Field: {F}")
print(f"Primitive element g = {g}")

h = F(5)
k = h.log(g)
print(f"\nFind k such that g^k = {h}")
print(f"Discrete log: k = {k}")
print(f"Verification: {g}^{k} = {g^k}")

Out[19]:

Field: Finite Field of size 11
Primitive element g = 2

Find k such that g^k = 5
Discrete log: k = 4
Verification: 2^4 = 5

In [20]:

# Discrete logarithm table for F_7
F = GF(7)
g = F.multiplicative_generator()

print(f"Primitive element: g = {g}")
print("\nDiscrete logarithm table:")
print("h | log_g(h)")
print("--|----------")
for h in F:
    if h != 0:
        k = h.log(g)
        print(f"{h} | {k}")

Out[20]:

Primitive element: g = 3

Discrete logarithm table:
h | log_g(h)
--|----------
1 | 0
2 | 2
3 | 1
4 | 4
5 | 5
6 | 3

Conway Polynomials

Conway polynomials are a standard choice of irreducible polynomials for constructing finite field extensions. They are designed to be compatible across different extension degrees, ensuring consistent embeddings.

Conway polynomials were defined by Richard Parker and named after John Horton Conway. They provide a canonical way to represent finite fields.

In [21]:

# Get Conway polynomials for various fields
from sage.rings.finite_rings.conway_polynomials import conway_polynomial

print("Conway polynomials for F_{p^n}:")
print()

# F_4 = F_{2^2}
print(f"F_4 = F_2[x]/(f), where f = {conway_polynomial(2, 2)}")

# F_8 = F_{2^3}
print(f"F_8 = F_2[x]/(f), where f = {conway_polynomial(2, 3)}")

# F_9 = F_{3^2}
print(f"F_9 = F_3[x]/(f), where f = {conway_polynomial(3, 2)}")

# F_25 = F_{5^2}
print(f"F_25 = F_5[x]/(f), where f = {conway_polynomial(5, 2)}")

Out[21]:

Conway polynomials for F_{p^n}:

F_4 = F_2[x]/(f), where f = x^2 + x + 1
F_8 = F_2[x]/(f), where f = x^3 + x + 1
F_9 = F_3[x]/(f), where f = x^2 + 2*x + 2
F_25 = F_5[x]/(f), where f = x^2 + 4*x + 2

Application: Linear Algebra over Finite Fields

Finite fields are extensively used in linear algebra computations, particularly in applications like coding theory and cryptography.

In [22]:

# Create a matrix over F_5
F = GF(5)
A = matrix(F, [[1, 2, 3], [4, 0, 1], [2, 3, 4]])

print("Matrix over F_5:")
print(A)
print(f"\nDeterminant: {A.determinant()}")
print(f"Is invertible? {A.is_invertible()}")

if A.is_invertible():
    print("\nInverse matrix:")
    print(A.inverse())

Out[22]:

Matrix over F_5:
[1 2 3]
[4 0 1]
[2 3 4]

Determinant: 0
Is invertible? False

In [23]:

# Solve a linear system over F_7
F = GF(7)
A = matrix(F, [[1, 2], [3, 4]])
b = vector(F, [5, 6])

print("Solve Ax = b over F_7:")
print(f"A = ")
print(A)
print(f"\nb = {b}")

x = A.solve_right(b)
print(f"\nSolution: x = {x}")
print(f"Verification: Ax = {A * x}")

Out[23]:

Solve Ax = b over F_7:
A = 
[1 2]
[3 4]

b = (5, 6)

Solution: x = (3, 1)
Verification: Ax = (5, 6)

In [24]:

# Eigenvalues over finite fields
F = GF(11)
A = matrix(F, [[3, 1], [2, 4]])

print("Matrix:")
print(A)
print(f"\nCharacteristic polynomial: {A.characteristic_polynomial()}")

# Find eigenvalues
char_poly = A.characteristic_polynomial()
print(f"\nFactorization: {char_poly.factor()}")

# The roots are the eigenvalues
eigenvalues = char_poly.roots(multiplicities=False)
print(f"Eigenvalues: {eigenvalues}")

Out[24]:

Matrix:
[3 1]
[2 4]

Characteristic polynomial: x^2 + 4*x + 10

Factorization: (x + 6) * (x + 9)
Eigenvalues: [5, 2]

Summary

In this notebook, we've explored:

Finite Rings: The ring $\mathbb{Z}/n\mathbb{Z}$ and its properties
Prime Fields: Fields $\mathbb{F}_p$ where $p$ is prime
Extension Fields: Fields $\mathbb{F}_{p^n}$ constructed as quotient rings
Multiplicative Structure: Primitive elements and cyclic multiplicative groups
Frobenius Endomorphism: The fundamental automorphism $x \mapsto x^p$
Polynomials: Working with polynomials over finite fields
Discrete Logarithms: Computing logarithms in finite fields
Conway Polynomials: Standard irreducible polynomials for field extensions
Applications: Linear algebra computations over finite fields

Key Theoretical Results

Existence and Uniqueness: For each prime power $q = p^n$ , there exists exactly one finite field (up to isomorphism) with $q$ elements
Multiplicative Group: The non-zero elements of $\mathbb{F}_q$ form a cyclic group of order $q-1$
Fermat's Little Theorem: For $a \in \mathbb{F}_p^*$ , we have $a^{p-1} = 1$
Frobenius Automorphism: The map $x \mapsto x^p$ is a field automorphism with order equal to the extension degree

Finite Rings and Fields in SageMath

Introduction

Historical Context

Integers Modulo n: $\mathbb{Z}/n\mathbb{Z}$

Prime Fields: $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$

Extension Fields: $\mathbb{F}_{p^n}$

Multiplicative Structure and Primitive Elements

Frobenius Endomorphism

Polynomials over Finite Fields

Constructing Extension Fields via Quotient Rings

Discrete Logarithm Problem

Conway Polynomials

Application: Linear Algebra over Finite Fields

Summary

Key Theoretical Results

Further Reading

Product

Resources

Company

Finite Rings and Fields in SageMath

Introduction

Historical Context

Integers Modulo n: Z/nZ\mathbb{Z}/n\mathbb{Z}Z/nZ

Prime Fields: Fp=Z/pZ\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}Fp​=Z/pZ

Extension Fields: Fpn\mathbb{F}_{p^n}Fpn​

Multiplicative Structure and Primitive Elements

Frobenius Endomorphism

Polynomials over Finite Fields

Constructing Extension Fields via Quotient Rings

Discrete Logarithm Problem

Conway Polynomials

Application: Linear Algebra over Finite Fields

Summary

Key Theoretical Results

Further Reading

Integers Modulo n: $\mathbb{Z}/n\mathbb{Z}$

Prime Fields: $\mathbb{F}_p = \mathbb{Z}/p\mathbb{Z}$

Extension Fields: $\mathbb{F}_{p^n}$