Ещё раз взглянул на сообщение 21976045 и подумал,
а почему бы не создать отдельный топик по решению сверх-задачи, которую поставил mayton.

Попробую эту сверх-задачу ещё раз сформулировать:
maytonДавайте поставлю сверх-задачу.

Пускай задана максимально-известная prime-константа Мерсенна (Хи-мерсенна).


На каком расстоянии от Хи-Мерсенна находится следующее простое число?
Ясно, что на своих ПК мы не сможем (пока) «искать простоту» вблизи таких больших чисел.

Остаётся отрабатывать наши действия на меньших числах,
и, если получится, распространить эти действия на большие числа
(это ещё называется построением эвристического алгоритма).

Можно искать следующее простое число за , двумя способами:
- искать следующее простое число Мерсенна;
- искать следующее простое число, следующее за этим число Мерсенна.
Если для первого варианта есть тест Люка-Лемера, то для второго варианта теста простоты пока нет

Конечно, тесты простоты есть. Но с учётом того, что по этим тестам простоты нужно провести очень большое количество раундов, связанных с возведением в большую степень (в тесте Люка-Лемера только возведение в квадрат), то времени на поиск очередного простого числа потребуется во много раз больше, чем для теста Люка-Лемера.

Остаётся найти другой тест для поиска простых чисел в окрестности чисел Мерсенна, по скорости сравнимого с тестом Люка-Лемера.

maytonНам следует оставить бесполезные Попытки просто искать числа. В районе сверхбольших.
Вычислительная сложность такова что наших машин не хватит.
Давай откатывать гипотезы на малых числах которые хотя бы быстро вычислимы.Конечно, сначала проверка гипотез будет на малых числах,
и если гипотеза работает,
то, согласно эвристике, можно гипотезу в виде алгоритма распространить на большие числа.

Немного о тесте Люка-Лемера.
Как известно, числа Мерсенна получили известность благодаря тесту простоты Люка-Лемера.
Однако тест Люка-Лемера может проверять только числа из последовательности Мерсенна.
Другие большие числа этот тест не рассматривает.
Все остальные известные тесты простоты не могут в разумное время определить простоту больших чисел,
поскольку такие тесты включают в себя объём вычислений, намного больший, чем объём вычислений теста Люка-Лемера.

При определении простоты числа тест простоты Люка-Лемера формирует
последовательность чисел из (n – 2) остатков по модулю квадратов чисел, меньших n.
После того, как последовательность сформирована, оценивается последний элемент последовательности.
Если последний элемент равен числу 0, тогда число Mn простое.
Если последний элемент не равен числу 0, тогда число Mn составное.
В тесте Люка-Лемера не применяется формула Ферма, в отличие от большинства тестов простоты.
Это является преимуществом теста по быстроте.

Поэтому, если разрабатывать новый алгоритм,
то его быстродействие должно сравниться с быстродействием теста Люка-Лемера.

В эвристическом алгоритме для числа n одним из основных элементов является число d.

Появляется соблазн "сформировать" очень большие числа следующим образом.
Выбирается очень большое число 2^m, и уже для этого числа «подбирается» число d. Таким образом, получается число
2^m * d + 1

Такие числа уже рассматривались.
Они называются числами Прота.
https://ru.wikipedia.org/wiki/Число_Прота
Для проверки таких чисел на простоту существует теорема Прота
https://ru.wikipedia.org/wiki/Теорема_Прота
Данная теорема Прота является вероятностным тестом простоты.

Самым большим известным простым числом Прота является число 10223*2^31172165 + 1 ,
которое является крупнейшим известным простым числом, не являющимся числом Мерсенна.

Были проверены числа Прота на небольших числах m.
Можно для каждого значения m определить минимальное значение d.

Появилась ещё одна статья.
http://sci-article.ru/stat.php?i=1569407195

Если коротко, то
получен эвристический алгоритм для определения простых чисел Мерсенна Mn .

Составлена на Python программа с применением эвристического алгоритма по определению простых чисел Мерсенна.

Время работы такой программы сопоставимо со временем работы программы теста Люка-Лемера.

Получается, что
время определения (n – 2) квадратов чисел, меньших Mn, в виде остатков по модулю Mn
почти равно времени определения остатка по модулю Mn для числа
a^((Mn – 1)/2)
В статье рассмотрено число a = 3. Показаны возможности других оснований степени.

В отличие от теста Люка-Лемера
данный эвристический алгоритм определяет простые числа Mnk = 2^n - 1 + 4*k, где k - натуральное число.

Программа на Python подтвердила эти расчёты для n < 60 и для шагов 1 <= k <= 25.

