Calculadora de factorización de números enteros

Esta aplicación factoriza números o expresiones numéricas usando los algoritmos rápidos ECM y SIQS.

Este programa utiliza almacenamiento local para recordar el avance de la factorización, así que puedes completar la factorización de un número grande en varias sesiones. Tu computadora recordará el estado de la factorización. Sólo debes recargar esta página.

El tiempo de ejecución depende de la magnitud del segundo mayor factor primo y de la velocidad del equipo.

Como todos los cáculos se realizan en tu computadora, puedes desconectarla de Intenet mientras progresa la factorización. Puedes arrancar esta aplicación sin conexión de Internet después de la primera corrida.

El código fuente está escrito en lenguaje C y compilado en asm.js y WebAssembly. Este último es más rápido, pero no está soportado en todos los navegadores Web. Podrás ver la versión que se ejecuta al factorizar un número.

Récords de factorización para esta aplicación.

Expresiones

Puedes ingresar expresiones que usen los siguientes operadores y paréntesis:

  • + para suma
  • - para resta
  • * para multiplicación
  • / para división entera
  • % para el resto de la división entera
  • ^ o ** para exponenciación (el exponente debe ser mayor o igual que cero).
  • n!: factorial (n debe ser mayor o igual que cero).
  • p#: primorial (producto de todos los primos menores o iguales a p).
  • B(n): Número probablemente primo 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 probablemente primo posterior a n
  • P(n): particiones irrestrictas (cantidad de descomposiciones de n en sumas de números enteros sin tener en cuenta el orden).
  • Gcd(m,n): Máximo común divisor de estos dos números enteros.
  • Modinv(m,n): inverso de m modulo n, sólo válido cuando gcd(m,n)=1.
  • Modexp(m,n,r): halla mn módulo r.

Puedes usar el prefijo 0x para números hexadecimales, por ejemplo 0x38 es igual a 56.

Valores óptimos de B1 y cantidad de curvas esperadas
DígitosValores de B1Curvas esperadas
15200025
201100090
2550000300
30250000700
351 0000001800
403 0000005100
4511 00000010600
5043 00000019300
55110 00000049000
60260 000000124000
65850 000000210000
702900 000000340000

El programa procesa 25 curvas con límite B1 = 2000, 300 curvas con límite B1 = 50000, 1675 curves con límite B1 = 1000000 y finalmente usa curvas con límite B1 = 11000000 hasta hallar todos los factores.

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, aprieta el botón Más, escríbalo en la caja de entrada que se encuentra en la nueva ventana y presiona el botón Nueva curva.

Cuando una de las otras máquinas descubre un nuevo factor, deberás apretar nueva el botón Más, ingresar dicho factor en la caja de entrada y finalmente apretar el botón Factor.

Factorización utilizando el método de criba cuadrática (SIQS)

Cuando el número a factorizar tiene 31 a 95 dígitos, después de procesar algunas curvas para hallar factores pequeños, el programa ejecuta el algoritmo SIQS, que es mucho más rápido que ECM cuando el número tiene dos factores grandes. Como este método necesita gran cantidad de memoria de tu computadora, si arrancas otra vez el programa la factorización comenzará desde el principio. Para comenzar a factorizar inmediatamente mediante SIQS, deberás apretar el botón Más, ingresar el número cero en la caja de entrada y finalmente apretar el botón Nueva Curva.

Umbral para cambio a SIQS
Dígitos31-5556-6061-6566-7071-7576-8081-8586-9091-95
Curva101522263550100150200

Configuración

Puedes cambiar la configuración de esta aplicación apretando el botón Config mientras el programa no está factorizando. En ese momento aparecerá una nueva ventana donde puedes seleccionar los siguientes ajustes:

  • Dígitos por grupo: Para mejorar la legibilidad, los números grandes se separan mediante espacios formando grupos de una cantidad fija de dígitos. Con esta caja de entrada, puedes determinar la cantidad de dígitos por grupo.
  • Factorización en lotes: La explicación se encuentra en la siguiente sección.
  • Información: No está listo aún.
  • Impresión bonita: Si la casilla de verificación está marcada, los exponentes se muestran con superíndices y el signo de multiplicación es " × ". La aplicación muestra la cantidad de dígitos de los números que tienen más de 30 dígitos. Si la casilla de verificación no está marcada, los exponentes se muestran precedidos por el signo " ^ " y la multiplicación se indica mediante asteriscos. Además nunca se muestra la cantidad de dígitos. Esto facilita la copia de resultados a otros programas matemáticos.
  • Usar tablas de Cunningham en el servidor: Si está seleccionado y el número a factorizar tiene la forma ab ± 1, la aplicación intentará recuperar los factores conocidos del servidor Web. Para reducir esa base de datos, sólo se incluyen factores primos con al menos 14 dígitos, así que la aplicación deberá hallar los factores pequeños. La fuente de estos factores es la lista de factores de Jonathan Crombie e incluye 2674850 factores de números de Cunningham.

La configuración se almacena en tu dispositivo, así que si arrancas nuevamente el navegador, los ajustes no se modificarán.

Factorización en lotes

Después de haber habilitado el modo de factorización en lotes usando la casilla de verificación en la ventana de configuración, escribe una expresión por línea, y luego aprieta el botón Sólo evaluar o Factorizar.

Las líneas en blanco o de comentarios (que comienzan con el carácter numeral '#') se replicarán en la salida.

Expresión para ciclos: con la siguiente sintaxis podrás factorizar o determinar si varios números son primos con sólo digitar una línea. Deberás escribir cuatro expresiones separadas por puntos y coma:

  • Primera expresión: Debe comenzar con la cadena 'x=' e indica el primer valor para la variable x.
  • Segunda expresión:Debe comenzar con la cadena 'x=' e indica el siguiente valor para la variable x. Dicha expresión puede incluir las variables 'x' (la variable) y 'c' (el contador).
  • Tercera expresión: Contiene la expresión de finalización del ciclo. Si es mayor que cero el ciclo termina, en caso contrario, continúa. Puede incluir las variables indicadas arriba.
  • Cuarta expresión: Contiene la expresión a factorizar. Puede incluir las variables indicadas arriba.

Example: Hallar los factores de los primeros 100 números de la forma primo menos 1. La línea a escribir es: x=3;x=n(x);c-100;x-1.

Código fuente

Puedes bajar el código fuente de esta aplicación y del viejo applet de factorización desde GitHub. El código fuente está escrito en lenguaje C, por lo que es necesario Emscripten para generar Javascript.

Escrito por Dario Alpern. Actualizado el 3 de noviembre de 2017.