2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


Посмотреть правила форума



Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Сколько простых представимо формой:
Сообщение12.03.2020, 00:06 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Немного поэкспериментировал. У меня 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 для них нет и не будет, так как он не желает платить за ОС. Ну, его право.

 Профиль  
                  
 
 Re: Сколько простых представимо формой:
Сообщение12.03.2020, 02:35 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Продолжил эксперименты. Дело в том, что время проверки числа $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 с ними не справится.

 Профиль  
                  
 
 Re: Сколько простых представимо формой:
Сообщение12.03.2020, 13:18 
Заслуженный участник
Аватара пользователя


23/07/05
17973
Москва
Someone в сообщении #1444415 писал(а):
Функция PrimeQ определяет, что число $10^{1000}-1769$ простое, за $0{,}156$ секунды. После этого я запустил ProvablePrimeQ с опцией "Certificate"→True. Пока считает. (Используется 25% времени процессора.) Попробую не выключать до утра, может быть, закончит.
К моменту написания этого сообщения не закончила. Прошло уже несколько больше 12 часов, поэтому процесс останавливаю.

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

 Профиль  
                  
 
 Re: Сколько простых представимо формой:
Сообщение12.03.2020, 13:29 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Сколько простых представимо формой:
Сообщение12.03.2020, 15:08 


03/03/12
1380
Someone, спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group