AklinGennadiy Usov,
продолжайте наблюдения.Дальнейшие наблюдения уже почти не нужны.

1. Получен эвристический алгоритм определения всех простых чисел (проверено на диапазоне от 5 до 250 000 000) (новизна).

2. Получена последовательность простых чисел, состоящая из 50% всех простых чисел. При этом для каждого проверяемого числа достаточно 3-х раундов вычислений (новизна).

3. Получен эвристический алгоритм определения простых чисел Мерсенна, сопоставимый по времени работы с тестом Люка-Лемера.

4. Данный эвристический алгоритм можно применять для определения простых чисел в окрестности чисел Мерсенна (новизна).

maytonRange Primes Found(Usoff) Primes Found(JDK::BigInteger) Primes (theoretical) Elapsed time(s) Average Speed (primes/sec)2 - 10024002^200 + 1 - 2^200 + 1 + 1 000 0007134611892^500 + 1 - 2^500 + 1 + 200 00057622882^1024 + 1 - 2^1024 + 1 + 200 0002818352^2048 + 1 - 2^2048 + 1 + 100 000782722^4096 + 1 - 2^4096 + 1 + 50 00022950И что даёт таблица?

Не стал много считать на своём стареньком ПК, поэтому только один час:

2019-10-07-09.53.54
-простое- 1760 -s- 5
-простое- 7226 -s- 1
-простое- 7422 -s- 1
-простое- 10092 -s- 2
-простое- 10472 -s- 3
-проверка чисел от - 2^4096 + 1 -дистанция - 11000
-количество простых чисел- 5
-количество раундов - 5687
-минимальное количество раундов для числа - 1
-количество минимальных раундов - 5495
-максимальное количество раундов для числа - 38
-количество максимальных раундов - 190
-остаток- 2
2019-10-07-10.54.48

Программа практически сразу определяет составное число.

fkthatGennadiy Usovпроверено на диапазоне от 5 до 250 000 000250 лямов это даже до 32 бит не дотягивает. Ты вот сгенери простое число битов так хотя бы на 256. А зачем так мало? 256?

Уж лучше 500, 1500, 2500,...

В работе
http://sci-article.ru/stat.php?i=1569407195

показаны последовательности простых чисел, в которых есть следующие простые числа:

2^2370 - 1 + 4
2^2648 - 1 + 8
2^1661 - 1 + 12
2^2772 - 1 + 16
2^2810 - 1 + 20

Тут появилась одна задачка:

Пусть имеется выражение:

a mod(b)

Если в данном случае b = c + d,

то как можно представить первоначальное выражение через mod(b) и mod(c),
или через их комбинацию?

Исправляю предыдущее сообщение:

то как можно представить первоначальное выражение через mod(d) и mod(c),
или через их комбинацию?

maytonИли ты имел в виду дистрибутивность операции mod?Да.

Может быть можно получить функцию вида

x mod(c) +- y mod(d) +- (что-то),

или другие опперации?

BarlonemaytonДля умножения что-то подобное было. Или для возведения в степень. Я думаю если Барлон заскочет
в топик - то он прояснит. Вроде скилованный парень в этих кольцах и модулях.Для умножения. Китайская теорема об остатках.Получается, что есть формулы только для умножения, а для сложения формул нет.

exp98Gennadiy UsovДа. Может быть можно получить функцию вида
x mod(c) +- y mod(d) +- (что-то), или другие опперации? Вопрос странный. Формулу вида x mod(c) +- y mod(d) +- (что-то) получитьможно всегда.
Надо тщательнЕе расставлять скобки, а то догадки разбегаются как тараканы:
b (mod x) = c + (d (mod x))
b (mod x) = (c + d)(mod x)
b (mod x) = c(mod x) + d (mod x)
((c + d)(mod x))(mod x)
Здесь только один вариант верен для натуральных в общем случае.
А вообще, найти опровергающие примеры было в тягость, школьная арифметика, не царское это дело.Здесь надо было связать сообщение с предыдущим сообщением:

Если есть
a mod (x+y),
то можно ли это выражение разложить на
a1 (mod x) и a2 (mod y)?

Нашел для Питона распечатку программы pow:
http://qaru.site/questions/132239/how-did-python-implement-the-built-in-function-pow




Это самая быстрая программа для Питона для pow?

maytonУбежден что Геннадия ведет какая-то интуиция. И она ему подсказывает искать формулы
ускоренного сложения чисел по модулю. Очевидно что за этим стоит некая оптимизационная
цель.Расчёты на ПК по определению простых чисел Мерсенна показали, что практически за одно и тоже время определяют простые числа Мерсенна
как тест Люка-Лемера, так и эвристический алгоритм (одна формула вида pow).

