Factorización usando curvas elípticas
Si su programa de visualización de páginas Web acepta cookies, ud. podrá completar la factorización de un número grande en varias sesiones. Sólo deberá recargar esta página.
El tiempo de ejecución dependerá de la magnitud del segundo factor primo más grande y la velocidad de su computadora.
Como todos los cálculos se realizan en su computadora, ud. podrá desconectarse de Internet durante la factorización si así lo desea.
Además puede entrar expresiones que usen los siguientes operadores y paréntesis:
- + para suma
- - para resta
- * para multiplicación
- / para división entera
- ^ para exponenciación
- n!: factorial
- p#: primorial (producto de todos los primos menores o iguales que p).
- B(n): número pseudoprimo anterior a n.
- F(n): número de Fibonacci Fn.
- L(n): número de Lucas Ln = Fn-1 + Fn+1.
- N(n): número pseudoprimo posterior a n.
- P(n): particiones irrestrictas (cantidad de descomposiciones de n en sumas de números enteros sin tener en cuenta el orden).
Los tests usados en las funciones B y N incluyen divisiones por los cien primeros números primos y luego hasta 20 tests de Rabin-Miller. Así que hay una muy alta probabilidad de que el número hallado sea primo.
El valor final debe tener 10000 o menos dígitos, los resultados intermedios deben tener como máximo 20000 dígitos y en el caso de divisiones, el dividendo debe ser múltiplo del divisor.
La siguiente tabla muestra los valores óptimos de B1 según la cantidad de dígitos del factor y la cantidad esperada de curvas usando ese límite. Estos valores son promedios.
Dígitos | Valor de B1 | Curvas esperadas |
15 | 2000 | 25 |
20 | 11000 | 90 |
25 | 50000 | 300 |
30 | 250000 | 700 |
35 | 1 000000 | 1800 |
40 | 3 000000 | 5100 |
45 | 11 000000 | 10600 |
50 | 43 000000 | 19300 |
55 | 110 000000 | 49000 |
60 | 260 000000 | 124000 |
65 | 850 000000 | 210000 |
70 | 2900 000000 | 340000 |
Este programa usa 25 curvas con límite B1 = 2000, 300 curvas con límite B1 = 50000, 1675 curvas con límite B1 = 1000000 y finalmente usa curvas con límite B1 = 11000000 hasta encontrar todos los factores.
Factorización de números de Cunningham
Si el número a factorizar tiene la forma ab ± 1 (forma de Cunningham) o si es un número de Fibonacci o de Lucas, el programa encuentra todos los factores algebraicos y de Aurifeuille antes de utilizar el método de ECM.
Si el cuadro de selección Usar tablas de Cunningham en el servidor está habilitado, el applet le pide al servidor los factores conocidos mayores que 109, y luego trata de completar la factorización.
Las fuentes de los datos almacenados en el servidor son:
Factorización de un número en varias computadoras
El algoritmo de factorización ECM se puede correr fácilmente en paralelo. Para hacer esto, ejecute la factorización en la primera computadora desde la curva 1, ejecútela en la segunda computadora desde la curva 10000, en la tercera computadora desde la curva 20000, y así sucesivamente. Para cambiar el número de curva, simplemente escríbalo en la caja de entrada que se encuentra abajo a la izquierda y apriete Enter o presione el botón Nueva curva.
Cuando alguna de las máquinas encuentre un nuevo factor, entre este factor en las otras computadoras escribiéndolo en la caja que se encuentra abajo a la derecha y apretando la tecla Enter (o presionando el botón Factor).
Factorización en lotes ¡Nuevo!
Escriba una expresión por línea, y luego presione el botón apropiado. La salida se mostrará en la ventana inferior.
Factorización utilizando el método de criba cuadrática (SIQS)
Cuando el número a factorizar se encuentra en el rango de 31 a 90 dígitos, después de calcular algunas curvas para hallar los factores pequeños, el programa cambia a SIQS (si la casilla de verificación que se encuentra debajo del applet lo habilita), que es un algoritmo que es mucho más rápido que ECM cuando el número tiene dos factores primos grandes. Como este método necesita gran cantidad de memoria de su computadora, si ud. arranca otra vez el applet la factorización comenzará desde el principio. Para comenzar a factorizar inmediatamente mediante SIQS, puede entrar 0 en la caja Nueva Curva.
Los números de curva en los que se produce el cambio a SIQS son:
Dígitos | 31-35 | 36-40 | 41-45 | 46-50 | 51-55 | 56-60 | 61-65 | 66-70 | 71-75 | 76-80 | 81-85 | 86-90 |
Curva | 5 | 8 | 15 | 25 | 27 | 32 | 43 | 70 | 150 | 300 | 350 | 600 |
fuente:alpertron.com.ar
|