Calculadora de factorización de números enteros
- Alpertron
- Aplicaciones web
- Calculadora de factorización de números enteros
Escriba una expresión numérica o un ciclo por línea. Ejemplo: x=3;x=n(x);c<=100;x‑1
Esta aplicación web le permite factorizar números o expresiones numéricas utilizando dos algoritmos rápidos: el método de curvas elípticas (ECM) y el método de criba cuadrática especial (SIQS).
El programa utiliza almacenamiento local para recordar el avance de la factorización. Esto le permite continuar la factorización de un número grande en varias sesiones: basta con recargar esta página para reanudar el proceso exactamente donde quedó.
Todos los cálculos se realizan de manera local en su computadora. Por este motivo, podrá desconectarla de Internet mientras la factorización continúa sin interrupciones. Una vez ejecutada por primera vez, esta aplicación puede iniciarse sin conexión.
El código fuente está escrito en lenguaje C y se compila a JavaScript y WebAssembly, que son formatos comprendidos por los navegadores web. WebAssembly suele ser más rápido, aunque no todos los navegadores lo soportan. Podrá ver qué versión se está utilizando al factorizar un número.
Existe una lista de videos sobre el funcionamiento de esta calculadora.
También puede consultar los récords de factorización obtenidos con esta aplicación.
Expresiones
Usted puede ingresar expresiones que utilicen los siguientes operadores y paréntesis:
- + para suma.
- - para resta.
- * para multiplicación.
- / para división entera.
- % para obtener el resto de la división entera.
- ^ o ** para exponenciación (el exponente debe ser mayor o igual que cero).
- <, ==, >, <=, >=, != para comparaciones. Estos operadores devuelven cero si la comparación es falsa y –1 si es verdadera.
- Ans: obtiene la última respuesta generada.
- AND, OR, XOR, NOT para operaciones de lógica binaria. Las operaciones se realizan en base 2. Los números positivos se rellenan con infinitos ceros a la izquierda, y los negativos con infinitos unos.
- SHL o <<: Si b ≥ 0, a SHL b desplaza a hacia la izquierda b bits, lo que equivale a multiplicar por 2b. Si b < 0, desplaza a a la derecha –b bits, equivalente a floor(a / 2−b). Ejemplo: 5 SHL 3 = 40.
- SHR o >>: Si b ≥ 0, a SHR b desplaza a a la derecha b bits, equivalente a floor(a / 2b). Si b < 0, desplaza a a la izquierda –b bits. Ejemplo: –19 SHR 2 = –5.
- n!: factorial de n (con n ≥ 0). Ejemplo: 6! = 720.
- n!!...!: factorial múltiple. Es el producto de n, n–k, n–2k, etc., donde k es la cantidad de signos de exclamación, y todos los valores deben ser positivos. Ejemplo: 7!! = 7 × 5 × 3 × 1 = 105.
- p#: primorial, es decir, el producto de los números primos ≤ p. Ejemplo: 12# = 2310.
- B(n): número probablemente primo inmediatamente anterior a n. Ejemplo: B(24) = 23.
- F(n): número de Fibonacci Fn, donde la sucesión inicia en 0, 1, 1, 2, 3, 5, 8, 13... Ejemplo: F(7) = 13.
- L(n): número de Lucas Ln = Fn–1 + Fn+1.
- N(n): número probablemente primo inmediatamente posterior a n. Ejemplo: N(24) = 29.
- P(n): número de particiones irrestrictas de n (descomposiciones en sumas sin importar el orden). Ejemplo: P(4) = 5.
- Gcd(m,n,...): máximo común divisor. Ejemplo: GCD(12,16) = 4.
- Lcm(m,n,...): mínimo común múltiplo. Ejemplo: LCM(12,16,24) = 48.
- FloorDiv(m,n): parte entera del cociente m/n. Ejemplos: floordiv(10,7) = 1, floordiv(–10,7) = –2.
- Mod(m,n): m módulo |n|. Ejemplos: Mod(10,7)=3, Mod(–10,7)=4.
- Modinv(m,n): inverso modular de m módulo n, solo válido cuando ambos números son coprimos. Ejemplo: Modinv(3,7) = 5.
- Modpow(m,n,r): calcula mn mod r. Ejemplo: Modpow(3,4,7) = 4.
- Totient(n): cantidad de enteros positivos menores que n que son coprimos con él. Ejemplo: Totient(6) = 2.
- Jacobi(m,n): símbolo de Jacobi.
- Random(m,n): número entero aleatorio entre m y n.
- Abs(n): valor absoluto.
- Sign(n): devuelve 0 si n = 0, 1 si n > 0, –1 si n < 0.
- IsPrime(n): devuelve –1 si n es primo probable y 0 si no lo es.
- Sqrt(n): parte entera de la raíz cuadrada.
- Iroot(n,r): raíz entera r-ésima. Ejemplo: Iroot(8,3) = 2.
- NumFact(n): cantidad de factores primos distintos. Ejemplo: NumFact(28) = 2.
- MinFact(n): menor factor primo. Ejemplo: MinFact(28) = 2.
- MaxFact(n): mayor factor primo. Ejemplo: MaxFact(28) = 7.
- NumDivs(n): cantidad de divisores positivos. Ejemplo: NumDivs(28) = 6.
- SumDivs(n): suma de divisores positivos. Ejemplo: SumDivs(28)=56.
- NumDigits(n,r): cantidad de dígitos de n en base r. Ejemplo: NumDigits(13,2)=4.
- SumDigits(n,r): suma de dígitos en la base indicada.
- RevDigits(n,r): invierte los dígitos de n en base r.
- ConcatFact(m,n): concatena factores primos según el modo especificado.
| Modo | Orden de los factores | Factores repetidos | Ejemplo |
|---|---|---|---|
| 0 | Creciente | No | concatfact(0,36)=23 |
| 1 | Decreciente | No | concatfact(1,36)=32 |
| 2 | Creciente | Sí | concatfact(2,36)=2233 |
| 3 | Decreciente | Sí | concatfact(3,36)=3322 |
Puede usar el prefijo 0x para ingresar números hexadecimales. Por ejemplo, 0x38 es igual a 56.
Factorización usando el método de curvas elípticas (ECM)
La notación k ≡ m (mod n) significa que el resto de la división de k entre n es igual al resto de la división de m entre n. Al número n se lo denomina módulo.
Este método calcula puntos en curvas elípticas, las cuales se representan mediante fórmulas como y² ≡ x³ + ax + b (mod n), donde n es el número que se desea factorizar.
En la siguiente imagen, usted puede ver los puntos (x, y) que cumplen y² ≡ x³ + 4x + 7 (mod 29). Dado que los cálculos usan aritmética modular (en este caso tomando el resto de la división por 29), solo existen los pares de enteros (x, y) que satisfacen la ecuación. Por ello, la curva se muestra como un conjunto de puntos discretos en lugar de una línea continua, como ocurriría si trabajáramos con números reales.
Además de estos puntos, la curva incluye un elemento especial denominado O, o punto en el infinito.
Mediante fórmulas algebraicas específicas, es posible definir una ley de suma, de modo que la suma de dos puntos (x1, y1) y (x2, y2) pertenecientes a la curva produce otro punto (x3, y3) que también pertenece a la curva.
Si usted suma repetidamente un punto P = (x, y) consigo mismo (proceso llamado multiplicación de puntos), obtiene múltiplos de ese punto, usualmente escritos como 2P, 3P, 4P, etc.
Cuando el módulo es un número primo y se cumple que 4a³ + 27b² ≢ 0 (mod p), los puntos de la curva elíptica (incluyendo el punto O) forman una estructura matemática llamada grupo. El orden del grupo es la cantidad total de puntos. En el gráfico se observan 31 puntos visibles. Si incluimos el punto en el infinito, el grupo tiene 32 puntos, que constituye su orden. Como O + O = O, si multiplicamos cualquier punto por un múltiplo del orden del grupo, obtenemos el punto O.
Aunque el orden del grupo es difícil de calcular, siempre está cercano al valor del módulo según el teorema de Hasse. Si cambiamos la curva, obtenemos un grupo diferente y, por lo tanto, un orden distinto.
Para factorizar un número n, realizamos multiplicaciones de puntos hasta encontrar un múltiplo del orden del grupo correspondiente a alguno de los factores primos de n. En ese momento, un cálculo de máximo común divisor puede revelar dicho factor.
Para cada curva elíptica, intentamos alcanzar el punto en el infinito comenzando desde un punto aleatorio (x, y) perteneciente a una curva elíptica aleatoria y² ≡ x³ + ax + b (mod n). Como resolver ecuaciones cuadráticas o cúbicas módulo un número compuesto es muy difícil, conviene elegir valores aleatorios para x, y y a. Luego podemos calcular b ≡ y² − x³ − ax (mod n).
En el primer paso del algoritmo, multiplicamos el punto por potencias de diversos números primos menores que un límite denominado B1. Al calcular el máximo común divisor entre la coordenada x del punto obtenido y el número a factorizar, es posible obtener un factor primo de n, siempre que todos los factores primos del orden del grupo sean menores que B1.
Usando el punto obtenido en el Paso 1, el Paso 2 calcula nuevos múltiplos de ese punto para todos los primos entre B1 y B2. Luego multiplicamos las coordenadas x de todos los puntos hallados en este segundo paso. Finalmente, calculamos el máximo común divisor entre ese producto y el número a factorizar. En este caso, el algoritmo puede encontrar el factor buscado si todos los factores primos (excepto uno) del orden del grupo son menores que B1, y si el mayor de dichos factores es menor que B2.
Si el máximo común divisor es igual a 1 (o igual a n), entonces esa curva no permitió hallar un factor. En ese caso, el algoritmo prueba con otra curva aleatoria: es necesario cambiar el punto inicial (x, y) y el parámetro a, y calcular el nuevo valor de b mediante la misma fórmula.
El programa utiliza muchas optimizaciones del método ECM que están fuera del alcance de esta sección de ayuda.
El tiempo de ejecución depende principalmente del tamaño del segundo mayor factor primo de n y de la velocidad de su computadora.
| Dígitos | Valores de B1 | Curvas esperadas |
|---|---|---|
| 15 | 2.000 | 25 |
| 20 | 11.000 | 90 |
| 25 | 50.000 | 300 |
| 30 | 250.000 | 700 |
| 35 | 1.000.000 | 1.800 |
| 40 | 3.000.000 | 5.100 |
| 45 | 11.000.000 | 10.600 |
| 50 | 43.000.000 | 19.300 |
| 55 | 110.000.000 | 49.000 |
| 60 | 260.000.000 | 124.000 |
| 65 | 850.000.000 | 210.000 |
| 70 | 2.900.000.000 | 340.000 |
El programa prueba aproximadamente la cantidad de curvas indicada en la tabla, dependiendo del valor B1 seleccionado (hasta un máximo de 110.000.000), hasta que se encuentran todos los factores.
Factorización de un número en varias computadoras
El algoritmo de factorización ECM se puede ejecutar de manera paralela sin dificultad. Para hacerlo, inicie el proceso de factorización en la primera computadora desde la curva 1; en la segunda computadora comience desde la curva 10.000; en la tercera computadora desde la curva 20.000; y así sucesivamente.
Para modificar el número de curva, presione el botón Más, ingrese el valor en la caja correspondiente que aparece en la nueva ventana y luego pulse Nueva curva.
Cuando alguna de las computadoras encuentre un factor, vuelva a presionar el botón Más, ingrese el factor hallado y finalmente haga clic en Factor para continuar la descomposición en su dispositivo.
Factorización utilizando el método de criba cuadrática (SIQS)
La notación k ≡ m (mod n) significa que el resto de la división de k entre n es igual al resto de la división de m entre n. Al número n se lo denomina módulo.
Sea N el número a factorizar. Este número no debe ser una potencia perfecta (como a², b³, etc.). Si lo es, el algoritmo no puede producir relaciones válidas. Si de alguna manera encontramos dos enteros X y Y tales que X² ≡ Y² (mod N) y X≠Y (mod N), entonces mcd(X+Y, N) revelará un factor propio de N.
Para hallar estos valores X y Y, el método busca relaciones de la forma t² ≡ u (mod N), donde u es el producto de números primos pequeños. El conjunto de estos primos se denomina base de factores. Estas relaciones se encuentran mediante cribas, cuyo funcionamiento está fuera del alcance de esta introducción.
Las relaciones se combinan multiplicando algunas de ellas. Como el producto de cuadrados siempre produce otro cuadrado, todo el miembro izquierdo resulta ser un cuadrado perfecto. El objetivo es obtener también 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: sea N = 1817 y supongamos que hemos hallado las siguientes relaciones con base de factores = {2, 7, 13}:
45² ≡ 24 × 70 × 131
123² ≡ 210 × 70 × 131
Ambas relaciones tienen un miembro derecho que no es un cuadrado porque el exponente de 13 no es par. Pero, al multiplicarlas, obtenemos:
84² ≡ 214 × 13²
84² ≡ (27×13)²
Dado que 27×13 ≡ 1664, obtenemos el factor mcd(84+1664, 1817) = 23.
Determinar qué relaciones deben multiplicarse para obtener un cuadrado perfecto en el miembro derecho es un problema de álgebra lineal y se resuelve utilizando matrices.
El principal inconveniente de este método es que, a medida que crece el número a factorizar, resulta cada vez más difícil encontrar relaciones; por ello se necesita una variación del método.
La versión SIQS de primos grandes utiliza primos grandes además de la base de factores. El tamaño del primo más grande depende del número a factorizar, pero normalmente es entre 50 y 100 veces mayor que el mayor elemento de la base de factores.
Una relación parcial es una identidad en la que el miembro izquierdo es un cuadrado y el miembro derecho es un producto de los primos de la base de factores multiplicados por un primo grande. Si obtenemos dos relaciones parciales que comparten el mismo primo grande, podemos combinarlas en una relación completa. Esto permite encontrar relaciones aproximadamente el doble de rápido que la variante sin primos grandes.
Por ejemplo, usando nuevamente N = 1817, supongamos que encontramos las siguientes relaciones parciales, donde el número 67 es un primo grande:
71² ≡ 3 × 7 × 67
116² ≡ 11 × 67
Para combinar estas relaciones parciales en una relación completa, las multiplicamos y luego dividimos por el cuadrado del primo grande:
(71 × 116 / 67)² ≡ 3 × 7 × 11
367² ≡ 3 × 7 × 11
La división modular requiere calcular un máximo común divisor extendido.
Cuando el número a factorizar tiene entre 31 y 95 dígitos, después de procesar algunas curvas para encontrar factores pequeños, el programa cambia automáticamente al método SIQS (si la casilla ubicada debajo del applet lo habilita). Este algoritmo es significativamente más rápido que ECM cuando el número tiene dos factores primos grandes. Como este método requiere una gran cantidad de memoria para almacenar relaciones, si usted reinicia el applet, la factorización comienza desde el principio. Para comenzar a factorizar de inmediato usando SIQS, puede ingresar 0 en la caja denominada “New Curve”.
| Dígitos | 31-55 | 56-60 | 61-65 | 66-70 | 71-75 | 76-80 | 81-85 | 86-90 | 91-95 |
|---|---|---|---|---|---|---|---|---|---|
| Curva | 10 | 15 | 22 | 26 | 60 | 130 | 200 | 270 | 350 |
Configuración
Usted puede modificar la configuración de esta aplicación presionando el botón Config cuando el programa no se encuentra realizando una factorización. Al hacerlo, se abrirá una nueva ventana donde podrá seleccionar los siguientes ajustes:
- Dígitos por grupo: Para facilitar la lectura, los números grandes se dividen en grupos separados por espacios. Con esta opción, usted puede especificar cuántos dígitos contendrá cada grupo.
- Información: Si está activada, la aplicación mostrará información adicional sobre los factores hallados.
- Impresión bonita: Si esta casilla está seleccionada, los exponentes aparecerán en superíndice y el signo de multiplicación será “×”. Además, cuando un número tiene más de 30 dígitos, se mostrará la cantidad total de dígitos. Si la casilla está desactivada, los exponentes se indicarán con el símbolo “^” y la multiplicación se mostrará mediante asteriscos. En este modo, nunca se indica la cantidad de dígitos, lo cual facilita copiar los resultados hacia otros programas matemáticos.
- Salida hexadecimal:
Si se activa esta opción, la aplicación mostrará los números en formato hexadecimal en lugar de decimal.
Para ingresar números en hexadecimal, estos deben comenzar con la secuencia
0x. Por ejemplo:0x38equivale a 56. Los números en hexadecimal se muestran empleando un tipo de letra monoespaciado. - Teclado: Permite seleccionar entre un teclado virtual numérico o uno completo (alfanumérico). El teclado virtual aparece automáticamente en pantallas táctiles cuando usted selecciona una caja de entrada.
- Usar tablas de Cunningham en el servidor: Si está activada esta opción y el número a factorizar tiene la forma ab ± 1, la aplicación intentará recuperar factores conocidos desde un servidor Web. Para reducir el tamaño de la base de datos, sólo se incluyen factores primos de al menos 14 dígitos, por lo cual el programa deberá calcular los factores menores por sí mismo. Estos factores provienen de la lista de Jonathan Crombie, que contiene 2.674.850 factores de números de Cunningham.
La configuración se almacena en su dispositivo, de modo que, si vuelve a abrir la calculadora, los ajustes permanecerán intactos.
Factorización en lotes
Escriba una expresión por línea y luego presione el botón Sólo evaluar o Factorizar.
Las líneas en blanco o aquellas que comienzan con el carácter numeral # (comentarios) se copiarán tal cual en la salida.
Expresiones para ciclos: Con una sola línea usted puede evaluar, probar primalidad o factorizar secuencias de números. Para ello, introduzca entre cuatro y cinco expresiones separadas por punto y coma:
- Primera expresión: Debe comenzar con
x=e indica el valor inicial de la variable x. - Segunda expresión: Debe comenzar con
x=e indica cómo debe actualizarse x. - Tercera expresión: Es la condición de finalización del ciclo. Si su valor es distinto de cero (verdadero), el ciclo termina; si vale cero (falso), continúa.
- Cuarta expresión: Indica el número a evaluar o factorizar.
- Quinta expresión (opcional): Si su valor es distinto de cero (verdadero), se muestra o factoriza la cuarta expresión. Si vale cero (falso), la cuarta expresión se ignora.
Excepto la primera, las demás expresiones deben incluir la variable x y/o el contador c.
Si la condición de finalización permanece falsa después de procesar 1000 números, aparecerá el botón Continuar. Al presionarlo, el programa procesará los 1000 valores siguientes y así sucesivamente.
Ejemplo 1: Hallar los factores de los primeros 100 números de la forma “primo impar 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 de 10000.
Un número de Smith es un compuesto cuyo valor, expresado en base 10, tiene la misma suma de dígitos que la suma de dígitos de la factorización de sus factores 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)
La cuarta expresión puede reemplazarse por una cadena de formato seguida de varias expresiones. La cadena de formato determina qué debe mostrarse en pantalla. Dentro de esa cadena pueden utilizarse cláusulas de conversión comenzando con el carácter “%” (en mayúsculas o minúsculas):
- %D: muestra la expresión como número decimal.
- %X: muestra la expresión en hexadecimal.
- %L: muestra sí si la expresión no es cero; muestra no si su valor es cero.
- %FD: factoriza la expresión y muestra los factores en decimal.
- %FX: factoriza la expresión y muestra los factores en hexadecimal.
Las expresiones se escriben después de la cadena de formato, y deben estar separadas por dos puntos. También deben incluirse dos puntos entre la cadena y la primera expresión.
Para mostrar un símbolo de porcentaje real dentro de la cadena de formato, escriba %%.
Para mostrar una comilla, utilice %'.
Ejemplo 3: Para cada número entre –100 y 100, mostrar si es primo y luego mostrar su factorización tanto en decimal como en hexadecimal:
x=-100; x=x+1; x<=100; "%d es primo: %l, %Fd, %Fx":x:isprime(x):x:x
Ejemplo 4: Obtener 33331 dígitos de π usando el algoritmo de Gauss–Legendre (script de Samuel Eraut):
x=10^99999+10^66666/4+10^66666/sqrt(2*10^66666);
x=(x/10^66666+x%10^33333)/2*10^66666 +
(((x/10^33333)%10^33333) - 2^(c-1)*(x/10^66666 - (x/10^66666+x%10^33333)/2)^2 /10^33333 )*10^33333 +
sqrt((x/10^66666)*(x%10^33333));
c<=15;
(x/10^66666+x%10^33333)^2/4/((x/10^33333)%10^33333)/1000;
c==15
En este algoritmo, las tres partes del número x se interpretan como:
- a = dígitos más significativos,
- t = parte intermedia,
- b = los 33333 dígitos menos significativos.
Los nombres a, b y t coinciden con los utilizados en la descripción de Wikipedia sobre el método Gauss–Legendre.
Ejemplo 5: Obtener 33331 dígitos de π usando la fórmula de Bailey–Borwein–Plouffe (BBP), código también escrito por Samuel Eraut:
x=0;
x = x + ( 2^(110742-c*4)/(8*(c-1)+1)
- 2^(110741-c*4)/(8*(c-1)+4)
- 2^(110740-c*4)/(8*(c-1)+5)
- 2^(110740-c*4)/(8*(c-1)+6) );
c<=27674;
x*10^33330/2^110736;
c==27674
Código fuente
Usted puede descargar el código fuente de esta aplicación y del antiguo applet de factorización desde GitHub. El código está escrito en lenguaje C, por lo que es necesario utilizar Emscripten para generar el código JavaScript correspondiente.
Escrito por Dario Alpern. Actualizado el 30 de agosto de 2026.