Algoritmos

algoritmos de factorización de enteros

criba racional es un algoritmo general para la factorizar enteros en factores primos. Es esencialmente un caso especial de la criba general del cuerpo de números, y mientras que es mucho menos eficiente que el algoritmo general, es conceptualmente más simple. Así que, mientras es más bien un algoritmo de factorización sin utilidad en la práctica, es de utilidad como primer paso para aquellos que tratan de entender cómo funciona la criba general de cuerpo de números.

Método

Suponga que intenta factorizar el número compuesto n. Se puede elegir una acotación B, e identificar el factor base (que se llamará P), al conjunto de todos los primos menores o iguales a B. A continuación, se buscan los enteros positivos z tales que tanto z y z + n sean B-liso — i.e. todos sus factores primos están en P. Por tanto, podemos escribir, para los exponentes adecuados ${\displaystyle a_{k}}$,

${\displaystyle z=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

y del mismo modo, para el adecuado ${\displaystyle b_{k}}$, tenemos

${\displaystyle z+n=\prod _{p_{i}\in P}p_{i}^{b_{i}}}$.

Pero ${\displaystyle z}$ y ${\displaystyle z+n}$ son congruentes módulo ${\displaystyle n}$, y por lo que cada número entero tal z que encontramos con dé una relación multiplicativa (mod n) entre los elementos de P, i.e.

${\displaystyle \prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}\;\operatorname {(mod} \;n\operatorname {)} }$

(donde los a_i y b_i son enteros no negativos.)

Cuando se hayan generado las suficientes de estas relaciones (por lo general es suficiente con que el número de relaciones sea un poco más que el tamaño de P), podemos utilizar los métodos del álgebra lineal para multiplicarlos junto a estas varias relaciones de manera que los exponentes de los números primos sean todos pares. Entonces se obtendrá una congruencia de cuadrados de la forma a²≡b² (mod n), que puede convertirse en una factorización de n, n = mcd(a-b,n)×mcd(a+b,n). Esta factorización podría llegar a ser trivial (i.e. n=n×1), en cuyo caso tenemos que intentarlo de nuevo con una combinación diferente de las relaciones; pero con suerte tendremos un par no trivial de los factores de n, y el algoritmo terminará.

Ejemplo

Factorizaremos el entero n = 187 usando la criba racional. Tomaremos arbitrariamente el valor B=7, obteniendo el factor base P = {2,3,5,7}. El primer paso es comprobar la divisibilidad de cada uno de los miembros de P en n; claramente si n es divisible por uno de esos primos, entonces habremos finalizado ya. Sin embargo, 187 no es divisible por 2, 3, 5, o 7. Seguidamente, buscamos los valores adecuados de z; los primeros son 2, 5, 9, y 56. Los cuatro valores adecuados de z dan cuatro relaciones multiplicativas (mod 187):

• 2¹3⁰5⁰7⁰ = 2 ≡ 189 = 2⁰3³5⁰7¹.............(1)

• 2⁰3⁰5¹7⁰ = 5 ≡ 192 = 2⁶3¹5⁰7⁰.............(2)

• 2⁰3²5⁰7⁰ = 9 ≡ 196 = 2²3⁰5⁰7².............(3)

• 2³3⁰5⁰7¹ = 56 ≡ 243 = 2⁰3⁵5⁰7⁰.............(4)

Ahora hay esencialmente varias maneras diferentes de combinar estos y acabar con exponentes pares. Por ejemplo,

• (1)×(4): Después de multiplicarlos y, anulando el factor común de 7 (lo cual podemos hacer puesto que 7 se considera un miembro de P, y se ha determinado que estos son coprimos con n¹ ), esto se reduce a 2⁴ ≡ 3⁸, o 4² ≡ 81². La factorización resultante es 187 = mcd(81-4,187) × mcd(81+4,187) = 11×17.

Alternativamente, la ecuación (3) está en la forma adecuada ya:

