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.
Две формулы по три оператора - что проще?