Criba racional

En matemáticas, la criba racional es un algoritmo general para la factorizar enteros en factores primos.

Es esencialmente un caso especial de la criba general del cuerpo de números, y mientras que es mucho menos eficiente que el algoritmo general, es conceptualmente más simple.

Suponga que intenta factorizar el número compuesto n. Se puede elegir una acotación B, e identificar el factor base (que se llamará P), al conjunto de todos los primos menores o iguales a B.

todos sus factores primos están en P. Por tanto, podemos escribir, para los exponentes adecuados

Seguidamente, buscamos los valores adecuados de z; los primeros son 2, 5, 9, y 56.

Los cuatro valores adecuados de z dan cuatro relaciones multiplicativas (mod 187): Ahora hay esencialmente varias maneras diferentes de combinar estos y acabar con exponentes pares.

Por ejemplo, Alternativamente, la ecuación (3) está en la forma adecuada ya: La criba racional, como la criba general del cuerpo de números, no puede factorizar números de la forma pm, donde p es un primo y m es un entero.

Esto no es un gran problema, dado que tales números son estadísticamente raros, y más aún, hay un proceso simple y rápido para verificar si un número dado es de esta forma.

Así que si n es grande (digamos, un centenar de dígitos), será difícil o imposible encontrar los suficientes z para que el algoritmo funcione.

La ventaja de la criba general del cuerpo de números es que se necesita únicamente buscar números lismo del orden de n1/d para algún entero positivo d (típicamente 3 o 5), a diferencia del orden n que es requerido aquí.