Публикация научных статей.
Вход на сайт
E-mail:
Пароль:
Запомнить
Регистрация/
Забыли пароль?

Научные направления
Поделиться:
Статья опубликована в №76 (декабрь) 2019
Разделы: Математика
Размещена 07.11.2019. Последняя правка: 27.08.2021.
Просмотров - 1949

Новый алгоритм для определения простых чисел Мерсенна и для определения простых чисел в окрестности чисел Мерсенна

Усов Геннадий Григорьевич

к.т.н.

МГУ, 1972

пенсионер

Аннотация:
Полученный в статье эвристический алгоритм работает несколько быстрее известного теста Люка-Лемера при определении простоты чисел Мерсенна. Данный эвристический алгоритм определяет простоту чисел, расположенных в некоторой окрестности чисел Мерсенна.


Abstract:
The heuristic algorithm obtained in article works somewhat faster than the well-known Luc-Lemer test in determining the simplicity of Mersenne numbers. This heuristic algorithm determines the simplicity of numbers located in some neighborhood of Mersenne numbers.


Ключевые слова:
эвристический алгоритм; простое число; тест простоты; число Мерсенна

Keywords:
algorithm; Prime number; simplicity test; Mersenne number


УДК 511

Введение

Одной из задач современной математики является задача поиска максимальных простых чисел.

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

Автором был разработан эвристический алгоритм для определения простых чисел Мерсенна [2]. Причем, тестовые расчеты на ЭВМ показали для этих двух тестов простоты схожие скорости определения простых чисел.

Теперь ставится задача о доработке эвристического алгоритма с целью улучшения его быстродействия работы по сравнению с быстродействием работы теста Люка–Лемера.

Актуальность

В настоящее время существует некоторый предел по определению простых чисел Мерсенна с применением теста Люка-Лемера с учетом существующих ЭВМ. Последнее найденное простое число Мерсенна 2^82589933-1.

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

Цели и задачи

Тест Люка-Лемера определяет для числа Мерсенна вида Mn = 2^n - 1 последовательность  (n – 1) чисел [1]:

S(1) = 4

S(i) = (S (i - 1)*S(i - 1) – 2) (mod Mn), 2 <= i <= (n - 1)

После определения последовательности чисел проверяется число S(n – 1).

Если это число равно 0, то число Mn будет простым числом.

Эвристический алгоритм для определения простых чисел Мерсенна имеет следующий вид [2]:

пусть n – натуральное число.

Число Мерсенна Mn = 2^n – 1 будет простым тогда и только тогда, когда выполняется условие:

a^d =  (Mn – 1) (mod Mn), где:                                                             (1)

d – нечётное число, равное (Mn  - 1)/2;

a = 3.

Ставится задача преобразовать выражение 3^d в последовательность операций, аналогичных тесту Люка-Лемера.

 

Выражение 3^d представляет собой произведение d чисел 3, где d – нечётное число.

Чтобы удобнее работать с данными числами при определении их произведения по mod (Mn), необходимо эти числа разложить попарно на блоки вида 3^d.

Однако удобнее раскладывать выражение 3^d попарно на блоки тогда, когда это выражение имеет чётное количество начальных блоков. Поэтому при раскладывании на блоки рассматривается следующее выражение:

3* 3^d= 3^(d+1) = 3^(Mn/2) = 3^d1, где d1 = Mn/2 = M(n-1)

Блок 3^d1  состоит из двух блоков:

3^d1  =  3^d2  * 3^d2, где d2 = d1 /2 =Mn/4 = M(n-2).

Блок 3^d2 состоит из двух блоков:

3^d2   = 3^d3  * 3^d3, где d3 = d2 /2 =Mn/8 = M(n-3).

Блок 3^d3 состоит из двух блоков:

3^d3   = 3^d4  * 3^d4, где d4 = d3/2 = Mn/16= M(n-4)

Данные разложения можно продолжить до тех пор, пока не будут определены блоки вида 3^1.

Теперь можно построить последовательность чисел, аналогичную последовательности чисел для теста Люка-Лемера. В этом случае получается последовательность из (n – 1) чисел:

В(1) = 9

B(i) = (B (i - 1) * B(i - 1)) (mod Mn), 2 <= i <= (n – 1).                             (2)

Поскольку вместо числа 3^d теперь в алгоритме будет число 3^(d+1), то меняется основное условие эвристического алгоритма для определения простоты числа:

3^d * 3 =  (Mn – 1)*3 (mod Mn), или

3^(Mn/2) = (Mn – 3) (mod Mn), или

3^M(n-1) = (Mn – 3) (mod Mn).                                                          (3)

Тогда условие для определения простых чисел Мерсенна с помощью эвристического алгоритма будет выглядеть следующим образом:

Пусть n –  нечётное число.

Число Мерсенна Mn = 2^n – 1 будет простым тогда и только тогда, когда (n – 1) член последовательности:

В(1) = 9

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

будет равен числу (Mn – 3):

B(n-1) = (Mn – 3).

 

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

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

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

 

Данный эвристический алгоритм можно ещё немного упростить.

Можно в виде первоначального числа В(1) назначать числа вида

3^(2^(p)), где 0 <= p <= P.                                                    (5)

Тогда количество элементов в последовательности чисел уменьшается на р. При этом немного уменьшается время работы алгоритма за счёт того, что не проводится несколько операций по (mod Mn) и операций сопровождения цикла для небольших чисел.

Кроме того, если рассматриваются несколько чисел Мерсенна, то уже посчитанное начальное число можно будет применить при проверке следующего числа.

Начальное число для каждого определяемого числа определяется как число 3^(2^(p)), немного большее, чем число Mn.

 

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

