Как работает метод Java BigInteger nextProbablePrime?

Question

Я работаю с Java BigInteger Class и мне интересно узнать об алгоритме метода nextProbablePrime.Я знаю о каком-то эффективном алгоритме тестирования простоты, таком как Miller-Rabin, но не уверен, какой алгоритм был реализован здесь.

Попробуем следующий код для хорошего времени и до сих пор нет ответа.

BigInteger number = BigInteger.ZERO;
number = number.setBit(82589933);
number = number.nextProbablePrime();

Answer 1

Я прошел с исходным кодом из BigInteger.Он внутренне использует алгоритм MillerRabin для метода nextProbablePrime.

Answer 2

Почему ваш пример работает и работает без возврата:

Ваш номер длиной 82 миллиона битов , и (по простому числу th) такие простые числа равны 82 миллионам / log_e (2) номера врозь.Итак, вы просите Миллера-Рабина протестировать около 15 миллионов кандидатов, причем каждый кандидат включает 82 миллиона бит, а каждая проверка нетривиальна.Так что да, даже такие эффективные алгоритмы, как Миллер-Рабин, потребуют времени на такие запредельно большие умы.

(Я помню, как однажды пробежал повышение одного числа до другого, слишком долго и жаловалсяразработчику языка, что они должны использовать повторное возведение в квадрат для более быстрого возведения в степень ... прежде чем я отступил и понял, что мой номер теста также содержит миллионы цифр.)