• (3): Esto dice que 3² ≡ 14² (mod n), que proporciona la factorización 187 = mcd(14-3,187) × mcd(14+3,187) = 11×17.

Limitaciones del algoritmo

La criba racional, como la criba general del cuerpo de números, no puede factorizar números de la forma p^m, donde p es un primo y m es un entero. Esto no es un gran problema, dado que tales números son estadísticamente raros, y más aún, hay un proceso simple y rápido para verificar si un número dado es de esta forma. Probablemente el método más elegante es verificar si ${\displaystyle \lfloor n^{1/b}\rfloor ^{b}=n}$ se cumple para cualquier 1 < b < log(n) usando una versión entera del método de Newton para la extracción de raíces.²

El mayor problema es encontrar un número suficiente de z tales que para ambos, z y z+n, sean B-lisos. Para cualquier B dado, las proporción de números que son B-lisos decrece rápidamente con el tamaño del número. Así que si n es grande (digamos, un centenar de dígitos), será difícil o imposible encontrar los suficientes z para que el algoritmo funcione. La ventaja de la criba general del cuerpo de números es que se necesita únicamente buscar números lismo del orden de n^1/d para algún entero positivo d (típicamente 3 o 5), a diferencia del orden n que es requerido aquí.

división por tentativa es el algoritmo de factorización de enteros más sencillo y fácil de entender.

Descripción

Dado un entero compuesto n (a lo largo de este artículo, n será «el entero a factorizar»), la división por tentativa consiste en intentar dividir n entre todo número primo menor o igual a √n. Si se encuentra un número que es divisor de n, en división entera, ese número es un factor de n.

Es posible determinar un límite para los factores primos. Supóngase que ${\displaystyle \scriptstyle P(i)}$ es el i-ésimo primo, de modo que ${\displaystyle \scriptstyle P(1)=2}$, ${\displaystyle \scriptstyle P(2)=3}$, ${\displaystyle \scriptstyle P(3)=5}$ etc. Entonces el valor del último número primo probado como un posible factor de n sería ${\displaystyle \scriptstyle P(i)}$ puesto que ${\displaystyle \scriptstyle P(i+1)^{2}>n}$; si fuese igual querría decir que ${\displaystyle \scriptstyle P(i+1)}$ es un factor. Aunque todo esto está muy bien, normalmente el inconveniente de inspeccionar un n concreto para determinar el valor correcto de i es más costoso que simplemente probar con el único candidato innecesario ${\displaystyle \scriptstyle P(i+1)}$ que estaría incluido en la tentativa con todos los ${\displaystyle \scriptstyle P(i)}$ tales que ${\displaystyle \scriptstyle P(i)\leq {\sqrt {n}}}$. Puede la raíz cuadrada de n ser entera, entonces es un factor y n es un cuadrado perfecto, pero no es esta una manera buena de encontrarlos.

La división por tentativa garantiza encontrar un factor de n, puesto que comprueba todos los factores primos posibles de n. Por tanto, si el algoritmo no encuentra ningún factor, es una prueba de que n es primo.

Complejidad computacional

En el peor caso, la división por tentativa es un algoritmo costoso. Si se empieza en 2 y se va subiendo hasta la raíz cuadrada de n, el algoritmo requiere

${\displaystyle \pi ({\sqrt {n}})\approx {2{\sqrt {n}} \over \ln n}}$

tentativas, donde ${\displaystyle \pi (x)}$ es la función contador de primos, el número de primos menores que x. En lo anterior no se ha tenido en cuenta la sobrecarga del test de primalidad para obtener los números primos candidatos a ser factores. Si se utiliza una variante sin el test de primalidad, sencillamente dividiendo por todo número impar menor que la raíz cuadrada de n, ya sea primo o no, puede llegar a necesitarse alrededor de

${\displaystyle {{\sqrt {n}} \over 2}}$

tentativas, que para un n grande es peor.

Esto significa que para un n con factores primos grandes de tamaños similares (como aquellos empleados en la criptografía asimétrica), la división por tentativa es computacionalmente impracticable.