Последовательности чисел Mnk в окрестности чисел Мерсенна можно определить следующим образом:

Mnk = 2^n – 1+k, где n – целое число, k – целое число, кратное 2.

Поскольку появляются числа Mnk, то в целях единого обозначения можно числа Мерсенна Mn обозначать в виде Mn0.

Если число k отрицательное, например, k = -4, то последовательность чисел в окрестности чисел Мерсенна будет иметь вид Mn(-4).

Если имеется число Mnk, то эвристический алгоритм из [2], если определить а = 3, будет выглядеть следующим образом :

3^((Mnk-1)/2) =  D (mod Mnk), где                                                        (7)

D = Mnk – 1 или D = 1.

 

Рассмотрим случай, когда число k – положительное.

Подставим в это уравнение значение Mnk:

3^((2^n – 1+k -1)/2) =  D (mod Mnk), или

3^((2^n – 2)/2)* 3^(k /2) =  D (mod Mnk), или

3^(2^(n –1)- 1) (mod Mnk) * 3^(k /2) (mod Mnk) =  D (mod Mnk), или

3^M(n-1) (mod Mnk) * 3^((k /2)-1) (mod Mnk) =  D (mod Mnk).                   (8)

В результате получается эвристический алгоритм для определения простых чисел Mnk в окрестности чисел Мерсенна (для числа k – положительного, кратного 2) в виде следующих шагов:

шаг 1.  определяется значение эвристического алгоритма для простых чисел Мерсенна по (mod Mnk),

            А = 3^M(n-1) (mod Mnk)                                                                  (9)

шаг 2. определяется произведение числа А на значение произведения ( k/2-1) оснований степени 3 по (mod Mnk),

            В = (А * 3^((k /2)-1)) (mod Mnk)                                                       (10)

шаг 3. полученное произведение В сравниваются с величиной D:

            Если имеет место равенство B = D, то число Mnk – простое.                (11)

 

Рассмотрим случай, когда число k – отрицательное.

Подставим в это уравнение значение Mnk:

3^((2^n – 1+k -1)/2) =  D (mod Mnk), или

3^((2^n – 2)/2)* 3^(k /2) =  D (mod Mnk), или

3^(2^(n –1)-1) (mod Mnk) =  D (mod Mnk) * 3^(- k /2) (mod Mnk), или

3^M(n-1) (mod Mnk) =  (D * 3^(1-k /2)) (mod Mnk)                                       (12)

В результате получается эвристический алгоритм для определения простых чисел Mnk в окрестности чисел Мерсенна (для числа k – отрицательного, кратного 2) в виде следующих шагов:

шаг 1.  определяется значение эвристического алгоритма для простых чисел Мерсенна по (mod Mnk),

            А = 3^M(n-1) (mod Mnk)                                                               (13)

шаг 2. определяется произведение числа D на значение произведения (1 - k/2) оснований степени 3 по (mod Mnk),

            С = (D * 3^(1-k /2)) (mod Mnk)                                                       (14)

шаг 3. полученное число А сравнивается с полученным числом С:

            Если имеет место равенство А = С, то число Mnk – простое.             (15)

В обоих случаях числа k происходят вычисления и сравнение для двух вариантов числа D.

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

       

В работе [3] был рассмотрен тест Пепена, который определил необходимое и достаточное условие для определения простоты чисел вида Fk = 2^(2^k)+1 (числа Ферма):

при k >= 1 число Fk является простым тогда и только тогда, когда:

3^((Fk – 1 )/2) = Fk-1 (mod Fk).                                                        (16)

Следовательно, данный тест для определения простых чисел Ферма, а также определения простых чисел вида 2^k+1, подтверждает верность формулы эвристического алгоритма для определения простых чисел в окрестности чисел Мерсенна.

 

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

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

для  n = 7 расстояние  572 найдено простых чисел 95

для  n = 8 расстояние  444 найдено простых чисел 71

для  n = 9 расстояние  188 найдено простых чисел 29

для  n = 10 расстояние  514 найдено простых чисел 70

для  n = 11 расстояние  414 найдено простых чисел 55

для  n = 12 расстояние  862 найдено простых чисел 99

для  n = 13 расстояние  206 найдено простых чисел 23

для  n = 14 расстояние  144 найдено простых чисел 14

для  n = 15 расстояние  8270 найдено простых чисел 784

для  n = 16 расстояние  6502 найдено простых чисел 587

для  n = 17 расстояние  7406 найдено простых чисел 632

для  n = 18 расстояние  16074 найдено простых чисел 1296

для  n = 19 расстояние  6590 найдено простых чисел 508

для  n = 20 расстояние  2406 найдено простых чисел 170

для  n = 21 расстояние  16766 найдено простых чисел 1156

для  n = 22 расстояние  58074 найдено простых чисел 3799

для  n = 23 расстояние  17246 найдено простых чисел 1078

для  n = 24 расстояние  1662 найдено простых чисел 91

для  n = 25 расстояние  194 найдено простых чисел 10

для  n = 26 расстояние  25674 найдено простых чисел 1401

для  n = 27 расстояние  559490 найдено простых чисел 29966

для  n = 28 расстояние  70092 найдено простых чисел 3639                          (17)

Назовём эти расстояния рабочим диапазоном числа Mn для применения эвристического алгоритма.

Для чисел n, равных от 29 до 35, рабочий диапазон будет больше 600000, при этом было определено более 28000 простых чисел на каждом рабочем диапазоне.

При этом было замечено, что для чисел Mnk = Mn + 4 * t, t > 0 рабочий диапазон будет намного больше, чем для чисел Mnk = Mn + 2 + 4 * t, t > 0.

Аналогичная картина получается для определения рабочего диапазона для числа Mn в том случае, когда число k будет отрицательным.

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

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

