Сколько простых представимо формой:

[Someone]

Немного поэкспериментировал. У меня Wolfram Mathematica 9. Четырёхъядерный процессор Intel Xeon 3 GHz.

Функция PrimeQ определяет, что число $10^{1000}-1769$ простое, за $0{,}156$ секунды. После этого я запустил ProvablePrimeQ с опцией "Certificate"→True. Пока считает. (Используется 25% времени процессора.) Попробую не выключать до утра, может быть, закончит.
Чтобы сильно не скучать, через некоторое время запустил с тем же числом программу Primo 3.0.9 (автор — Marcel Martin; сайт программы — https://www.ellipsa.eu/). Она тоже использует 25% времени процессора. Работу она закончила, затратив $25$ минут $42$ секунды. Размер файла, содержащего сертификат, составляет $119\,373$ байта и включает информацию о $151$ выполненном тесте, необходимую для проверки сертификата.

К сожалению, версия 3.0.9 программы Primo (вышла в декабре 2009 года), видимо, последняя, предназначенная для Windows. После этого автор перешёл на линукс. Последняя версия — 4.3.2. Про другие ОС он говорит, что версий Primo для них нет и не будет, так как он не желает платить за ОС. Ну, его право.

[Someone]

Продолжил эксперименты. Дело в том, что время проверки числа $10^{1000}-1769$ командой PrimeQ ($0{,}156$ секунды) заставляет думать, что используется пробное деление на малые простые числа плюс малая теорема Ферма, возможно, для нескольких оснований. Для сравнения я заставил программу PFGW64 версии 3.8.3 (сайт https://sourceforge.net/projects/openpfgw/; уже есть версия 4.0.1) искать простые числа вида $10^{1000}-n\cdot 2^{1000}\cdot 5^{47}+1$ в области $1\leqslant n\leqslant 10000$. Минут за 10–15 (точнее не заметил) она проверила весь диапазон и нашла 10 простых чисел. Командная строка выглядит так:
pfgw64.exe -f -tm -lLog.txt S.txt
где файл S.txt содержит две строчки:
ABC2 10^1000-$a*2^1000*5^47+1
a: from 1 to 10000
В файл Log.txt записывается протокол проверки:
Recognized ABC Sieve file:
Primality testing 10^1000-1*2^1000*5^47+1 [N-1, Brillhart-Lehmer-Selfridge]
factors: 3
10^1000-1*2^1000*5^47+1 is factored (0.0037s+0.0004s)
Primality testing 10^1000-2*2^1000*5^47+1 [N-1, Brillhart-Lehmer-Selfridge]
factors: 7^3
10^1000-2*2^1000*5^47+1 is factored (0.0037s+0.0004s)
Primality testing 10^1000-3*2^1000*5^47+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 3
10^1000-3*2^1000*5^47+1 is composite (0.0709s+0.0003s)
…
Числа, которые прошли тесты, но простоту которых доказать не удалось, записываются в файл pfgw.log (программа не может доказать простоту любого простого числа, она справляется только с числами специального вида, но для них используются очень эффективные методы). В данном случае таких не встретилось.
Числа, простота которых доказана, записываются в файл pfgw-prime.log:
10^1000-581*2^1000*5^47+1
10^1000-2033*2^1000*5^47+1
10^1000-2568*2^1000*5^47+1
10^1000-2700*2^1000*5^47+1
10^1000-2799*2^1000*5^47+1
10^1000-3380*2^1000*5^47+1
10^1000-5708*2^1000*5^47+1
10^1000-6177*2^1000*5^47+1
10^1000-7172*2^1000*5^47+1
10^1000-9750*2^1000*5^47+1
Вот как выглядит доказательство простоты в файле Log.txt:
…
Primality testing 10^1000-581*2^1000*5^47+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 7
Running N-1 test using base 11
Calling Brillhart-Lehmer-Selfridge with factored part 33.54%
10^1000-581*2^1000*5^47+1 is prime! (0.0995s+0.0058s)
…
Primality testing 10^1000-2033*2^1000*5^47+1 [N-1, Brillhart-Lehmer-Selfridge]
Running N-1 test using base 11
Calling Brillhart-Lehmer-Selfridge with factored part 33.45%
10^1000-2033*2^1000*5^47+1 is prime! (0.0709s+0.0054s)
…
Время доказательства даже меньше, чем у функции PrimeQ, но числа $10^{1000}-1769$ и $3+1036^{1036}$ не относятся к числам того вида, для которых есть быстрые алгоритмы. Программа PFGW с ними не справится.

[Someone]

Someone в сообщении #1444415 писал(а):

Функция PrimeQ определяет, что число $10^{1000}-1769$ простое, за $0{,}156$ секунды. После этого я запустил ProvablePrimeQ с опцией "Certificate"→True. Пока считает. (Используется 25% времени процессора.) Попробую не выключать до утра, может быть, закончит.

К моменту написания этого сообщения не закончила. Прошло уже несколько больше 12 часов, поэтому процесс останавливаю.

В общем, я не верю, что функция PrimeQ для столь больших чисел за столь короткое время даёт гарантированный результат, что число простое. Нужно понимать, что ошибки чрезвычайно редки, поэтому на уровне практической уверенности результату можно верить, но рассматривать его как доказательство нельзя.

[nnosipov]

Someone
Спасибо за проделанные эксперименты, это интересно. В Maple про isprime честно пишут, что применяется тест строгой псевдопростоты, и все ясно. А в Wolfram Mathematica сплошной туман. Впрочем, на это я уже жаловался.

[TR63]

Someone, спасибо.