Como principiante en el mundo de la factorización de enteros, mi idea de factorizar un entero es generar una gran lista de números primos por debajo de este número y tratar repetidamente de dividir el entero por estos primos. Sin embargo, para números enteros muy grandes este método es inútil.
Se sabe que la Criba General de Campos Numéricos es el "algoritmo clásico más eficiente que se conoce para la factorización de enteros de más de 100 dígitos", sin embargo, ningún artículo que haya encontrado lo explicaba con la suficiente sencillez como para entenderlo.
¿Pueden ayudarme a entender el GNFS en términos y métodos sencillos, y cómo implementarlo en un número entero grande? $2^{64}$ ?
4 votos
No hay números enteros grandes por debajo de $2^{64}$ --- no usarías GNFS para algo tan pequeño. Además, hay un límite a lo simple que puede ser una explicación y seguir siendo una explicación. Para entender la GNFS hay que entender los campos numéricos algebraicos; para entenderlos, hay que entender la teoría de Galois, el álgebra conmutativa y la teoría elemental de los números; para entenderlos, hay que entender la teoría de grupos y el álgebra lineal. Entonces, ¿cuál es su punto de partida?
0 votos
@GerryMyerson He implementado el tamiz del campo cuadrático pero no conozco ninguno de los campos que has mencionado. En una explicación sencilla, espero ver un ejemplo de elección de dos polinomios pequeños, $f(x)$ y $f(g)$ con pequeños grados $d$ y $e$ que tienen una raíz común $m$ y mostrar cómo encontrar pares b-suaves con ellos. Sería bueno si también puede mostrar cómo el cribado de celosía entran en juego y la referencia de otras optimizaciones que uno debe considerar. Básicamente, todo lo que espero ver es un ejemplo.
1 votos
@Ilya, ¿has comprobado el enlace en la respuesta dada por el usuario58512?
0 votos
@GerryMyerson sí, por supuesto, lo he leído varias veces. Pero soy un desarrollador y necesito ver el método en acción para poder implementarlo (ese es mi objetivo actual). He estado leyendo mucho la wiki y también he visto algunos vídeos. Pero estoy en un punto en el que hay muchas cosas que no entiendo y no sé qué necesito aprender más a fondo para poder entenderlo. Por eso quiero ver algún ejemplo muy sencillo y claro de cómo se cogen los polinomios y se convierten en relaciones b-smooth.
0 votos
@Ilya, ¿qué tal si citeseerx.ist.psu.edu/viewdoc/ (Michael Case, A beginner's guide to the general number field sieve).
0 votos
@GerryMyerson De hecho, he visto este. Sólo leí una parte ya que el resto era demasiado complicado para mí. Intentaré terminarlo y os lo haré saber. Por favor, dame unos días