Calculadora de factorización de números enteros

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.
• Ans: obtiene la última respuesta.
• AND, OR, XOR, NOT para lógica binaria. Las operaciones se hacen en binario (base 2). Se agregan infinitos ceros (unos) a la izquerda de los números positivos (negativos).
• SHL o <<: Si b ≥ 0, a SHL b desplaza el valor a a la izquierda la cantidad de bits especificada por b. Esto equivale a a × 2^b. En caso contrario, a SHL b desplaza el valor a a la derecha la cantidad de bits especificada por −b. Esto equivale a floor(a / 2^−b). Ejemplo: 5 SHL 3 = 40.
• SHR o >>: Si b ≥ 0, a SHR b desplaza el valor a a la derecha la cantidad de bits especificada por b. Esto equivale a floor(a / 2^b). En caso contrario, a SHR b desplaza el valor a a la izquierda la cantidad de bits especificada por −b. Esto equivale a a × 2^−b. Ejemplo: -19 SHR 2 = -5.
• n!: factorial (n debe ser mayor o igual que cero). Ejemplo: 6! = 6 × 5 × 4 × 3 × 2 = 720.
• n!! ... !: factorial múltiple (n debe ser mayor o igual que cero). Es el producto de n por n − k por n − 2k ... (todos los números son mayores que cero) donde k es la cantidad de signos de exclamación. Ejemplo: 7!! = 7 × 5 × 3 × 1 = 105.
• 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 F_n 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 L_n = F_n-1 + F_n+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 números enteros. Ejemplo: GCD(12,16) = 4.
• Lcm(m,n, ...): Mínimo común múltiplo de estos números enteros. Ejemplo: LCM(12,16,24) = 48.
• 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 mⁿ módulo r. Ejemplo: Modpow(3, 4, 7) = 4, porque 3⁴ ≡ 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.
• Jacobi(m,n): obtiene el símbolo de Jacobi de m y n. Cuando el segundo argumento es primo, el resultado es cero si m es múltiplo de n, es uno si hay una solución a x² ≡ m (mód n) y es igual a −1 cuando la congruencia mencionada no tiene soluciones.
• Random(m,n): número entero aleatorio entre m y n.
• Abs(n): valor absoluto de n.
• IsPrime(n): retorna cero si n no es un primo probable y -1 si lo es. Ejemplo: IsPrime(5) = -1.
• Sqrt(n): parte entera de la raíz cuadrada del argumento.
• Iroot(n,r): Raíz r-ésima entera del primer argumento. Ejemplo: Iroot(8, 3) = 2.
• NumFact(n): cantidad de factores primos distintos de n. Ejemplo: NumFact(28) = 2 porque los factores primos son 2 y 7.
• MinFact(n): mínimo factor primo de n. Ejemplo: MinFact(28) = 2 porque los factores primos son 2 y 7.
• MaxFact(n): máximo factor primo de n. Ejemplo: MaxFact(28) = 7 porque los factores primos son 2 y 7.
• 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:

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

La notación k ≡ m (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 (x₃, y₃) que pertenece a la curva mencionada puede ser la suma de otros dos puntos (x₁, y₁) y (x₂, y₂) que también pertenecen a la curva.

Un punto (x, y) se puede sumar varias veces consigo mismo, obteniendo un nuevo punto (x₄, y₄) 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, comenzando con un punto aleatorio (x, y) perteneciente a una curva elíptica aleatoria y² ≡ x³ + ax + b (mód n). Como es muy difícil resolver ecuaciones cuadráticas o cúbicas módulo un número compuesto, conviene elegir números aleatorios para x, y y a. Luego podemos calcular fácilmente b ≡ y² − x³ − ax (mód n)

En el primer paso el algoritmo multiplica puntos por potencias de diferentes números primos menores que una cota denominada B1. Al calcular el máximo 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 el punto inicial (x, y) y el parámetro a, calculando el nuevo parámetro b usando la fórmula.

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.

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 k ≡ m (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 X≠Y (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² ≡ 2⁴ × 7⁰ × 13¹

123² ≡ 2¹⁰ × 7⁰ × 13¹

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

84² ≡ 2¹⁴ × 13²

84² ≡ (2⁷×13)²

Dado que 2⁷×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.

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 a^b ± 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 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 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.