Поэтому ставится задачка:

доработать алгоритм для процедуры pow таким образом, чтобы эвристический алгоритм при определении простых чисел Мерсенна работал быстрее, чем тест Люка-Лемера.maytonЕсли мы упрёмся именно в процессорные ресурсы для умножения
или деления то можно подключать к питону библиотечки-ускорители.
Но об этом еще рано говорить IMHO. Мы же не делаем новый стандарт несимметричного шифра.
Мы - экспериментируем.Скорее всего, подключение библиотечек-ускорителей мало что даст.

Ведь идёт поиск алгоритма для программы, а не поиск самой программы.

На каждом компьютере и в каждой среде на нём будет своя скорость расчёта простых чисел.
И в каждой среде будут, скорее всего, такие же ускорители.

Если сравнивать тест Люка-Лемера и процедуру типа pow для чисел Мерсенна Mn, то оказывается, что :
- в каждом тесте количество циклов равно n;
- в каждом тесте в цикле идет умножение х = х*х;
- в тесте Люка-Лемера от числа х отнимается 2 для каждого элемента цикла;
- в pow число х умножается на предыдущее число (number) для каждого элемента цикла;
- и после каждой операции идёт операция %.

Данные рассуждения говорят о том, что скорости работы теста Люка-Лемера и процедуры pow почти равны,
о чём уже говорилось на топике по результатам работы прораммы.

maytonА асимптоматику надо считать.В данном топике рассматривается задачка
построения алгоритма для определения очень больших простых чисел,
например, простых чисел Мерсенна, простых чисел, расположенных недалеко от чисел Мерсенна.

Программа на ПК показала, что эвристический алгоритм 21980061 (одна формула) показывает результаты,
сравнимые с результатами работы теста Люка-Лемера:
- количество и перечень простых чисел Mn , время работы.
Проверено до n = 20000 (далее - ПК очень долго считает).

Как быть здесь с асимптоматикой?

maytonЕсли полином то хорошо.Алгоритм для pow - полином?

Сравнил pow из 21995132 и оказалось,
что этот алгоитм работает в два раза медленнее pow из стандартной библиотеки Питона.

Может быть есть ещё алгоритм для pow?

BarloneВот pow из питона https://github.com/python/cpython/blob/master/Objects/longobject.c#L4243
а тут gmp https://gmplib.org/repo/gmp/file/tip/mpn/generic/powm.c Если это питон, то почему скобки {?

Немного отдохнул, и решил сравнить два теста: тест Люка-Лемера и эвристический алгоритм 21980061 .

Составил две программы на Питоне и выбрал интервал чисел Мерсенна от 11 до 5000 без применения делителей с шагом 2.

Получились следующие результаты:
для теста Люка-Лемера определение простых чисел Мерсенна шло 14 мин. 05 сек.

Для эвристического алгоритма определение простых чисел Мерсенна шло 13 мин. 20 сек.

То есть, эвристический алгоритм «работает» на 5% быстрее, чем тест Люка-Лемера.

Таким образом, получен самый быстрый алгоритм для определения простых чисел Мерсенна – эвристический алгоритм.

mayton5% это слишком мало. Это можно списать на погрешность
- Оптимизатора Python
- Недостатки твоей реализации.

Вообще интересно было-бы рассматривать 1000% и больше. Этож криптография мать ее так.
Полумеры нам не нужны.

Уж если бахнуть так бахнуть.И там и там - Python.
Две формулы по три оператора - что проще?

Однако, 5% - это хорошее подспорье.

При 20 часах работы ПК экомится 1 час работы!
(или вместо 20 чисел можно проверить 21 число за то же время.)

maytonДля крипто-задач я думаю комиссия смотрела-бы не на 5% а на какие-то другие технологические поинты.Просто так отказаться от алгоритма, который считает на 5% быстрее?
Всего-то: каких-то 3 оператора меняются на 3 других оператора.

Такое бывает?

BarloneGennadiy UsovИ там и там - Python.
Две формулы по три оператора - что проще?pow в питоне - встроенная функция, написанная на С. А реализация на питоне в два раза медленнее. Так что сравнение нечестное. На самом деле, тест Миллера-Рабина для чисел Мерсенна должен быть в два раза медленнее Люка, потому что умножений надо в два раза больше.Две программы написаны на питоне.

Эта часть программы для эвристического алгоритма

Эта часть программы для теста Люка-Лемера

И где нечестное сравнение?