Всё уже придумано до нас. Усов, если вы думаете, что придумали что-то новое, то вы ошибаетесь, все это уже известно, просто вы плохо искали.

Придумал я как-то раз, как как можно добавить в сообщение контрольных битов, чтобы можно было не только обнаружить, что один из битов сообщения по дороге изменился, но и узнать какой именно, и исправить его. А оказалось, что Хэмминг придумал то же самое еще 50 лет назад.

Или вот тесты простоты и факторизация. Что делает тест Миллера-Рабина? Он фактически пытается убедиться в том, что порядок мультипликативной группы вычетов по модулю P делит P-1. По теореме о структуре конечной абелевой группы порядок любого элемента группы делит порядок группы. И если мы находим элемент, порядок которого не делит P-1 - значит число составное.
А можно, используя делители P-1, доказать простоту числа , не перебирая делители самого P.
И есть метод факторизации - p-1 метод Полларда - предполагая, что N=P*Q, пытаемся, перебрав все возможные делители P-1, получить единицу по модулю P.

Повторюсь, всё это базируется на мультипликативной группе вычетов по модулю P. А если взять другую группу?
Возьмем например матрицы 2х2. Умножение матриц не коммутативно, плохо, группа не абелева. Но можно выбрать коммутативную подгруппу. Например, для матриц вида где n фиксированное, умножение будет коммутативным: Если дополнительно потребовать, чтобы определитель такой матрицы был равен 1, получим уравнение Пелля , и решения этого уравнения можно умножать, получая новые решения - это как раз соответствует умножению таких матриц.

Ну вот у нас есть абелева группа решений уравнения Пелля. А давайте рассмотрим их по модулю простого числа P, и поинтересуемся порядком этой группы.
Оказывается, что если n квадратичный вычет по модулю P, то порядок этой группы равен P-1, а если n квадратичный невычет, то порядок равен P+1.
Первый случай неинтересен, такая группа изоморфна мультипликативной группе вычетов по модулю P. А вот случай невычета можно рассмотреть поподробнее.
Тут можно построить тест простоты по аналогии с Ферма: найдем n такое, что символ Якоби (n/P) был равен -1 и решение уравнения Пелля для этого n. Возведем это решение в степень P+1 по модулю P. Убедимся, что получили тривиальное решение (1,0).
Или даже аналог Миллера-Рабина: представим P+1 в виде 2 ^s d, d нечетно. Возводим начальное решение в степень d, и убеждаемся, что либо сразу получили (1,0), либо, после не более s возведений в квадрат, (-1,0).

И вот придумал я значит эту конструкцию, проверил, что работает, а потом посмотрел повнимательней - а оказалось, что Люка это уже больше ста лет назад придумал. Только описано оно у него немножко по другому - через последовательности Люка .
Последовательности Люка определяются как линейные рекуррентные последовательности V _n и U _n , параметризованные парой коэффициентов P, Q.
Но можно получить матричное представление: считаем дискриминант характеристического многочлена D = P*P - 4Q и подставляем в матрицу
Определитель этой матрицы равен Q, а возводя ее в степень n, получим V _n /2 и U _n /2 в первой строке. Сильный вариант теста как раз требует Q=1 - вот и уравнение Пелля.

И P+1 метод факторизации также можно описать через степени решений уравнения Пелля вместо последовательностей Люка.
Так что всё придумано до нас...

Gennadiy Usov1. А где написано, что числа Мерсенна определяет ещё какой-нибуть тест, кроме теста Люка-Лемера, да ещё с сопоставимой скоростью ?

2. Где написано, что можно БЕЗ ВЕРОЯТНОСТИ определять ВСЕ простые числа (с учётом мощности ПК)?

3. Где написано, что можно за менее 4-х раундов для каждого числа определять 50% ВСЕХ простых чисел (с учётом мощности ПК)?

1. Тест Люка-Лемера для простоты проверки 2 ^p -1 требует p-1 возведений в квадрат. Возведение в степень 2 ^p-1 -1 потребует p-2 возведений в квадрат плюс p-2 умножений, что минимум в два раза медленнее, а с учетом того, что возведение в квадрат быстрее, чем умножение произвольных чисел, более чем в два раза медленнее. Для поиска максимальных известных простых чисел это весьма существенно - там каждое число на обычном компьютере проверяется несколько месяцев.

2. Для математиков, пока вы строго математически не ДОКАЗАЛИ, что ваш алгоритм действительно это определяет, он не имеет никакого значения. А с практической точки зрения, для криптографических целей комбинация одного раунда Миллера-Рабина с тестом Люка достаточна.

3. Опять же, для математиков 50% простых - совсем не интересно. Либо вы доказываете теорему, которая выполняется для всех простых, либо это никому не нужно.

Вот на этих числах свой алгоритм проверьте: https://oeis.org/A074773

Вот еще хорошее число: 3825123056546413051

Gennadiy UsovВзял из вики описание теста Люка-Лемера и написал программу на Питоне.
На питоне? Да, хороший вариант для измерения скорости :)