Научная новизна

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

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

Оказалось, что в рамках рабочего диапазона чисел Мерсенна достаточно одной проверки чисел на простоту.

Библиографический список:

1. Василенко О. Н. Теоретико-числовые алгоритмы в криптографии, М.:МЦНМО, 2003- 328 c.
2. Усов Г.Г., Эвристический алгоритм для определения больших простых чисел в окрестности чисел Мерсенна. Электронный периодический рецензируемый научный журнал «SCI-ARTICLE.RU», №74 (октябрь) 2019, стр. 22-26. http://sci-article.ru/number/10_2019.pdf
3. Крэндалл Р., Померанс К. Простые числа: Криптографические и вычислительные аспекты. Пер. с англ. / Под ред. и с предисл. В. Н. Чубарикова. - М.: УРСС: Книжный дом




Рецензии:

18.01.2020, 12:18 Мирмович Эдуард Григорьевич
Рецензия: Автор продолжил работу в избранной области, хотя не очень понятно, почему он её не публикует в каких-то математических журналах типа "Квант". Желательно хотя бы в некоторых формулах приводить ниже по два-три конкретных примера как инструмент для представления читателем, что даёт каждая формула, привести хоть несколько оценок сравнения времени расчёта трёх моделей реализации предыдущих и предлагаемого эвристических алгоритмов. Однако автор сам выбирает и идейное наполнение своей работы, и контент. Надо расставить пробелы, где их нет (Word подскажет). Несмотря на то, что актуальность статья для рецензента под большим вопросом, преданность автора поиску упрощений в нахождении больших простых чисел и его компетентность в этой области дают рецензенту возможность рекомендовать эту работу к публикации после прииятия им решения - учитывать предложения рецензента или не учитывать.

19.01.2020 13:13 Ответ на рецензию автора Усов Геннадий Григорьевич:
Уважаемый Эдуард Григорьевич! Благодарю Вас за рецензию к моей статье. Если я публикуюсь в данном журнале, то, наверное, надо продолжать отдавать интересные материалы этому журналу. Эвристический алгоритм похож на алгоритм Люка-Лемера и отличается от него на 3 числа. В расчетах по этим алгоритмам для чисел Мерсенна на печать выходят одни и те же простые числа. Поэтому я не приводил примеров определения простых чисел Мерсенна с помощью эвристического алгоритма. Однако, когда я рассматривал числа в окрестности чисел Мерсенна, то привел результаты расчетов в виде количества определяемых простых чисел. Пробелы расставил. Спасибо за подсказку! А актуальность работы в том, что найден более быстрый алгоритм определения простых чисел Мерсенна. И пусть всего на чуть-чуть по времени.



Комментарии пользователей:

11.11.2019, 7:25 Усов Геннадий Григорьевич
Отзыв: В результате исследований была немного доработана статья. Числа в окрестности числа Mn рассматриваются не с шагом 4, а с шагом 2. Проведена оценка рабочих диапазонов для малых чисел Mn, где с помощью эвристического алгоритма определяются только простые числа. Немного отредактирована новизна работы и расширен библиографический список.


6.12.2019, 16:55 Усов Геннадий Григорьевич
Отзыв: В результате исследований была немного доработана статья. Добавлен 3-ий пункт научной новизны. В связи с публикацией представлена статья [2].


19.01.2020, 15:30 Мирмович Эдуард Григорьевич
Отзыв: Физическая миссия простых чисел не изучена, и нет уверенных надежд, что (кроме криптографии) этому будут посвящены серьёзные исследования в микро- и макрофизике. Даже в теории групп и представлений неприводимым многочленам (математическое обобщение простых чисел) уделено фундаментальное место, а простым числам - нет. Нет исследований и простых чисел в других, не десятичной, системах счисления. Успехов автору в его деятельности на пенсии. Справиться с текучкой и посвятить время для любимых занятий дорогого стоят.


19.01.2020, 16:55 Усов Геннадий Григорьевич
Отзыв: Спасибо за напутствие! Сейчас много свободного времени, и есть желание решать интересные задачи, на которые ранее не обращал внимание.


20.01.2020, 3:13 Мирмович Эдуард Григорьевич
Отзыв: Максимальное число электронов конечных элементов групп: n = 2, 8, 8, 18, 18, 32, 32... Всегда ли n - 1 - простое число? Решением каких диофантовых уравнений являются простые числа?Простые числа и фрактальная концепция. Стабильное состояние любого объекта должно быть гомеоморфным некому простому числу (хотелось бы). Устойчивость и простые числа (в приципе). Посмотрите адиковые числа. В общем, дерзайте.


20.01.2020, 13:08 Усов Геннадий Григорьевич
Отзыв: Уважаемый Эдуард Григорьевич! Спасибо Вам за перечень интересных тем по решения задач с применением простых чисел. В настоящее время я пробую варианты по факторизации чисел. В дальнейшем предполагаю заняться решением одной из задач, предложенных Вами. Если Вы не против, я попробую обратиться к Вам за разъяснениями по этой задаче по Вашей электронной почте, которая указана в настоящем журнале.


3.02.2020, 19:26 Усов Геннадий Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Задачей статьи был не поиск самого большого простого числа Мерсенна, а поиск быстрого алгоритма для такого поиска. На своем домашнем компьютере я определял простое число Мерсенна М-23209 с целью проверки алгоритма в разумное время - несколько часов. Очередные простые числа Мерсенна не имеет смысла искать на домашнем компьютере: самое большое простое число не определишь из-за нехватки времени рабочего состояния компьютера, а меньшие числа - уже известны. С уважением, Усов Геннадий Григорьевич


