Computational Algebra Labs (Python)

Coursework repository for Computational Algebra (UCM, 2025–2026).

This project implements finite-field arithmetic and polynomial algorithms in pure Python, including fast polynomial operations and probabilistic factorization over finite fields.

Author

• Alejandro Parreño Minaya — GitHub: aparreno14

Contents

• cuerpos_finitos.py Finite fields and polynomial rings:

  • Field Fp (mod prime p)
  • Extension field Fq (constructed from an irreducible polynomial over Fp)
  • Polynomial rings over Fp and Fq with arithmetic, division, gcd and extended gcd

• cuerpos_finitos_robusto.py A more “robust” variant that introduces explicit element wrappers (e.g., field elements and polynomials) and keeps the same high-level API (useful for safer operations and debugging).

• algoritmos_rapidos.py Fast polynomial algorithms over Fp and Fq:

  • Karatsuba multiplication
  • Toeplitz-based helpers and fast division (divmod)
  • FFT / IFFT routines This module attaches convenience methods to the polynomial ring classes:
  • anillo_fp_x.mult_fast, anillo_fp_x.divmod_fast
  • anillo_fq_x.mult_fast, anillo_fq_x.divmod_fast

• factorizacion.py Polynomial factorization over finite fields using the Cantor–Zassenhaus framework:

  • square-free factorization
  • distinct-degree factorization
  • equal-degree factorization (randomized splitting) This module attaches:
  • anillo_fp_x.factorizar
  • anillo_fq_x.factorizar

Requirements

• Python 3.x
• No external dependencies (standard library only)

Implementation note

This repository includes two finite-field backends:

• cuerpos_finitos.py is the base/reference implementation. All higher-level modules in this repo (fast polynomial algorithms and factorization) are designed to work with this backend.
• cuerpos_finitos_robusto.py is an alternative, more defensive rewrite kept for experimentation and debugging. It is not used as the default dependency by the rest of the project.

Quick start (interactive)

Create a prime field and its polynomial ring:

import cuerpos_finitos as cf
fp  = cf.cuerpo_fp(101)
fpx = cf.anillo_fp_x(fp)

Enable fast polynomial operations and factorization (adds methods to the ring classes):

import algoritmos_rapidos
import factorizacion

From here you can use:

• fpx.mult_fast(f, g) / fpx.divmod_fast(f, g) (after importing algoritmos_rapidos)
• fpx.factorizar(f) (after importing factorizacion)

For extension fields:

fq  = cf.cuerpo_fq(fp, g)     # g is an irreducible polynomial over Fp
fqx = cf.anillo_fq_x(fq)

Notes

• Some factorization steps are randomized (as in standard Cantor–Zassenhaus-style workflows). For reproducibility, set a random seed before running experiments.
• This code is intended for educational purposes and focuses on algorithmic clarity and correctness within the course scope.

License

MIT — see LICENSE.