Escriba un programa para factorizar un número semi-primo en el menor tiempo posible.
Para fines de prueba, use esto: 38! +1 (523022617466601111760007224100074291200000001)
Es igual a: 14029308060317546154181 × 37280713718589679646221
fastest-code
primes
Soham Chowdhury
fuente
fuente
12259243
se usará para probar qué tan rápidos son los programas, los resultados serán tan pequeños que no obtendrá diferencias estadísticamente significativas.Respuestas:
Python (con PyPy JIT v1.9) ~ 1.9s
Uso de un tamiz cuadrático polinómico múltiple . Tomé esto como un desafío de código, así que opté por no usar ninguna biblioteca externa (aparte de la
log
función estándar , supongo). Al cronometrar, se debe usar PyPy JIT , ya que da como resultado tiempos 4-5 veces más rápidos que los de cPython .Actualización (2013-07-29):
desde la publicación original, he realizado varios cambios menores, pero significativos, que aumentan la velocidad general en un factor de aproximadamente 2.5x.
Actualización (2014-08-27):
como esta publicación aún recibe atención, he actualizado la
my_math.py
corrección de dos errores, para cualquier persona que pueda estar usándola:isqrt
fue defectuoso, a veces produciendo resultados incorrectos para valores muy cercanos a un cuadrado perfecto. Esto se ha corregido y el rendimiento aumentó mediante el uso de una semilla mucho mejor.is_prime
Ha sido actualizado. Mi intento anterior de eliminar 2 sprps cuadrados perfectos fue poco entusiasta, en el mejor de los casos. Agregué una verificación de 3 sprp, una técnica utilizada por Mathmatica, para garantizar que el valor probado no tenga cuadrados.Actualización (2014-11-24):
si al final del cálculo no se encuentran congruencias no triviales, el programa ahora tamiza polinomios adicionales. Esto se marcó previamente en el código como
TODO
.mpqs.py
my_math.py
Muestra de E / S:
Nota: no usar la
--verbose
opción dará tiempos ligeramente mejores:Conceptos básicos
En general, un tamiz cuadrático se basa en la siguiente observación: cualquier compuesto compuesto n puede representarse como:
Esto no es muy difícil de confirmar. Como n es impar, la distancia entre dos cofactores de n debe ser par 2d , donde x es el punto medio entre ellos. Además, la misma relación se mantiene para cualquier múltiplo de n
Tenga en cuenta que si cualquiera de tales x y D se pueden encontrar, resultará inmediatamente en un factor de (no necesariamente primo) de n , ya que x + d y x - delta tanto brecha n por definición. Esta relación puede debilitarse aún más, como consecuencia de permitir posibles congruencias triviales, a la siguiente forma:
Entonces, en general, si podemos encontrar dos cuadrados perfectos que sean mod n equivalentes , entonces es bastante probable que podamos producir directamente un factor de n a la gcd (x ± d, n) . Parece bastante simple, ¿verdad?
Excepto que no lo es. Si pretendemos realizar una búsqueda exhaustiva de todas las posibles x , tendríamos que buscar en todo el rango desde [ √ n , √ ( 2n ) ], que es marginalmente más pequeño que la división de prueba completa, pero también requiere una
is_square
operación costosa cada iteración para confirmar el valor de d . A menos que se sabe de antemano que n tiene factores muy cerca √ n , sala de primera instancia es probable que sea más rápido.Quizás podamos debilitar aún más esta relación. Supongamos que elegimos una x , tal que para
Se conoce fácilmente una factorización prima completa de y . Si tuviéramos suficientes relaciones, deberíamos ser capaces de construir una d adecuada , si elegimos un número de y tal que su producto sea un cuadrado perfecto; es decir, todos los factores primos se usan un número par de veces. De hecho, si tenemos más y más que el número total de factores primos únicos que contienen, se garantiza que existe una solución; Se convierte en un sistema de ecuaciones lineales. La pregunta ahora es, ¿cómo elegimos tal x ? Ahí es donde entra en juego el tamizado.
El tamiz
Considere el polinomio:
Entonces, para cualquier primo p y entero k , lo siguiente es cierto:
Esto significa que después de resolver las raíces del polinomio mod p , es decir, has encontrado una x tal que y (x) ≡ 0 (mod p) , ergo y es divisible por p , entonces has encontrado un número infinito de tal x . De esta manera, puede tamizar sobre un rango de x , identificando pequeños factores primos de y , con suerte encontrando algunos para los cuales todos los factores primos son pequeños. Tales números conocidos como k-smooth , donde k es el factor primo más grande utilizado.
Sin embargo, hay algunos problemas con este enfoque. No todos los valores de x son adecuados, de hecho, solo hay muy pocos de ellos, centrados alrededor de √ n . Los valores más pequeños se volverán en gran medida negativos (debido al término -n ), y los valores más grandes se volverán demasiado grandes, de modo que es poco probable que su factorización prima consista solo en números primos pequeños. Habrá una cantidad de tales x , pero a menos que el compuesto que está factorizando sea muy pequeño, es muy poco probable que encuentre suficientes suavidades para resultar en una factorización. Y así, para n más grande , se hace necesario tamizar sobre múltiples polinomios de una forma dada.
Polinomios múltiples
¿Entonces necesitamos más polinomios para tamizar? Qué tal esto:
Eso funcionará Tenga en cuenta que A y B podrían ser literalmente cualquier valor entero, y las matemáticas aún se mantienen. Todo lo que necesitamos hacer es elegir algunos valores aleatorios, resolver la raíz del polinomio y tamizar los valores cercanos a cero. En este punto, podríamos llamarlo lo suficientemente bueno: si arrojas suficientes piedras en direcciones aleatorias, es probable que rompas una ventana tarde o temprano.
Excepto, hay un problema con eso también. Si la pendiente del polinomio es grande en la intersección x, que será si no es relativamente plana, solo habrá unos pocos valores adecuados para tamizar por polinomio. Funcionará, pero terminarás tamizando un montón de polinomios antes de obtener lo que necesitas. ¿Podemos hacerlo mejor?
Podemos hacerlo mejor. Una observación, como resultado de Montgomery, es la siguiente: si A y B se eligen de manera tal que exista algo de C que satisfaga
entonces todo el polinomio se puede reescribir como
Además, si A es elegido para ser un cuadrado perfecto, el principal Un término puede despreciarse mientras tamizado, lo que resulta en valores mucho más pequeños, y una curva más plana mucho. Para que exista una solución de este tipo, n debe ser un mod de residuo cuadrático √ A , que se puede conocer inmediatamente calculando el símbolo de Legendre : ( n | √A ) = 1 . Tenga en cuenta que para resolver B , es necesario conocer una factorización prima completa de √A (para tomar la raíz cuadrada modular √n (mod √A) ), por lo que normalmente se elige √A como primo.
Entonces se puede mostrar que si , entonces para todos los valores de x ∈ [ -M, M ] :
Y ahora, finalmente, tenemos todos los componentes necesarios para implementar nuestro tamiz. O nosotros?
Poderes de los primes como factores
Nuestro tamiz, como se describió anteriormente, tiene un defecto importante. Puede identificar qué valores de x resultarán en una y divisible por p , pero no puede identificar si esta y es divisible por una potencia de p . Para determinar eso, tendríamos que realizar una división de prueba en el valor a tamizar, hasta que ya no sea divisible por p . Parecíamos haber llegado a un punto muerto: el objetivo del tamiz era que no teníamos que hacer eso. Hora de revisar el libro de jugadas.
Eso se ve muy útil. Si la suma de ln de todos los factores primos pequeños de y está cerca del valor esperado de ln (y) , entonces es casi un hecho que y no tiene otros factores. Además, si ajustamos un poco el valor esperado, también podemos identificar valores tan suaves que tienen varios poderes de primos como factores. De esta manera, podemos usar el tamiz como un proceso de 'preselección' y solo factorizar aquellos valores que probablemente sean suaves.
Esto tiene algunas otras ventajas también. Tenga en cuenta que los primos pequeños contribuyen muy poco a la suma de ln , pero requieren el mayor tiempo de tamizado. Tamizar el valor 3 requiere más tiempo que 11, 13, 17, 19 y 23 combinados . En cambio, podemos omitir los primeros números primos y ajustar el umbral en consecuencia, asumiendo que un cierto porcentaje de ellos hubiera pasado.
Otro resultado, es que se permitirá que una serie de valores 'se deslicen', que en su mayoría son suaves, pero contienen un solo cofactor grande. Podríamos descartar estos valores, pero supongamos que encontramos otro valor mayormente uniforme, con exactamente el mismo cofactor. Entonces podemos usar estos dos valores para construir una y utilizable ; Como su producto contendrá este cofactor grande al cuadrado, ya no necesita ser considerado.
Poniendolo todo junto
Lo último que debemos hacer es usar estos valores de y construir una x y d adecuadas . Supongamos que solo consideramos los factores no cuadrados de y , es decir, los factores primos de una potencia impar. Entonces, cada y se puede expresar de la siguiente manera:
que se puede expresar en forma de matriz:
El problema es encontrar un vector v tal que vM = ⦳ (mod 2) , donde ⦳ es el vector nulo. Es decir, para despejar el espacio nulo izquierda de M . Esto puede hacerse en un número de maneras, el más simple de los cuales es para llevar a cabo Gaussian Eliminación en M T , en sustitución de la operación de adición fila con una fila xor . Esto dará como resultado una serie de vectores de base de espacio nulo, cualquier combinación de los cuales producirá una solución válida.
La construcción de x es bastante sencilla. Es simplemente el producto de Ax + B para cada uno de los y utilizados. La construcción de d es un poco más complicada. Si tomáramos el producto de todo y , terminaríamos con un valor con 10s de miles, si no 100s de miles de dígitos, para lo cual necesitamos encontrar la raíz cuadrada. Este cálculo es poco costoso. En cambio, podemos hacer un seguimiento de los poderes pares de los números primos durante el proceso de tamizado, y luego usar las operaciones y y xor en los vectores de factores no cuadrados para reconstruir la raíz cuadrada.
Parece que he alcanzado el límite de 30000 caracteres. Ahh bien, supongo que es lo suficientemente bueno.
fuente
Bueno, tu 38! +1 rompió mi script php, no estoy seguro de por qué. De hecho, cualquier semi-prime de más de 16 dígitos rompe mi script.
Sin embargo, usando 8980935344490257 (86028157 * 104395301) mi script logró un tiempo de 25.963 segundos en la computadora de mi casa (2.61GHz AMD Phenom 9950). Mucho más rápido que mi computadora de trabajo, que fue casi 31 segundos a 2.93GHz Core 2 Duo.
php - 757 caracteres incl. nuevas lineas
Me interesaría ver este mismo algoritmo en algún otro lenguaje compilado.
fuente
lcm(2, 3, 5, 7) == 210
, el patrón de números eliminados por estos factores se repetirá cada 210 números, y solo quedan 48. De esa manera, puede eliminar el 77% de todos los números de la división de prueba, en lugar del 50% tomando solo probabilidades.