Разница между BigInteger.probablePrime () и другими алгоритмами простоты в Java

Question

Я реализую программу шифрования RSA с использованием Java. Прямо сейчас я использую BigInteger.probablePrime(1024, rnd), чтобы получить простые числа. Здесь rnd - случайное число, сгенерированное Random rnd = new Random(). Мне нужно проверить различные скорости шифрования.

Мои вопросы:

1. Какой алгоритм использует BigInteger.probablePrime(1024, rnd)?

2. В чем разница между алгоритмом выше и другими алгоритмами: например, Рабин-Миллер, Фермац, Лукас-Лемер?

Спасибо.

Answer 1

BigInteger вероятные простые методы используют алгоритмы Миллера-Рабина и Лукаса-Лемера для проверки простоты.

См. Внутренний метод BigInteger.primeToCertainty.

Answer 2

Исходный код Java доступен для скачивания, так что вы можете посмотреть его самостоятельно. Вот код для 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));
}

Фактические тесты содержатся в методах smallPrime() и largePrime(), которые следуют непосредственно в исходном коде.