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 dos algoritmos rápidos: el método de curvas elípticas (ECM) y el de criba cuadrática (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.

Como todos los cálculos se realizan en tu computadora, puedes desconectarla de Internet 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 de programación C y compilado en asm.js y WebAssembly, que son los lenguajes que entienden los navegadores Web. 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.

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: desplaza a la izquierda la cantidad de bits (o multiplica por la potencia de 2) indicada en el operando derecho. Ejemplo: 5 SHL 3 = 40.
  • SHR: desplaza a la derecha la cantidad de bits (o divide por la potencia de 2) indicada en el operando derecho. Ejemplo: -19 SHR 2 = -5.
  • n!: factorial (n debe ser mayor o igual que cero). Ejemplo: 6! = 6 × 5 × 4 × 3 × 2 = 720.
  • p#: primorial (producto de todos los primos menores o iguales a p). Ejemplo: 12# = 11 × 7 × 5 × 3 × 2 = 2310.
  • B(n): Número probablemente primo anterior a n. Ejemplo: B(24) = 23.
  • F(n): Número de Fibonacci Fn que corresponde a la secuencia 0, 1, 1, 2, 3, 5, 8, 13, 21, etc. donde cada elemento es igual a la suma de los dos anteriores. Ejemplo: F(7) = 13.
  • L(n): Número de Lucas Ln = Fn-1 + Fn+1
  • N(n): Número probablemente primo posterior a n. Ejemplo: N(24) = 29.
  • P(n): particiones irrestrictas (cantidad de descomposiciones de n en sumas de números enteros sin tener en cuenta el orden). Ejemplo: P(4) = 5 porque el número 4 se puede particionar de 5 formas distintas: 4 = 3+1 = 2+2 = 2+1+1 = 1+1+1+1.
  • Gcd(m,n): Máximo común divisor de estos dos números enteros. Ejemplo: GCD(12,16) = 4.
  • Modinv(m,n): inverso de m modulo n, sólo válido cuando m y n son coprimos, es decir que no tienen factores en común. Ejemplo: Modinv(3,7) = 5 porque 3 × 5 ≡ 1 (mod 7)
  • Modpow(m,n,r): halla mn módulo r. Ejemplo: Modpow(3, 4, 7) = 4, porque 34 ≡ 4 (mod 7).
  • Totient(n): cantidad de enteros positivos menores que n coprimos con n. Ejemplo: Totient(6) = 2 porque 1 y 5 no tienen factores en común con 6.
  • IsPrime(n): retorna cero si n no es un primo probable y -1 si lo es. Ejemplo: IsPrime(5) = -1.
  • NumDivs(n): cantidad de divisores positivos de n. Ejemplo: NumDivs(28) = 6 porque los divisores de 28 son 1, 2, 4, 7, 14 y 28.
  • SumDivs(n): suma de todos los divisores positivos de n. Ejemplo: SumDivs(28) = 56 porque 1 + 2 + 4 + 7 + 14 + 28 = 56.
  • NumDigits(n,r): cantidad de dígitos de n en base r. Ejemplo: NumDigits(13, 2) = 4 porque 13 en binario (base 2) se expresa como 1101.
  • SumDigits(n,r): suma de dígitos de n en base r. Ejemplo: SumDigits(213, 10) = 6 porque la suma de los dígitos expresados en decimal es 2+1+3 = 6.
  • RevDigits(n,r): halla el valor que se obtiene escribiendo para atrás los dígitos de n en base r. Ejemplo: RevDigits(213, 10) = 312.
  • 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 repetidosEjemplo
0CrecienteNoconcatfact(0,36) = 23
1DecrecienteNoconcatfact(1,36) = 32
2Crecienteconcatfact(2,36) = 2233
3Decrecienteconcatfact(3,36) = 3322

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

La notación km (mod n) significa que el resto de la división de k dividido n es igual al resto de la división de m dividido n. El número n se denomina módulo.

Este método calcula puntos en curvas elípticas, que se representan mediante fórmulas del tipo y² ≡ x³ + ax + b (mod n) donde n es el número a factorizar.

A continuación se muestran los puntos (x, y) en los que se cumple y² ≡ x³ + 4x + 7 (mod 29). Las abscisas corresponden a los valores de x de 0 a 28 y las ordenadas a los valores de y en el mismo rango. Como los cálculos usan aritmética modular (en este caso usando el resto de la división por 29), los puntos que componen la curva elíptica no forman líneas continuas como sería el caso si operásemos con números reales.

Aparte de los puntos mostrados, se utiliza un punto adicional, denominado O, o punto en el infinito.

Mediante complicadas fórmulas, se definen sumas de puntos. De esta manera un punto (x3, y3) que pertenece a la curva mencionada puede ser la suma de otros dos puntos (x1, y1) y (x2, y2) que también pertenecen a la curva.

Un punto (x, y) se puede sumar varias veces consigo mismo, obteniendo un nuevo punto (x4, y4) que es un múltiplo de (x, y).

Cuando el módulo es un número primo y no se cumple 4a³ + 27b² ≡ 0 (mod p), los puntos que conforman la curva elíptica (incluyendo el punto O) forman una estructura matemática llamada grupo. El orden del grupo es igual a la cantidad de puntos. En el gráfico se observan 31 puntos, por lo que el orden del grupo es 32. Se puede demostrar que siempre se puede obtener el punto O multiplicando cualquier punto por el orden del grupo. Como O + O = O, si multiplicamos cualquier punto por un múltiplo del orden del grupo obtenemos este punto O.

Si bien el valor del orden del grupo es difícil de hallar, se puede demostrar que es cercano al número primo usado como módulo. Al variar la curva, se obtiene un grupo diferente, y su orden también es diferente.

Para poder factorizar un número, hay que hallar un múltiplo del orden del grupo correspondiente a alguno de los factores primos.

Por cada curva elíptica a procesar intentamos obtener el punto en el infinito. Se realizan dos pasos.

En el primer paso el algoritmo multiplica puntos por potencias de diferentes números primos menores que una cota denominada B1. Al calcular el maximo común divisor entre la coordenada x del punto hallado y el número a factorizar se puede obtener el primo buscado si todos los factores primos del orden son menores que B1.

Usando el resultado del primer paso, el segundo paso obtiene múltiplos de ese punto hasta la cota máxima B2 y se van multiplicando entre sí las coordenadas x de los puntos hallados. Finalmente se calcula el máximo común divisor entre el valor obtenido y el número a factorizar. En este caso se obtiene el primo buscado si todos los factores primos del orden (excepto uno) son menores que B1 y el mayor factor primo es menor que B2.

Si el máximo común divisor vale 1, hay que intentar con otra curva variando los parámetros a y b y calculando otro punto inicial (x, y) que pertenezca a la nueva curva.

El programa usa varias optimizaciones que son demasiado técnicas como para explicarlas aquí.

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

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.

El algoritmo de factorización ECM se puede correr fácilmente en paralelo. Para hacer esto, ejecuta la factorización en la primera computadora desde la curva 1, ejecútala 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.

La notación km (mod n) significa que el resto de la división de k dividido n es igual al resto de la división de m dividido n. El número n se denomina módulo.

Sea N el número a factorizar. Este número no debe ser una potencia perfecta. Si hallamos de alguna manera dos números enteros X e Y tales que X² ≡ Y² (mod N) y XY (mod N), entonces mcd(X+Y, N) será un factor no trivial (ni 1 ni N) de N.

Para hallar estos valores X e Y, el método busca relaciones que tienen la forma t² ≡ u (mod N) donde u es el producto de números primos pequeños. El conjunto de estos primos es la base de factores. Estas relaciones se obtienen mediante cribas, cuya explicación se encuentra fuera del alcance de esta introducción.

Las relaciones halladas se combinan mediante multiplicaciones. El miembro izquierdo siempre será un cuadrado perfecto porque es el producto de cuadrados. Nuestro objetivo es obtener un cuadrado perfecto en el miembro derecho. Un número es un cuadrado perfecto cuando todos sus factores primos aparecen una cantidad par de veces.

Por ejemplo: si el número a factorizar es N = 1817 y hallamos las siguientes relaciones con la base de factores = {2, 7, 13}:

45² ≡ 24 × 70 × 131

123² ≡ 210 × 70 × 131

En ambas relaciones el miembro derecho no es cuadrado perfecto, porque el exponente de 13 es impar. Pero multiplicándolos obtenemos:

84² ≡ 214 × 13²

84² ≡ (27×13)²

Dado que 27×13 ≡ 1664 obtenemos el factor mcd(84+1664, 1817) = 23.

Qué relaciones se deben multiplicar para obtener un cuadrado perfecto en el miembro derecho es un problema de álgebra lineal y se resuelve mediante matrices.

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 para almacenar relaciones, 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

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: Muestra más información con respecto a los factores hallados.
  • 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.

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 menores 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)

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 13 de diciembre de 2018.