5.02.2020, 20:14 Усов Геннадий Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Числа Мерсенна имеют вид Mn = 2^n - 1, где n – целое число. Числа в окрестности чисел Мерсенна определяются следующим образом: Mnk = 2^n – 1 + k, где n – целое число, k – целое число, кратное 2. Некоторое количество чисел в окрестности чисел Мерсенна являются простыми числами.


6.02.2020, 18:28 Усов Геннадий Григорьевич
Отзыв: Уважаемый Вадим Григорьевич! Согласно определению: "эвристический алгоритм (эвристика) — алгоритм решения задачи, включающий практический метод, не являющийся гарантированно точным или оптимальным, но достаточный для решения поставленной задачи". Простота чисел в окрестности чисел Мерсенна была проверена на небольших значениях n и k с помощью простого перебора делителей. Результаты этих расчетов были представлены в статье. Следовательно, данный эвристический алгоритм можно распространить на большие значения числа n.


15.08.2021, 16:10 Цорин Борис Иосифович
Отзыв: Данная статья практически дублирует другую статью того же автора. Соответственно, ошибка в ней та же самая. Автор взял чужой вероятностный алгоритм (тест Миллера-Рабина), переименовал его в "эвристический алгоритм", и, не понимая смысла вероятности, сделал вывод, что раз на небольшом количестве проверенных чисел он работает, то и на других числах должен работать. Как вероятностный алгоритм, дающий верный результат в большинстве случаев, этот алгоритм не является достижением гражданина Усова, так как был известен задолго до его упражнений. Эвристическим же алгоритмом данный алгоритм не является. Алгоритм, дающий правильный ответ в большинстве случаев и совершенно неправильный в некоторых случаях, - вероятностный алгоритм. Алгоритм, дающий правильный ответ в некоторых случаях и очень близкий к правильному ответ в остальных случаях, - эвристический алгоритм. Вся статья, как и другие псевдоматематические статьи гражданина Усова, является смесью чужих результатов с демонстрацией непонимания гражданином Усовым основ математики.


17.08.2021, 18:20 Усов Геннадий Григорьевич
Отзыв: Гражданин Цорин! Вас не шокирует такое обращение? Ведь Вы же так ко мне обращаетесь? Удивлён Вашей работоспособностью. Пройтись катком по моим публикациям и камня на камне не оставить от этих работ. И ещё такое обвинение: «непонимания гражданином Усовым основ математики.» Простите, а Вы их понимаете, и понимаете ВСЕ основы? Простите, Вы также обучаете своих учеников по обращению к старшим по возрасту? (как мне кажется, я Вас старше). Кстати, одну мою статью забыли. Что-то непонятно в ней? Теперь по теме настоящей статьи. Вы обвиняете меня в: «Автор взял чужой вероятностный алгоритм (тест Миллера-Рабина), переименовал его в "эвристический алгоритм". Это надо доказывать. У меня алгоритм выделен жирным шрифтом. Приведите издание, где точно так же оформлен алгоритм (с точностью до параметра) определения числа Мерсенна. И ещё. «этот алгоритм не является достижением гражданина Усова, так как был известен задолго до его упражнений.» Приведите издание. Ваше слова гражданин …


18.08.2021, 10:01 Цорин Борис Иосифович
Отзыв: Гражданин Усов (до этого момента я использовал это не как обращение, но Вы сами пожелали), мне неинтересно, как Вы оформили то, что написали жирным шрифтом, так как это всего лишь Ваш вывод из уже совершенной Вами в работе [2] ошибки. Все, что я написал в предыдущем отзыве, является описанием вот этих строк: "Эвристический алгоритм для определения простых чисел Мерсенна имеет следующий вид [2]: пусть n – натуральное число. Число Мерсенна Mn = 2^n – 1 будет простым тогда и только тогда, когда выполняется условие: a^d = (Mn – 1) (mod Mn), где: d – нечётное число, равное (Mn - 1)/2; a = 3". Именно это - вероятностный тест Миллера-Рабина (только без "тогда"), который Вы решили переназвать в свой эвристический алгоритм. Все остальное читать даже смысла нет, так как добавлением этого "тогда" (то есть уверенности в том, что ответ будет верным всегда) Вы уже сделали неверным любой дальнейший вывод. Однако все, что Вы сделали дальше, - это провели простейшее и бесполезное преобразование формул теста Миллера-Рабина. Бесполезное потому, что возведение в степень все равно проводится через это преобразование. И, пожалуй, даже вредное, потому что Вы забыли один из двух случаев положительного результата теста Миллера-Рабина. "Издание" приводить не собираюсь, поскольку мы оцениваем смысл алгоритма, а не его оформления. Что тест Миллера-Рабина известен - Вы и сами знаете, остальное - Ваши ошибки и мартышкин труд, вперемешку.


18.08.2021, 12:00 Усов Геннадий Григорьевич
Отзыв: Гражданин Цорин! Раз Вы согласились с таким обращением, пусть будет так. Ранее Вы сказали, что: «я использовал это не как обращение,» А как Вы использовали – не уточнили. Значит, использовали как обращение. А по поводу тест Миллера-Рабина Вы додумываете. Тест Миллера-Рабина звучит так: Пусть n — простое число и (n – 1) = 2^s*d, где d — нечётно. Тогда для любого a из Zn выполняется хотя бы одно из условий: 1. a^d = 1 (mod n) 2. Существует целое число r < s такое что a^(2^r*d) = - 1 (mod n). А у меня :пусть n – натуральное число. Число Мерсенна Mn = 2^n – 1 будет простым тогда и только тогда, когда выполняется условие: a^d = (Mn – 1) (mod Mn), где: d – нечётное число, равное (Mn - 1)/2; a = 3". Разницу двух тестов видите?


