Calculadora de factorización de números enteros


Una expresión numérica o ciclo por línea. Ejemplo: x=3;x=n(x);c<=100;x‑1

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).
  • <, ==, >; <=, >=, != para comparaciones. Los operadores devuelven cero si es falso y -1 si es verdadero.
  • AND, OR, XOR, NOT para lógica binaria.
  • SHL: Desplazar a la izquierda la cantidad de bits indicada en el operando derecho.
  • SHR: Desplazar a la derecha la cantidad de bits indicada en el operando derecho.
  • 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.
  • Modpow(m,n,r): halla mn módulo r.
  • Totient(n): cantidad de enteros positivos menores que n coprimos con n.
  • IsPrime(n): returna cero si n no es un primo probable y -1 si lo es.
  • NumDivs(n): cantidad de divisores positivos de n primos o compuestos.
  • SumDivs(n): suma de divisores positivos de n primos o compuestos.
  • NumDigits(n,r): cantidad de dígitos de n en base r.
  • SumDigits(n,r): suma de dígitos de n en base r.
  • RevDigits(n,r): halla el valor que se obtiene escribiendo para atrás los dígitos de n en base r.
  • ConcatFact(m,n): concatena los factores primos de n de acuerdo al modo expresado en m según lo indicado en la siguiente tabla:
    Modos de la función ConcatFact
    ModoOrden de los factoresFactores repetidos
    0CrecienteNo
    1DecrecienteNo
    2Creciente
    3Decreciente

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.
  • 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.
  • Salida hexadecimal: Indica que los valores mostrados en pantalla deben figurar en hexadecimal en vez de decimal, que es lo habitual. Para ingresar números en el formato hexadecimal es necesario que tengan los caracteres 0x adelante. Por ejemplo 0x38 = 56. El programa muestra números en hexadecimal con tipo monoespaciado.
  • 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

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 o cinco 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.
  • Tercera expresión: Contiene la expresión de finalización del ciclo. Si es distinto que cero (indicando verdadero) el ciclo termina, en caso contrario, continúa.
  • Cuarta expresión: Contiene la expresión a factorizar.
  • Quinta expresión (opcional): Si esta expresión no vale cero (indicando verdadero), se muestra o factoriza la cuarta expresión, y si es cero (indicando falso), se ignora la cuarta expresión.

Excepto la primera expresión, las demás expresiones deben incluir la variable x y/o el contador c.

Si la expresión de finalización es falsa después de procesar 1000 números, aparecerá el botón Continuar. Apretando este botón hará que el programa procese los siguientes 1000 números, y así sucesivamente.

Ejemplo 1: 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.

Ejemplo 2: Hallar los números de Smith meores que 10000. Un número de Smith, de acuerdo a Wikipedia, es un número compuesto tal que, en una base dada (por defecto en base 10), la suma de sus dígitos es igual a la suma de los dígitos de su factorización en números primos. La línea a escribir es: x=1;x=x+1;x<10000;x;sumdigits(x, 10)==sumdigits(concatfact(2,x),10) and not isprime(x)

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 20 de junio de 2018.