La división por tanteo es el algoritmo de factorización de números enteros más laborioso pero más fácil de entender . La idea fundamental de la división por tanteo es comprobar si un número entero n , el número entero que se va a factorizar, se puede dividir por cada número que sea menor que la raíz cuadrada de n .
Por ejemplo, para hallar los factores primos de n = 70 , se puede intentar dividir 70 por primos sucesivos: primero, 70 / 2 = 35 ; luego, ni 2 ni 3 dividen exactamente a 35 ; finalmente, 35 / 5 = 7 , y 7 es primo en sí mismo. Por lo tanto , 70 = 2 × 5 × 7 .
La división por prueba fue descrita por primera vez por Fibonacci en su libro Liber Abaci (1202). [1]
Dado un entero n ( n se refiere al "entero que se va a factorizar"), la división de prueba consiste en probar sistemáticamente si n es divisible por cualquier número menor. Claramente, solo vale la pena probar factores candidatos menores que n , y en orden de dos en adelante porque es más probable que un n arbitrario sea divisible por dos que por tres, y así sucesivamente. Con este orden, no tiene sentido probar la divisibilidad por cuatro si ya se ha determinado que el número no es divisible por dos, y así sucesivamente para tres y cualquier múltiplo de tres, etc. Por lo tanto, el esfuerzo se puede reducir seleccionando solo números primos como factores candidatos. Además, los factores de prueba no necesitan ir más allá porque, si n es divisible por algún número p , entonces n = p × q y si q fuera menor que p , n se habría detectado antes como divisible por q o por un factor primo de q .
Es posible establecer un límite definido para los factores primos. Supongamos que P i es el primo i , de modo que P 1 = 2, P 2 = 3, P 3 = 5, etc. Entonces, el último número primo que vale la pena probar como posible factor de n es P i , donde P 2 i + 1 > n ; la igualdad aquí significaría que P i + 1 es un factor. Por lo tanto, probar con 2, 3 y 5 es suficiente hasta n = 48, no solo 25, porque el cuadrado del próximo primo es 49 y, por debajo de n = 25, solo 2 y 3 son suficientes. Si la raíz cuadrada de n es un entero, entonces es un factor y n es un cuadrado perfecto .
Un ejemplo del algoritmo de división de prueba, que utiliza números enteros sucesivos como factores de prueba, es el siguiente (en Python ):
def trial_division ( n : int ) -> list [ int ]: """Devuelve una lista de los factores primos de un número natural.""" a = [] # Prepara una lista vacía. f = 2 # El primer factor posible. while f * f <= n : # Mientras f no sea mayor que la raíz cuadrada de n ... if n % f == 0 : # El resto de n dividido por f puede ser cero. a.append ( f ) # Si es así, divide n. Agrega f a la lista. n // = f # Divide ese factor de n. else : # Pero si f no es un factor de n, f += 1 # Agrega uno a f e intenta nuevamente. if n ! = 1 : a.append ( n ) # Agrega el primo n restante a la lista return a # Los factores primos pueden repetirse: 12 factores de 2,2,3. Esta versión prueba todos los números enteros hasta la raíz cuadrada de n , no solo los primos. Una implementación más complicada que solo probara los primos sería significativamente más rápida en el peor de los casos.
En el peor de los casos , la división por tanteo es un algoritmo laborioso. Para un número a de base 2 de n dígitos , si comienza desde dos y llega hasta la raíz cuadrada de a , el algoritmo requiere
divisiones de prueba, donde denota la función de conteo de primos , el número de primos menores que x . Esto no tiene en cuenta la sobrecarga de la prueba de primalidad para obtener los números primos como factores candidatos. Una tabla útil no necesita ser grande: P(3512) = 32749, el último primo que cabe en un entero con signo de dieciséis bits y P(6542) = 65521 para enteros de dieciséis bits sin signo. Eso sería suficiente para probar la primalidad para números hasta 65537 2 = 4.295.098.369. Preparar una tabla de este tipo (generalmente mediante la criba de Eratóstenes ) solo valdría la pena si se probaran muchos números. Si en cambio se usa una variante sin prueba de primalidad, sino simplemente dividiendo por cada número impar menor que la raíz cuadrada del número de base 2 n dígito a , primo o no, puede tomar hasta aproximadamente:
En ambos casos, el tiempo requerido crece exponencialmente con los dígitos del número.
Aun así, este es un método bastante satisfactorio, considerando que incluso los algoritmos más conocidos tienen un crecimiento temporal exponencial. Para un número entero elegido uniformemente al azar de una longitud dada, hay una probabilidad del 50% de que 2 sea un factor de a y una probabilidad del 33% de que 3 sea un factor de a , y así sucesivamente. Se puede demostrar que el 88% de todos los números enteros positivos tienen un factor menor de 100 y que el 92% tienen un factor menor de 1000. Por lo tanto, cuando nos enfrentamos a un a arbitrariamente grande , vale la pena verificar la divisibilidad por los primos pequeños, ya que para , en base 2 .
Sin embargo, los números de muchos dígitos que no tienen factores en los primos pequeños pueden requerir días o meses para factorizarse con la división de prueba. En tales casos se utilizan otros métodos como la criba cuadrática y la criba de campo numérico general (GNFS). Debido a que estos métodos también tienen un crecimiento temporal superpolinómico, se alcanza muy rápidamente un límite práctico de n dígitos. Por esta razón, en la criptografía de clave pública , los valores para a se eligen para que tengan factores primos grandes de tamaño similar para que no puedan factorizarse por ningún método conocido públicamente en un período de tiempo útil en cualquier sistema informático disponible o clúster de computadoras como supercomputadoras y redes de computadoras . El número de grado criptográfico más grande que se ha factorizado es RSA-250 , un número de 250 dígitos, utilizando el GNFS y los recursos de varias supercomputadoras. El tiempo de ejecución fue de 2700 años de núcleo.