18.08.2021, 19:02 Цорин Борис Иосифович
Отзыв: Разница двух тестов: Вы взяли вероятностный тест Миллера-Рабина, выбрали значение a=3, для самих чисел Мерсенна бездоказательно оставили одно условие из двух (хотя таким свойством при а=3, видимо, обладают все числа вида 12k+7, так что я не стал на это обращать внимания в предыдущих отзывах), так же бездоказательно (и, очевидно, недостаточно обоснованно даже для гипотезы) заявили, что равенство при одном значении - это не только необходимое, но и достаточное условие "в окрестности чисел Мерсенна". Все остальное - элементарные преобразования, не меняющие смысла теста. Таким образом, "Ваш алгоритм" - это тест Миллера-Рабина, к которому безосновательно добавлено утверждение достаточности проверяемого условия. И кстати, то, что Вы сейчас процитировали как тест Миллера-Рабина, это еще не сам тест, а теорема, на которой он основан.


19.08.2021, 8:12 Усов Геннадий Григорьевич
Отзыв: Тогда почему, говоря о тесте Миллера-Рабина, Вы не говорите о том, что он много взял от теста Ферма? И так с многими тестами, которые опираются на тест Ферма. Все что-то взяли либо от теста Ферма, либо друг от друга, добавили, разбавили, построили логическую цепочку, и много ещё чего. При этом вначале указали весь список, откуда брали, а потом тест пошел «гулять» с новым именем. В предыдущей работе я сослался на тест Миллера-Рабина. Кстати, а в чём смысл теста Миллера-Рабина, а также любого другого?


19.08.2021, 10:05 Цорин Борис Иосифович
Отзыв: Тест Миллера-Рабина много взял от теста Ферма, но дает более надежный результат: псевдопростых чисел по тесту Миллера-Рабина по любому основанию меньше, чем псевдопростых чисел Ферма по тому же основанию. "Ваш алгоритм" ни по своему результату, ни по сути алгоритма, ни по его сложности по времени или памяти не отличается от теста Миллера-Рабина, поэтому именно алгоритм Вашим результатом не является, это тот же самый алгоритм теста Миллера-Рабина. Вашими результатами можно считать иное. Все, что Вы сделали, это: {1a}. Сказали: "(Mn -1)/2 нечетно, поэтому к числам Мерсенна при применении теста Миллера-Рабина проверка производится только для r=0," - это верное утверждение, но оно тривиально и крайне малозначаще, так как не совершенствует сам тест, а только иллюстрирует его частный случай; на научный результат не тянет, это уровень разминочной задачи при изучении темы студентами. Впрочем, если Вы считаете это весомым научным результатом, я не буду вдаваться в полемику именно по этой части, мои основные возражения относятся к пункту {3}, который и Вы, судя по статье, считаете основным. {1b}. Предложили эквивалентно заменить возведение в положительную степень на возведение вычетов в отрицательную степень, что допустимо, но не уменьшает количество шагов, зато увеличивает время отдельного шага при возведении в степень. Это тем более не научный результат. {2}. Сказали: "Числа Мерсенна при прохождении теста Миллера-Рабина не могут дать 1, только -1". Это предположительно верное утверждение, но его надо доказать. Я могу дать более сильное утверждение: "3^(2a+1)=1 (mod 12k+7) неразрешимо в целых числах", - но доказать эту гипотезу я не смог. Если Вы сможете это доказать, то из этого легко вытекает Ваше утверждение: числа Mn имеют вид 12k+7, а числа (Mn-1)/2 вид 2a+1. Только не надо использовать Ваш любимый метод "перебрать несколько тысяч чисел и посмотреть, что будет", это не доказательство. Будет ли доказательство значимым научным результатом, я не знаю, доказательство общего утверждения - скорее всего, да. Если докажете, можете назвать Леммой Усова и на меня не ссылаться. {3}. Сказали: "Числа Мерсенна / числа вида Mn+4k при 0<=k<=25 не могут быть сильно псевдопростыми по основанию 3" (в данной работе - k<=48, число 25 я взял из другой Вашей работы). Это гипотеза, верность которой сомнительна, так как попытка найти опровержение осуществлялась на относительно небольшом множестве чисел. Доказательство же ее Вы и не пытались найти, только осуществляли попытку найти опровержение. Если Вы сможете доказать эту свою гипотезу, это будет серьезным научным результатом, но пока что вся Ваша работа сводится к формулировке этой гипотезы и подробному рассказу о том, какие числа не смогли стать ее опровержением.


19.08.2021, 10:06 Цорин Борис Иосифович
Отзыв: Вопрос же "В чем смысл любого теста", я, с Вашего позволения, оставлю без ответа, как слишком неконкретный. Если он не являлся риторическим, дайте определение понятия "смысл", использованного в вопросе.


19.08.2021, 10:49 Цорин Борис Иосифович
Отзыв: В прошлом сообщении по невнимательности не то число написал: там, где "48", должно быть "35". Но это не влияет ни на что иное.


22.08.2021, 14:15 Мирмович Эдуард Григорьевич
Отзыв: И всё же слово "самый" в названии не очень корректно, оно декларативно применено. Лучше бы использовать слово "более", или надо добавлять "чем..." такой-то или такие-то..


22.08.2021, 14:41 Усов Геннадий Григорьевич
Отзыв: Теперь нашел время отвечать на вопросы. Прошло почти 2 года с публикации, пришлось заново вникать в суть проблемы. Так я понял, что вопроса 4: (1а), (1б), (2), (3). Очень трудно было понять, к какому месту статьи относится вопрос, поэтому я решился на изменение статьи - только обозначить цифрами форимулы. Просьба повторить ворпросы не текстом, а привязкой, если возможно, к формулам, или близко от них. Теперь по существу. (1а) "для r=0," - " Я пока не нашел у себя букву r (1б) У меня число k отрицательное, но степень положительная.(2) Пока не нашел в статье выделенной Вами моей фразы. Просьба привязать к номерам формул.


