Skip to content

README.md

Latest commit

 

History

History
39 lines (31 loc) · 2.16 KB

README.md

File metadata and controls

39 lines (31 loc) · 2.16 KB

Álgebra Computacional: Librería de Cuerpos Finitos y Polinomios

Implementación desde cero de estructuras algebraicas avanzadas y algoritmos de factorización en Python. Este proyecto destaca por no depender de librerías externas, implementando incluso los algoritmos de optimización matricial y polinómica de forma nativa.

🚀 Características Principales

🏗️ Estructuras Implementadas

  • Cuerpos Finitos ($F_p$): Aritmética modular completa, inversos y potencias rápidas.
  • Anillos de Polinomios ($F_p[x]$): División con resto, GCD extendido y test de irreducibilidad de Rabin.
  • Cuerpos de Extensión ($F_q$): Implementación mediante cocientes de polinomios irreducibles.
  • Anillos de Polinomios sobre extensiones ($F_q[x]$): Soporte para aritmética y algoritmos avanzados sobre cuerpos de extensión.

🧬 Algoritmos de Factorización

Implementación del pipeline completo de Cantor-Zassenhaus:

  1. Square-free Factorization: Eliminación de factores con multiplicidad.
  2. Distinct-degree Factorization: Separación de factores por grados.
  3. Equal-degree Factorization: Algoritmo probabilístico para obtener factores irreducibles.

⚡ Algoritmos de Alto Rendimiento

  • Multiplicación de Karatsuba: Optimización del producto de polinomios con complejidad $O(n^{\log_2 3})$.
  • Transformada Rápida de Fourier (FFT): Algoritmo de Cooley-Tukey para multiplicación en tiempo casi lineal.
  • Matrices de Toeplitz: Operaciones de producto e inversión mediante División y Conquista recursiva.
  • División Rápida: Basada en la inversión de matrices de Toeplitz.

🛠️ Instalación y Uso

Al ser una librería "pure Python", no requiere dependencias externas.

import cuerpos_finitos as cf
fp = cf.cuerpo_fp(7)
fpx = cf.anillo_fp_x(fp, 'x')
f = (5, 1, 0, 2, 3) # 3x^4 + 2x^3 + x + 5
print(fpx.factorizar(f))

✒️ Autoría

Proyecto desarrollado para la asignatura de Álgebra Computacional (2025).

  • Desarrolladores: Alberto Peña Peñalver y Fabio Torres Martínez.
  • Contribución: Implementación de la arquitectura de clases y optimización de algoritmos de factorización y matrices.