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í.