Sin embargo, para un n con al menos un factor pequeño, la división por tentativa puede ser un método rápido para encontrar ese factor pequeño. Vale la pena percatarse de que para un n aleatorio, existe un 50% de probabilidad de que 2 sea un factor de n, un 33% de probabilidad de que 3 sea un factor, y así sucesivamente. Se puede observar que el 88% de todos los enteros positivos tiene un factor menor que 100, y que el 91% tiene un factor menor que 1000.

Definir el problema

Necesitamos construir una máquina que pueda responder preguntas sencillas de tipo sí/no. Dado un número entero n como entrada, ¿n es primo?

Pensemos en qué es lo que debería existir dentro de esta máquina para que funcione. Las máquinas solo pueden seguir una secuencia de pasos con base en algunas instrucciones, conocidas como un algoritmo. Para entrar en calor, vamos a averiguar cuál es el algoritmo que está dentro de tu cerebro. Responde la siguiente pregunta: ¿el 49 es primo?

…

¿No? ¿Cómo lo hiciste? Probablemente buscaste un divisor de 49 que fuera mayor que 1 y menor que 49. Si no has memorizado tus tablas de multiplicar, entonces naturalmente seguirías esta secuencia:

• ¿2 divide a 49?     NO
• ¿3 divide a 49?     NO
• ¿4 divide a 49?     NO
• ¿5 divide a 49?     NO
• ¿6 divide a 49?     NO
• ¿7 divide a 49?    SÍ

Encontramos un divisor de 49 (7), lo que prueba que 49 es un número compuesto.

Construir una pared

Sin embargo, ¿qué pasaría si te pregunto si 2971215073 es primo?

¿Todavía lo estás revisando? Después de las primeras mil revisiones, yo sigo sin encontrar un divisor. La pregunta clave es: ¿cuándo podemos dejar de revisar y probar que n es primo? (llamémosle a esto nuestra pared). Como punto de partida, sabemos que nuestra pared debe ser n-1 (ya que n divide a n). Si revisamos hasta 2971215072 encontramos un divisor (lo cual prueba que n es compuesto) O no lo encontramos (lo cual que prueba que n es primo).

Construir una mejor pared

Esto funcionaría, pero ¿podemos mover nuestra pared para ahorrar tiempo? Recuerda que en realidad estamos buscando el primer divisor (o el más pequeño). Algunas veces el divisor más pequeño podría ser 2, aunque también podría ser mucho más grande. Lo que nos lleva a la pregunta clave: ¿qué tan grande podría ser el divisor más pequeño?

Recuerda que cualquier entero compuesto n está hecho de dos o más primos n= P * P …

P es el más grande cuando n tiene exactamente dos divisores los cuáles son iguales entre sí. A esto se le conoce como número cuadrado como por ejemplo 9 (9 = 3*3) o 49 (49 = 7*7). Para considerar este peor escenario, ¡simplemente construimos nuestra pared en la raíz cuadrada de n!

Convéncete de esto: si no encontramos un divisor de n después de revisar hasta la raíz cuadrada de n, entonces n debe ser primo. Trata de probarlo por ti mismo (hay una prueba al final de este artículo).

Algoritmo de la división por tentativa

Eso es todo, ahora estamos listos para continuar. Primero, vamos a resumir nuestro algoritmo de la división por tentativa:

• Acepta un entero n como entrada.
• Para cada entero x en {2 ... sqrt(n)} revisa si x divide a n
• Si encuentras un divisor, entonces n es compuesto. DE LO CONTRARIO, n es primo.

Si tienes experiencia en programación, deberías abrir una libreta de CC e intentar hacer que esta función sirva. Si no, puedes ir al siguiente paso donde te proporciono una versión funcional que puedes usar como punto de partida. (Para tu información, es posible realizar esta lección sin hacer nada de programación).

https://es.khanacademy.org/computing/computer-science/cryptography/comp-number-theory/a/trial-division