о простых числах

[l3xn]

Доброго дня!
Не знаю на тот ли форум я пришел или нет. Вопрос у меня про проверку на простоту больших чисел.
Предположим мне приснился сон, что число порядка 2 в степени несколько миллиардов плюс/минус еще какое-то число является простым. Запускаем вероятностный тест и спустя пару суток он показывает, что число простое. Обрадовавшись, запускаем истинный тест, предвкушая денежные премии за самое большое простое число...
Через 50 лет вспоминаем про наше число, ждем еще пару лет, когда закончится проверка. И вот собственно вопрос, а как вообще потом доказать, что,да, это число простое. "Мамой клянусь" - уверен, что не прокатит

[ИСН]

Истинный тест хоть и медленнее вероятностного, но всё-таки гораздо быстрее, чем полная факторизация.

[l3xn]

Про истинный тест согласен, что он побыстрее факторизации, но сколько он будет идти, если число будет состоять из миллиардов знаков?

[vpb]

ИСН в сообщении #1326121 писал(а):

а как вообще потом доказать, что,да, это число простое.

Думаю, что никак. Если компьютер правильно сработал, когда выполнял детерминистский тест, и не было ошибки в программе, то это и есть доказательство. (Замечание. Для простых чисел "общего вида" есть одни детерминистские тесты, а для специальных (чисел Мерсенна, скажем) --- другие, попроще. Но и те, и другие для больших чисел выполняются только с помощью компьютера.).

Впрочем, я не в курсе существующих достижений. Может быть (а вдруг ?), кто-нибудь когда-нибудь придумает простые числа еще более специального (нежели числа Мерсенна), вида, для которых возможно доказать простоту руками.

[Someone]

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

Полезную информацию можно найти здесь: http://primes.utm.edu/prove/index.html.

[victor.l]

А за простые числа больше чем два в миллионной степени блага не предусмотрены. Посчитал около десятка из спортивного интереса.

[grizzly]

victor.l в сообщении #1327082 писал(а):

А за простые числа больше чем два в миллионной степени блага не предусмотрены.

Да хоть за миллиарды.

[victor.l]

Я про миллионы спрашивал.