java - mkyong - Diferencia entre BigInteger.probablePrime() y otros algoritmos de primalidad

rsa java example

Question

Estoy implementando un programa de encriptación RSA. En este momento estoy usando BigInteger.probablePrime(1024, rnd) donde rnd es un número aleatorio generado por Random rnd = new Random() para obtener números primos. Necesito probar varias velocidades de encriptación. Mi pregunta es qué algoritmo usa BigInteger.probablePrime(1024, rnd) ? y ¿cuál es la diferencia entre eso y usar algún otro algoritmo como Rabin-Miller, Fermats, Lucas-Lehmer? Gracias.

Answer 1

Los métodos principales probables de BigInteger usan los algoritmos Miller-Rabin y Lucas-Lehmer para probar la primalidad.

Vea el método interno BigInteger.primeToCertainty .

Answer 2

El código fuente de Java está disponible para su descarga, por lo que puede verlo usted mismo. Aquí está el código para BigInteger.probablePrime(int, Random) :

public static BigInteger probablePrime(int bitLength, Random rnd) {

    if (bitLength < 2)
        throw new ArithmeticException("bitLength < 2");

    // The cutoff of 95 was chosen empirically for best performance

    return (bitLength < SMALL_PRIME_THRESHOLD ?
            smallPrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd) :
            largePrime(bitLength, DEFAULT_PRIME_CERTAINTY, rnd));
}

Las pruebas reales están contenidas en los smallPrime() y largePrime() , que siguen directamente en el código fuente.