La división de prueba es la más laboriosa pero más fácil de entender de los algoritmos de factorización de enteros . La idea esencial detrás de las pruebas de división de prueba para ver si un número entero n , el número entero a factorizar, se puede dividir por cada número a su vez que sea menor que n . Por ejemplo, para el entero n = 12 , los únicos números que lo dividen son 1, 2, 3, 4, 6, 12. Al seleccionar solo las mayores potencias de los números primos en esta lista, se obtiene 12 = 3 × 4 = 3 × 2 2 .
La división de prueba fue descrita por primera vez por Fibonacci en su libro Liber Abaci (1202). [1]
Método
Dado un número entero n ( n se refiere al "número entero 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 los factores candidatos menores que n , y en orden de dos hacia arriba porque es más probable que una n arbitraria sea divisible por dos que por tres, y así sucesivamente. Con este orden, no tiene sentido probar la divisibilidad por cuatro si el número ya se ha determinado que 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 primo números como factores candidatos. Además, los factores de prueba no necesitan ir más allá deporque, 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 una cota definida de los factores primos. Suponga que P i es el i -ésimo primo, 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 un 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 siguiente primo es 49, y por debajo de n = 25 solo 2 y 3 son suficientes. Si la raíz cuadrada de n es integral, entonces es un factor yn 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 para un número natural." "" a = [] # Prepara una lista vacía. f = 2 # El primer factor posible. while n > 1 : # Mientras que n todavía tiene factores restantes ... if n % f == 0 : # El resto de n dividido por f podría ser cero. a . append ( f ) # Si es así, divide n. Agregue f a la lista. n / = f # Divida ese factor entre n. else : # Pero si f no es un factor de n, f + = 1 # Suma uno af y vuelve a intentarlo. devuelve a # Los factores primos pueden repetirse: 12 factores hasta 2,2,3.
O 2 veces más eficiente:
def trial_division ( n : int ) -> List [ int ]: a = [] mientras que n % 2 == 0 : a . añadir ( 2 ) n / = 2 f = 3 mientras f * f <= n : si n % f == 0 : a . añadir ( f ) n / = f si no : f + = 2 si n ! = 1 : a . append ( n ) # Solo es posible un número impar devuelve un
Se garantiza que estas versiones de la división de prueba encontrarán un factor de n si hay uno, ya que verifican todos los factores posibles de n , y si n es un número primo, esto significa factores de prueba hasta n . Por lo tanto, si el algoritmo encuentra un solo factor, n, es prueba de que n es primo . Si se encuentra más de un factor, entonces n es un número entero compuesto . Una forma más ventajosa desde el punto de vista computacional de decir esto es, si cualquier primo cuyo cuadrado no exceda de n lo divide sin un resto, entonces n no es primo.
A continuación se muestra la versión C ++ (sin cuadrar f)
plantilla < clase T , clase U > vector < T > TrialDivision ( U n ) { vector < T > v ; T f ; f = 2 ; mientras que ( n % 2 == 0 ) { v . retroceso ( f ); n / = 2 ; } f = 3 ; mientras que ( n % 3 == 0 ) { v . retroceso ( f ); n / = 3 ; } f = 5 ; T ac = 9 , temp = 16 ; hacer { ac + = temp ; // Suponga que la suma no causa desbordamiento con el tipo U if ( ac > n ) break ; si ( n % f == 0 ) { v . retroceso ( f ); n / = f ; ac - = temp ; } más { f + = 2 ; temp + = 8 ; } } mientras ( 1 ); si ( n ! = 1 ) v . push_back ( n ); return v ; }
Velocidad
En el peor de los casos , la división de pruebas es un algoritmo laborioso. Para un número de base 2 n dígitos a , si comienza desde dos y funciona solo 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 las pruebas 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 de dieciséis bits con signo y P (6542) = 65521 para enteros de dieciséis bits sin signo. Eso sería suficiente para probar la primordialidad para números hasta 65537 2 = 4,295,098,369. La preparación de una tabla de este tipo (generalmente a través del Tamiz 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, pero simplemente dividiendo por cada número impar menor que la raíz cuadrada el número de base 2 n dígitos a , primo o no, puede tomar 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 escogidos de manera uniforme al azar de números enteros de una longitud dada, hay una probabilidad del 50% que 2 es un factor de una y un 33% de probabilidad de que 3 es un factor de una , y así sucesivamente. Puede ser mostrado que el 88% de todos los números enteros positivos tienen un factor de menos de 100 y que el 92% tienen un factor bajo de 1000. Por lo tanto, cuando se enfrentan a una gran arbitraria una , vale la pena para comprobar la divisibilidad por los pequeños primos, ya que para, en base-2 .
Sin embargo, los números de muchos dígitos que no tienen factores en los números primos pequeños pueden requerir días o meses para factorizar con la división de prueba. En tales casos, se utilizan otros métodos como el tamiz cuadrático y el tamiz de campo numérico general (GNFS). Debido a que estos métodos también tienen un crecimiento en el tiempo superpolinomial, 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, de modo que no puedan ser factorizados por ningún método conocido públicamente en un período de tiempo útil en cualquier sistema o grupo de computadoras disponible como supercomputadoras y redes informáticas . El número de grado de criptografía más grande que se ha factorizado es RSA-250 , un número de 250 dígitos, que utiliza el GNFS y los recursos de varias supercomputadoras. El tiempo de ejecución fue de 2700 años centrales.
Referencias
- ^ Mollin, Richard A. (2002). "Una breve historia de las pruebas de factoring y primalidad BC (antes de las computadoras)". Revista de Matemáticas . 75 (1): 18-29. doi : 10.2307 / 3219180 . Señor 2107288 .
- Childs, Lindsay N. (2009). Una introducción concreta al álgebra superior . Textos de Licenciatura en Matemáticas (3ª ed.). Nueva York, NY: Springer-Verlag . ISBN 978-0-387-74527-5. Zbl 1165.00002 .
- Crandall, Richard ; Pomerance, Carl (2005). Números primos. Una perspectiva computacional (2ª ed.). Nueva York, NY: Springer-Verlag . ISBN 0-387-25282-7. Zbl 1088.11001 .
enlaces externos
- Calculadora rápida de factores primos de JavaScript mediante división de prueba . Puede manejar números hasta aproximadamente 2 53
- División de prueba en Java, C y JavaScript (en portugués)