Base de factores

En la teoría de números computacionales , una base de factores es un conjunto pequeño de números primos que se utiliza comúnmente como herramienta matemática en algoritmos que implican una selección exhaustiva de factores potenciales de un entero dado.

Una base factorial es un conjunto relativamente pequeño de números primos distintos P , a veces junto con -1. ^[1] Digamos que queremos factorizar un entero n . Generamos, de alguna manera, una gran cantidad de pares de enteros ( x , y ) para los cuales , , y pueden factorizarse completamente sobre la base factorial elegida, es decir, todos sus factores primos están en P . ${\displaystyle x\neq \pm y}$${\displaystyle x^{2}\equiv y^{2}{\pmod {n}}}$${\displaystyle x^{2}{\pmod {n}}{\text{ y }}y^{2}{\pmod {n}}}$

En la práctica, se encuentran varios enteros x tales que tienen todos sus factores primos en la base de factores preseleccionada. Representamos cada expresión como un vector de una matriz con entradas enteras que son los exponentes de los factores en la base de factores. Las combinaciones lineales de las filas corresponden a la multiplicación de estas expresiones. Una relación de dependencia lineal módulo 2 entre las filas conduce a una congruencia deseada . ^[2] Esto esencialmente reformula el problema en un sistema de ecuaciones lineales , que se puede resolver utilizando numerosos métodos como la eliminación gaussiana ; en la práctica, se utilizan métodos avanzados como el algoritmo de bloques de Lanczos , que aprovechan ciertas propiedades del sistema. ${\displaystyle x^{2}{\pmod {n}}}$${\displaystyle x^{2}{\pmod {n}}}$${\displaystyle x^{2}\equiv y^{2}{\pmod {n}}}$

Esta congruencia puede generar el trivial ; en este caso, tratamos de encontrar otra congruencia adecuada. Si los intentos repetidos de factorizar fallan, podemos intentarlo nuevamente utilizando una base de factores diferente. ${\displaystyle \textstyle n=1\cdot n}$

Las bases factoriales se utilizan, por ejemplo, en la factorización de Dixon , la criba cuadrática y la criba de cuerpos numéricos . La diferencia entre estos algoritmos es esencialmente el método utilizado para generar candidatos ( x , y ). Las bases factoriales también se utilizan en el algoritmo de cálculo de índices para calcular logaritmos discretos. ^[3]