22.08.2021, 14:57 Усов Геннадий Григорьевич
Отзыв: (3) Здесь я немножко обобщил. Есть числа Мерсенна, их ищут, поскольку есть тест Люка-Лемера. Про другие числа разговор не идёт, так как тест Люка-Лемера не про них. Может быть ищут числа Мерсенна из-за азарта: нашёл самое большое число, и ничего более. Но если это только азарт, то окрестность чисел Мерсенна никому не нужна. Алгоритм (4) позволяет работать с другими числами, которые расположены недалеко от чисел Мерсенна. "Недалеко" - понятие относительное. Но есть такое предположение (по Вашему - гипотеза). А есть ещё вопрос от меня. (4) Как такое получилось, что нет формулы для определения простых чисел и есть тест (не вероятностный) для определения чисел Мерсенна?


22.08.2021, 15:07 Усов Геннадий Григорьевич
Отзыв: (0) (Наверное, это более ранний вопрос) Тест Миллера-Рабина и ссылка на мою статью [2]. На самом деле далее этот тест не используется, взято только число 3. А новый алгоритм построен на основе обычного алгоритма возведения в степень по модулю (pow или что-то подобное). Нужно было об этом сказать. Просто добавляются лишние блоки, получается симметрия, нет лишних прибавлений или отниманий и всё.


23.08.2021, 8:43 Цорин Борис Иосифович
Отзыв: "r=0" и прочие фразы, которые Вы не смогли найти - это переформулировка Ваших утверждений в применении их к тесту Миллера-Рабина. {1a}, {1b}, {2} и {3} - это не вопросы, это отличия Вашей работы от теста Миллера-Рабина как аргументация того, что "Ваш алгоритм" - это просто тест Миллера-Рабина с ошибкой. В {1b} был невнимателен, да, ремарка про отрицательные степени вычетов снята, значит, здесь нет отличия, Вы просто расписали подробнее один из шагов возведения в степень. Кстати, насчет "отрицательных k", как Вы относитесь к числу M7-6? Отрицательное четное k=-6, Ваш "алгоритм" считает число 121 простым.


23.08.2021, 11:29 Усов Геннадий Григорьевич
Отзыв: Есть предложение: вопросы (1а), (1б), (2), (3), как относящиеся к появлению в статье алгоритма, который по мнению рецензента есть просто тест Миллера-Рабина, отнести к предыдущей работе автора. Автор взял из предыдущей работы только число 3 и зачем-то (?) описал весь алгоритм. Если есть вопросы к тому алгоритму, то лучше эти вопросы обсуждать в предыдущей статье. Повторяю: этот алгоритм в статье не используется, и применяется только число 3. Появился вопрос (4) - число M7-6. Буду искать программу и проверять. Потом отвечу.


23.08.2021, 15:40 Усов Геннадий Григорьевич
Отзыв: По поводу M7-6. В предущей статье есть фраза: "отличающихся от чисел Мерсенна Mn на числа k, кратные 4." В этой статье я это упустил. Почему именно 4, буду смотреть на старые расчёты.


23.08.2021, 15:50 Цорин Борис Иосифович
Отзыв: I. Теперь нашел время пояснить еще подробнее. Вся текущая статья состоит из четырех частей. В первой части (формула 1) Вы дублируете свой "эвристический алгоритм" из другой статьи, со всеми его ошибками, и дальнейшая статья основана на нем. Во второй части (формулы 2-15) Вы подробно рассказываете, как собираетесь возводить в степень, развернув на две страницы обычное a^(b+c)=a^b*a^c. Я предпочту оставить без комментариев актуальность этой части статьи. В третьей части статьи (формула 16) Вы бездоказательно заявляете, что тест Пелена каким-то образом подтверждает "Ваш алгоритм", как будто Вы свой алгоритм предлагаете применять исключительно к числам Ферма. В четвертой части статьи Вы подробно рассказываете, какие именно числа не опровергли Ваше мнение о том, что "Ваш алгоритм" всегда работает. Далее разобью на отдельные отзывы.


23.08.2021, 15:58 Цорин Борис Иосифович
Отзыв: II. Начну с четвертой части. Проверенные Вами числа ничего не доказывают. Доказательство того, что что-то верно всегда, производится не перебором. Не являющихся простыми чисел, для которых тест Миллера-Рабина с выбранным основанием 3 дает ложное утверждение о простоте, не так много. Например, в районе M28 таких чисел примерно одно-два на миллион, в районе M35 - примерно одно на десять миллионов. И то, что среди чисел Мерсенна и близких к ним до М35 Вы не обнаружили таких чисел, не только не делает гипотезу доказанной (доказанной ее никакой перебор до М1000000 сделал бы), но и даже обоснованной.


