Sabemos que un número primo al que llamaremos `N` es un número que solo es divisible por `1` y por si mismo. Lo que queremos hacer es factorizarlo, por lo tanto podemos decir que `N=p*q // N in bbb "N"` sin importar el valor de N para este ejemplo. Pongamoslo de esta manera, para poder buscar que múltiplos son. Supongamos que hacemos una multiplicacion de `g*g*g*g*g*g...` hasta `r` veces, entonces podemos decir que `g^r=mN+1` (sabemos que encontraremos un multiplo de N).

Para comenzar a intuir que valor es `N` lo hay que hacer es `g^x/N` y cuando el resto sea `1` podremos expresarlo como `g^x=mN+1`, y ahora la `x` sabemos que es `r`, por lo tanto, `g^r=mN+1` cambiando de lugar un poco los valores queda `g^r-1=mN`, teniendo en cuenta de que `r` es par (caso contrario repetimos el proceso de buscar algun otro `g // g=[1,N-1] ^^ g in bbb "N"`), la formula que nos queda es

`(g^(r/2)-1)*(g^(r/2)+1)=mN`

Ahora como sabemos que `p` y `q` estan en el lado derecho de la ecuación, tambien lo estaran del lado izquierdo. Entonces con `(g^(r/2)-1)` y `(g^(r/2)+1)`, utilizando el algoritmo de Euclides podemos encontrar `p` y `q`.

Para hallarlo hacemos `(g^(r/2)-1) / N` esto nos dara un resto que llamaremos `R`, luego tendremos que hacer `R / N` esto nos dara otro resto entonces el resto anterior lo dividimos por el último resto que nos dió, y asi hasta que el resto `R` sea `0`. El último divisor sera un factor de `N`.

En resumen podemos definir este metodo de la siguiente manera:

• `1)` Buscamos un `g< N`, que no comparta factores con `N`
• `2)` Hallar `r` para que `g^r=mN+1`
• `3)` Si `r` es par calcula `(g^(r/2)-1)` y `(g^(r/2)+1)`. Si `r` es impar volvé al paso `1`
• `4)` Usá el algoritmo de Euclides para hallar el divisor común más grande

Ahora dejaré código escrito en Typescript para que veas cómo podes pasarlo a un programa de la misma manera, ¡podrías hacerlo en cualquier otro lenguaje!

                    
                        
function random(max: number): number {
    return Math.floor(Math.random() * (max - 1) + 1)
}

function getG(n: number): number {
    let g: number = random(n)
    while (n % g === 0) {
        g = random(n)
    }
    return g
}

function findR(g: number, n: number): number {
    let r: number = 1
    while ((Math.pow(g, r)) % n !== 1) {
        ++r
    }
    return r
}

function euclidesAlgorithm(
    n: number, 
    g: number, 
    r: number
    ): number[] {
    let w = Math.pow(g, r/2) + 1
    let s = Math.pow(g, r/2) - 1

    let first_factor: number = n;
    let second_factor: number = n;

    let first_remainder: number = w % first_factor
    w = first_factor % first_remainder
    first_factor = first_remainder % w

    let second_reminder: number = s % second_factor
    s = second_factor % second_reminder
    second_factor = second_reminder % s
    
    return [first_factor, second_factor]
}

function factorizePrime(n: number): number[] {
    let g: number = getG(n)
    let r: number = findR(g, n)

    while (r % 2 !== 0) {
       g = getG(n)
       r = findR(g, n) 
    }

    return algoritmoEuclides(n, g, r)
}

console.log(factorizePrime(77))
                    
                

Genial ya sabés factorizar un número primo. Esta es la base de la criptografía RSA, que es un sistema de criptografía asimétrica. Si te interesa saber más sobre este tema te recomiendo que le heches un vistazo a la siguiente lectura: Public-Key Cryptography and the RSA Algorithm .

Si te gustó este artículo, no dudes en compartirlo, y si tenés alguna duda o sugerencia no dudes en contactarme por Twitter.

¡Nos vemos la próxima!