Добро пожаловать в форум, Guest  >>   Войти | Регистрация | Поиск | Правила | В избранное | Подписаться
Все форумы / Программирование Новый топик    Ответить
 Самый быстрый алгоритм для определения простых чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Эпиграф
mayton
Gennadiy Usov
mayton
Чем планируешь занятся в отсутствие шахмат?
А нет у меня шахмат
Ну я имею в виду тему... Направление. К примеру:
Криптография (актуально сейчас в эпоху bitcoins, darknet, tor).
...
Не обещаю что за эти темы назначены денежные бонусы. Но всё-же.
Я мог-бы просто поддежать или поучаствовать хотя-бы на уровне
энтузиаста. Не специалиста.
Сообщаю, что получен самый быстрый алгоритм для определения простых чисел Мерсенна
( и конечно, для определения простых чисел в окрестности чисел Мерсенна).
Обоснования алгоритма опубликованы в
http://sci-article.ru/stat.php?i=1573028225

Если коротенько, то
Пусть n – простое нечётное число.
Число Мерсенна Mn = 2^n – 1 будет простым тогда и только тогда,
когда (n – 1) член последовательности:
В(1) = 3
B(i) = (B (i - 1)*B(i - 1)) mod (Mn), 2 <= i <= n - 1
будет равен числу (Mn – 3):
B (n-1) = Mn – 3.


В результате получился эвристический алгоритм, похожий на алгоритм теста Люка-Лемера, а отличающийся тем, что в эвристическом алгоритме отсутствует операция вычитания числа 2 на каждом шаге.
Проведённые тестовые расчёты на ЭВМ показали, что эвристический алгоритм определяет простые числа Мерсенна в среднем на 2% быстрее, чем определяет простые числа тест Люка-Лемера.

Спасибо всем, кто меня критиковал при работе над этой задачкой!
Буду признателен за обсуждение полученного алгоритма.
7 ноя 19, 12:57    [22011445]     Ответить | Цитировать Сообщить модератору
 Re: Самый быстрый алгоритм для определения простых чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
И тут же уточнение в 22011445:

Следует читать:
Пусть n – нечётное число.

В статье исправил.
7 ноя 19, 13:48    [22011488]     Ответить | Цитировать Сообщить модератору
 Re: Самый быстрый алгоритм для определения простых чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
Идёт работа над ошибками:

В(1) = 9

либо

В(1) = 3
B(i) = (B (i - 1)*B(i - 1)) mod (Mn), 2 <= i <= n

Первый вариант предпочтительнее, с точки зрения сравнения с тестом Люка-Лемера
7 ноя 19, 18:47    [22011846]     Ответить | Цитировать Сообщить модератору
 Re: Самый быстрый алгоритм для определения простых чисел Мерсенна  [new]
exp98
Member

Откуда:
Сообщений: 1846
Gennadiy Usov
Идёт работа над ошибками
Каждая исправленная ошибка -- последняя.
7 ноя 19, 22:30    [22011957]     Ответить | Цитировать Сообщить модератору
 Re: Самый быстрый алгоритм для определения простых чисел Мерсенна  [new]
Gennadiy Usov
Member

Откуда:
Сообщений: 1840
После проведённых исследований немного расширил статью (это не ошибка - для любителей статистики).

Рабочие диапазоны для чисел Mn рассматриваются не с шагом 4, а с шагом 2.
Показаны рабочие диапазоны для малых чисел Mn с количеством простых чисел,
определённых эвристическим алгоритмом.
11 ноя 19, 07:44    [22013215]     Ответить | Цитировать Сообщить модератору
 Re: Самый быстрый алгоритм для определения простых чисел Мерсенна  [new]
exp98
Member

Откуда:
Сообщений: 1846
Gennadiy Usov
(это не ошибка - для любителей статистики).
Конечно-конечно, благодаря известной мелкомягкой фирме мы все уже неск. десятков лет знаем, что "это не ошибка программы, а её особенность".
16 ноя 19, 23:46    [22018011]     Ответить | Цитировать Сообщить модератору
Все форумы / Программирование Ответить