Как получать большие простые числа?

Дмитрий40

Alexu007 писал(а):Source of the post Просто принцип решета Эрастофена: задаём фиксированный массив и начинаем вычёркивать из него всё, что делится на 3, потом на 5, 7. Девятку не проверяем, т.к. она уже вычеркнута делением на 3 - и так далее до корня из размера массива. И, как я понимаю, нельзя начать проверку с любого числа - сперва решето нужно заполнить с начала. Что тут можно сэкономить?

Нет, можно начать с любого числа, я же уже говорил. Просто надо будет выяснить остаток от деления этого начального числа на каждое известное простое - это и будет смещением в массиве следующего кратного этому простому составного числа. Ну а дальше как обычное решето. Надо лишь предварительно посчитать все простые числа не превосходящие $\sqrt{N}$ (начального числа). Если проверяемый интервал не бесконечный, то можно ещё упростить и найти простые сразу до квадратного корня из конца интервала.

Gassa · Сообщение **Gassa** » 12 авг 2014, 20:39

Дмитрий40 писал(а):Source of the post
omega писал(а):Source of the post
Дмитрий40 писал(а):Source of the post И для каждого теста существуют "псевдопростые" числа, на которых он гарантированно ошибается...
Примеры приведите, пожалуйста. Голословные заявления ничего не доказывают.
Псевдопростое число.

Для (вероятностного) теста Миллера-Рабина не существует псевдопростых чисел.

Этот тест используется, например, в стандартной библиотеке языка Java для генерации больших простых чисел и проверки больших чисел на простоту (функции probablePrime, isProbablePrime, nextProbablePrime).

Дмитрий40

Третье же предложение по указанной Вами ссылке "Однако, с его помощью нельзя строго доказать простоту числа." - т.е. можно доказать что число составное, но вот что оно простое - не доказать. Это и можно назвать "псевдопростотой", т.е. скорее всего простое, но ... Если бы таких чисел не существовало в принципе, то тест был бы 100%, а это не так.
PS. Да, наверное с утверждением "гарантированно ошибается" я чуток перегнул палку. Но всё же такие числа есть, которое каждый из тестов ошибочно примет за простые.

Gassa · Сообщение **Gassa** » 12 авг 2014, 21:12

Дмитрий40 писал(а):Source of the post
Третье же предложение по указанной Вами ссылке "Однако, с его помощью нельзя строго доказать простоту числа." - т.е. можно доказать что число составное, но вот что оно простое - не доказать. Это и можно назвать "псевдопростотой", т.е. скорее всего простое, но ... Если бы таких чисел не существовало в принципе, то тест был бы 100%, а это не так.
PS. Да, наверное с утверждением "гарантированно ошибается" я чуток перегнул палку. Но всё же такие числа есть, которое каждый из тестов ошибочно примет за простые.

1. Не, псевдопростым всё-таки обычно называется - по вашей же на этот раз ссылке выше - составное число, которое какой-то тест ошибочно принимает за простое.

2. Оправдание использования вероятностных алгоритмов на практике довольно простое. Как только мы начинаем использовать реальный компьютер, а не идеальный алгоритм, появляется отличная от нуля вероятность аппаратной ошибки (например, нолик в произвольном месте памяти заменяется на единичку). Если вероятность ошибки нашего алгоритма меньше вероятности аппаратной ошибки, можно считать, что мы не сильно испортили общую вероятность неправильного ответа выбором алгоритма. Не могу найти ссылку, но, насколько я помню, что-то типа 2^{-50} считается приемлемой вероятностью ошибки в криптографии (там ведь тоже одна из распространённых задач - проверка числа на простоту).

3. Если, тем не менее, хочется теоретической строгости, у теста Миллера-Рабина есть невероятностная версия - тест Миллера (там же, ниже). Он, конечно, медленный по сравнению с вероятностной версией.

Дмитрий40

1. Простите, не понимаю. Если тест не принял число за составное - то оно считается простым, разве нет? Если оно на самом деле составное, то и моё и Ваше утверждение эквивалентны. А если простое - то тест и не ошибся.

2. Уели, факт. Про аппаратные ошибки я забыл. Теперь даже не соображу, двойной повтор теста (на разных компьютерах) с одинаковым результатом даёт 100% гарантию отсутствия ошибок или не даёт? Ведь разные ошибки не смогут компенсировать друг друга и привести к одинаковому результату? Или смогут? Пожалуй могут ...

3. Хм, и правда, есть, причём сложность не так уж велика кажется. Но решету, пока оно влезает в память, всё равно не конкурент, до чисел 10^15 оно тратит меньше 10-ти тактов процессора на каждое проверяемое число. И меньше 40-ка тактов для чисел 10^18. Вот для больших чисел, когда решето тормозит и в память не влезает, да, интересно.

Собственно я вовсе не против вероятностных тестов, они великолепны. Но имхо не для длинных серий чисел. Очень длинных. Вон среди 800 триллионов чисел не найдено 15-ти штук нужных.

Gassa · Сообщение **Gassa** » 12 авг 2014, 22:59

Дмитрий40 писал(а):Source of the post
1. Простите, не понимаю. Если тест не принял число за составное - то оно считается простым, разве нет? Если оно на самом деле составное, то и моё и Ваше утверждение эквивалентны. А если простое - то тест и не ошибся.

Это я запутался в терминологии, прошу прощения.

Я имел в виду strong pseudoprime — сильно псевдопростые числа, то есть составные числа, которые для любого числа-свидетеля в некотором тесте притворяются простыми.

Например, для теста Ферма псевдопростые числа имеют собственное название — числа Кармайкла. Минимальное из них — число $$561$$

. Для любого выбора $$a$$

, взаимно простого с $$561$$

, в тесте Ферма будет верно проверяемое утверждение $a^{560} = 1 \mod 561$ . Однако $561 = 3 \cdot 11 \cdot 17$ — не простое число.

Так вот моё утверждение состояло в том, что для теста Миллера-Рабина не существует сильно псевдопростых чисел.

Alexu007 · Сообщение **Alexu007** » 13 авг 2014, 08:53

[quote=N T в t145375 (deleted)]
omega зачем-то хочет всё свести к публикации статистики - наверное это Alexu007 и имел в виду под мутью.
[/quote]
Мутит - в смысле что-то там непонятное в этих цифрах ищет.

yourdomain.com