23.08.2021, 16:18 Цорин Борис Иосифович
Отзыв: III. А теперь подробнее про часть первую, про сам "эвристический алгоритм", записанный в формулах (1) и (7). Этот "алгоритм" де-факто является тестом Миллера-Рабина с тремя отличиями, о которых я уже говорил. {Отличие 1} Вы предлагаете делить проверяемое число на 2 только один раз, тогда как тест Миллера-Рабина . Для чисел Mn и Mn+4k это не столько отличие, сколько тривиальное преобразование теста Миллера-Рабина, не меняющее его суть. Для чисел, отличающихся от Мn на четное число, не делящееся на 4, это отличие увеличивает шанс неверного ответа (составное число будет названо простым), приближая "Ваш алгоритм" по качеству работы к тесту Ферма. В других статьях Вы предлагали применять "Ваш алгоритм" только к числам вида Mn и Mn+4k. {Отличие 2} Вы указываете в формуле 1, что для чисел Мерсенна (и только для них) не надо проверять случай с a^d=1, а надо проверять только случай с a^d=Mn-1. Скорее всего, это верное утверждение, но не доказанное. Я предлагаю Вам доказать (только, пожалуйста, не надо перебор за доказательство выдавать), что в целом 3^(2a+1) не может быть равно 1 по модулю вида 12k+7, из этого и вытекает то, что это "отличие 2" верно. Однако на асимптотику времени работы теста это отличие не влияет, и поэтому не может служить признаком усовершенствования Вами теста Миллера-Рабина. {Отличие 3} является главным, поэтому его я вынесу в отдельный отзыв.


23.08.2021, 16:28 Цорин Борис Иосифович
Отзыв: IV. {Отличие 3} Тест Миллера-Рабина говорит: надо взять несколько разных a, сравнивая a^d (mod M), и чем больше проверить разных чисел a, тем ниже вероятность, что число будет ошибочно признано за простое. Вы говорите: для чисел Мерсенна и близких к ним достаточно взять a=3, и ответ будет всегда верным. Это очень значимое отличие, и это могло бы быть значительным усовершенствованием теста Миллера-Рабина, давая Вам даже право назвать это тестом Усова. Но есть проблема. Вы никак не доказали свое утверждение. Перебор нескольких тысяч относительно небольших чисел никак не является доказательством. Как я написал в отзыве номер II, в текущем виде это гипотеза, практически ни на чем не основанная. Переберете до M1000000 - будет гипотеза, основанная на практике. Но чтобы считать этот алгоритм Вашим научным результатом, необходимо именно доказать математически, что вот такая вот категория чисел при проверке тестом Миллера-Рабина с a=3 не может назвать простое число составным. В текущем же виде весь комплекс из трех Ваших статей по "эвристическому алгоритму поиску простых чисел в окрестностях чисел Мерсенна" - это бездоказательно ограниченный Вами тест Миллера-Рабина, несколько тривиальных алгебраических преобразований, ну и много-много бесполезной информации о том, сколько небольших простых чисел Вы им нашли.


23.08.2021, 16:39 Цорин Борис Иосифович
Отзыв: V. Ну и так, на десерт, хотя я где-то уже писал это, но Вы проигнорировали. "Эвристический алгоритм" - это алгоритм, который выдает ответы, близкие к истине. Алгоритм, выдающий ответы "да" и "нет", эвристическим быть не может по определению. Он может быть вероятностным, если правильный ответ он выдает намного чаще неправильного. Вероятностным алгоритмом является тест Миллера-Рабина. Вероятностным алгоритмом является тест Ферма, модификацией которого является тест Миллера-Рабина. Тест Миллера-Рабина является значимым научным результатом, так как он выдает неверный результат реже теста Ферма. "Ваш алгоритм" из-за модификаций выдает неверный результат чаще теста Миллера-Рабина (ну если Вы не докажете свою гипотезу, конечно). Все же математические преобразования со степенями, которые Вы проводили, не меняют алгоритм в целом, а относятся исключительно к его реализации. Причем реализации некачественной, замедляющей процесс возведения в степень. Единственная нормальная реализация алгоритма возведения в степень у Вас в формулах (3)-(4), дальше все модификации возведения в степень замедляют процесс. Открываем Википедию на статье "Алгоритм быстрого возведения в степень" и просвещаемся.


25.08.2021, 18:45 Цорин Борис Иосифович
Отзыв: IIIa. Дополнения и поправки к предыдущим отзывам. В отзыве III в {Отличии 1} в первом предложении я как-то утерял кусок предложения, после "тогда как тест Миллера-Рабина" должны быть слова "предлагает сделать это столько раз, сколько возможно, проверяя каждый шаг". В том же отзыве III в {Отличии 2} доказательство я за Вас нашел, через символ Якоби доказывается в два шага. Следовательно, сколь-либо значимым научным результатом {Отличие 2} не является, как тривиальное следствие из символа Якоби, не имеющее практической значимости (напоминаю, на асимптотическую сложность алгоритма оно не влияет), не говоря уже о том, что Вы его не доказали. Интересно, справитесь ли Вы с доказательством, уже получив несколько подсказок.


27.08.2021, 13:43 Мирмович Эдуард Григорьевич
Отзыв: Ещё раз повторяю Ваши слова: "Найден БОЛЕЕ БЫСТРЫЙ...", а не самый быстрый. Скорректируйте название. А ваша никчемная перепалка с учителем из моей любимой Балашихи не имеет смысла в рамках данного журнала. Если рецензент дал отрицательную рецензию - просто ждите вторую положительную. А дискуссию, как я у же говорил тридцать раз, перенесите в формат дискуссионных статей, которые станут дополнительными публикациями. Рецензент безошибочно, как видно из непрекращающейся перебранки, сформировать в одну статью свои возражения не может и не сможет из-за нечёткости и не безошибочности своих нотаток. А ВЫ, выделив основные его претензии и сославшись на них, можете. А то выглядит всё смешно и некорректно. Вы преувеличиваете значимость своей небольшой разработки, которой захотели поделиться с нашей аудиторией, а он её зануляет и никогда к положительной рецензии не перейдёт ни при каких условиях. А тут мне шлют и шлют на почту ваши экзерсисы и упражнения, часть из которых - просто повторяющееся словоблудие. ПОВТОРЯЮ алгоритм рецензирования во всех журналах любого статуса. Рецензент на основании СВОИХ личных компетенций оценивает работу и даёт положительную или отрицательную рецензию. Автор или принимает замечания и исправляет их, либо игнорирует и ждёт следующей рецензии. Вот и вся кухня. Тем более, когда попадается самомнительный и высокомерный рецензент, каковых здесь у нас единицы. Ведь оба оппонента всё равно черпают "кровь" для споров из одного источника, который называется "ИНТЕРНЕТ". Компетентный рецензент обычно при возражениях не рыщет в сети материал для оппонирования, а ссылается на СВОИ работы или диссертацию в этой области, которых у данного рецензента нет, а опубликована всего одна статья по исторической лингвистике, которую можно и раскритиковать и полностью разгромить, если захотеть.


27.08.2021, 14:23 Цорин Борис Иосифович
Отзыв: Просто замечательное мнение высказал Эдуард Григорьевич. Нам надо, оказывается, написать другую статью и перенести спор туда, чтобы на почту ему сообщения об отзывах не шли. Эдуард Григорьевич, Вы можете на почте настроить автоматический перенос оповещений в отдельную папку, хоть в "Спам". Что же касается Вашего мнения о "ссылается на свои работы", то хочу отметить, что лично Вы любите рецензировать работы в самых различных областях, от ветеринарии до эмиграции, и в большинстве этих рецензий я как-то ссылок на Ваши работы не замечал, а для меня, однако же, поиск и указание математических и логических ошибок в чужих работах являются важной профессиональной компетенцией. Так что я призываю Вас раскритиковать и полностью разгромить мою статью по исторической лингвистике, ибо в этой области как раз я признаю себя некомпетентным и с интересом ознакомлюсь с критикой.


27.08.2021, 14:25 Цорин Борис Иосифович
Отзыв: Ну и отдельно хочу сказать Эдуарду Григорьевичу, что наше с ним понимание смысла научных журналов различается. Я вижу смысл науки в поисках истины, а не в публикации всех статей, сколь угодно ошибочных, но зато получивших положительную рецензию хотя бы от кого-нибудь.


27.08.2021, 14:26 Усов Геннадий Григорьевич
Отзыв: Уважаемый Эдуард Григорьевич! Спасибо за поддержку! Я почему-то считал, что нельзя трогать эту статью, так как она напечатана. Теперь попробую исправить. У меня такая-же проблема: давно ввязался в обсуждение статьи про "школьное доказательство", теперь вся перебранка в этой статье сыплется ко мне. Я уже сокращаю круг вопросов по своим статьям, при этом стараюсь остановиться только на тех, которые самые основные. С другой стороны, запоминаю типовые замечания. Это ещё должно помочь в дальнейшем, так как готовится ещё одна статья про псевдопростые числа (анонс). С уважением, Усов Геннадий Григорьевич


28.08.2021, 19:23 Мирмович Эдуард Григорьевич
Отзыв: Ну, вот, и Э.Г. втягивают в какие-то словоблудские и хитроумные дискуссии. Журнал приравнивается к науке в целом. Демагогия про истину тут и вовсе неуместна. Лживые сентенции выдаются в виде поучений и критических выводов. Миссия научной публицистики (не науки) "в публикации всех статей... получивших положительную рецензию" официального рецензента ... "Хотя бы от кого-нибудь" журнал рецензии не принимает. "Сколь угодно ошибочных" или не "сколь угодно ошибочных" - это на совести и компетенции автора, которого в этой же научной печати раскритикуют, а в варианте ВАК, WoS, Scopus и подвергнут ретрагированию (ретракции) по канонам АНРИ. И именно туда и подаётся заявка на ретракцию, если обнаружены "сколь угодно ошибочные" в технологическом и редакционном отношении научные публикации. Здесь речь идёт лишь о рецензиях. Там, где даётся отрицательная рецензия по формальным признакам, отступлению от требований ГОСТа и др. оформительских канонов, любой рецензент в суть и содержание статьи может и не вдаваться, т.к. не соблюдены необходимые условия представления статьи в научную печать. И тут профессиональный редактор может давать рецензию любой статье. Но если же рецензент подвергает статью критическому научному анализу, опровержению выводов и результатов, то читатель, не обладающий глубокими знаниями в данной области, естественно, ищет подтверждения компетенции данного разбора, данного рецензента, и наиболее адекватным вариантом является наличие ссылок рецензента на свои и классические труды. Если рецензия позитивного направления, а рецензент делает замечания, которые помогут ему при учёте их автором дать положительную рецензию, то стоит дискутировать, отвечать, учитывать, исправлять или нет и т.д. Если же даётся принципиально отрицательная рецензия, то никакая дискуссия не имеет смысла, а автор ожидает рецензию других рецензентов. Если же и следующая рецензия окажется отрицательной, то статья снимается из портфеля. К рецензенту здесь претензий нет. Претензии к автору, который занимает время у своих коллег тем, что пытается «выпросить» положительную рецензию у настроенного отрицательно рецензента.


3.09.2021, 12:57 Усов Геннадий Григорьевич
Отзыв: Основная идея статьи - найден алгоритм (тест) определения чисел Мерсенна, сравнимый по быстродействию с тестом Люка-Лемера (и чуть-чуть быстрее). Во всех публикациях всегда говорили, что тест Люка-Лемера самый быстрый. А окрестность взял из предыдущей статьи для рекламы чисел из окрестности чисел Мерсенна.


3.09.2021, 15:31 Цорин Борис Иосифович
Отзыв: Тест Люка-Лемера - самый быстрый из детерминированных. Тест Миллера-Рабина при применении его по одному основанию сравним с тестом Люка-Лемера по скорости, но является вероятностным.


Оставить комментарий


 
 

Вверх