The Problem of Evaluating the Effectiveness of the Miller-Rabin Primality Test

Research article
DOI:
https://doi.org/10.23670/IRJ.2023.131.1
Issue: № 5 (131), 2023
Suggested:
25.07.2022
Accepted:
10.04.2023
Published:
17.05.2023
889
3
XML
PDF

Abstract

This work analyses the efficiency of the Miller-Rabin test. As a starting point for the analysis, the algorithm for finding a sequence of ψn numbers was chosen. Within this algorithm, a "bottle-neck" was detected and a way to solve it was presented. It turned out to be the memory consumption.

The main idea is the distribution of pseudoprime numbers over bin(ordp(ai)) values. It is concluded that the distribution is uneven and there is a strong bias towards smaller values of bin(ordp(ai)). For clarity, all reasoning and experimental results are accompanied by graphs.

Thanks to the data obtained, it was concluded that it is possible to divide the whole set of pseudoprime numbers into subsets by the value of bin(ordp(ai)). Thus, the final algorithm is produced, in which the memory consumption is optimized compared to the original algorithm.

1. Введение

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

Таким образом, актуальность работы обеспечивается использованием простых чисел в современных исследованиях. Например, в статьях

и
представлен новый протокол маршрутизации, основанный на простых числах, позволяющий обнаруживать кротовые норы в мобильных сетях. Также в статьях
,
и
представлен алгоритм шифрования, основанный на простых числах и биометрии, а также его применение в технологии блокчейна, а также его использование в интернете вещей. А в статье
представлен алгоритм шифрования изображений, использующий множество простых чисел и полярное разложение.

Основной целью является исследование эффективности работы теста Миллера-Рабина и распределения его ошибки. Для достижения поставленной цели были сформулированы и решены следующие задачи:

1. Анализ существующих методов оценки эффективности теста Миллера-Рабина.

2. Анализ возможных оптимизаций для существующего метода оценки эффективности теста Миллера-Рабина.

Тест Миллера-Рабина

,
является вероятностным тестом. Это означает, что тест может выносить ошибочный вердикт, но с очень маленькой вероятностью. В настоящий момент известна только верхняя граница для её значения, однако она сильно завышена.

Есть и другой подход к оценке эффективности алгоритма – последовательность чисел img – наименьшее строго псевдопростое число для n первых простых чисел. Главная сложность этого подхода – быстрый рост значение и отсутствие эффективных непереборных алгоритмов.

Таким образом, имея достаточно точную информацию об эффективности теста Миллера-Рабина, можно на его основе создавать модификации и получать достаточно точные асимптотики времени выполнения и памяти.

К примеру, К. Нари, Е. Оздемир и Н. А. Озкирисци представили алгоритм

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

2. Методы и принципы исследования

Тест Миллера-Рабина – вероятностный тест, представленный сперва Г. Миллером в 1976 г.

, затем улучшенным М. О. Рабиным в 1980
. Основан этот тест на модификации теоремы Эйлера
.

Для упрощения дальнейшего описания теорем и алгоритмов введём следующие функции:

Определение 1. Пусть n – произвольное натуральное число, представимое следующий вид:

img
(1)

Тогда функции bin(n) и odd(n) определяются следующим образом:

img
(2)

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

img
(3)

Если одно из условий выполнилось, то число a называется свидетелем простоты числа n, а само число считается прошедшим текущую итерацию теста.

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

:

Теорема 1. Пусть n – произвольное натуральное число, представимое следующий вид:

img
(4)

Тогда выполняются все перечисленные условия:

img
(5)

Где за ordk(a) обозначают порядок числа a по модулю k.

Обозначим за W(n) – количество свидетелей простоты. Ш.Т. Ишмухаметов, Б.Г. Мубараков и Р.Г. Рубцова представили конечную формулу

для расчёта функции W(n) для случая полупростого n=p*q:

img
(6)

Однако позже Б. Г. Мубараков получил формулу

для произвольного числа n по его разложению на простые множители img:

img
(7)

Следующим шагом для оценки эффективности вводится функция Fr(n)  вероятность выбора свидетеля простоты. Поскольку из условий (3) следует, что НОД (a, n)=1, то значение функции будет вычисляться по следующей формуле:

img
(8)

М.О. Рабин доказал, что ¼ верхняя граница

для Fr(n). Однако данное значение достигается для бесконечного количества чисел n, что значительно усложняет анализ этой функции.

Поэтому оценки вычислялись для среднего значения вероятности на отрезке Avg(Fr(n)). Первая оценка

для этой функции была получена Б.Г. Мубараковым, но ограничиваясь только полупростыми числами n=p*q при фиксированном p:

img
(9)

Однако данная оценка была сильно завышена, поэтому Б.Г. Мубараков представил улучшение оценки, но для случая p=2*p', где p' – простое число. Для этой цели рассматривались два возможных случая отношений p и q:

1. q=(p-1)k+1 → в этом случае верхняя оценка из (5) становится асимптотикой функции

.

2. q=2k+1, где 2k mod (p-1) ≠ 0 → в этом случае верхняя оценка из (5) улучшается до следующей

:

img
(10)

Наконец, посчитав математическое ожидание от обоих вариантов получаем результат

:

img
(11)

После чего было высказано предположение, что для всех значений p оценка будет принимать следующий вид

:

img
(12)

Где коэффициент img находится на отрезке img.

Также были получены результаты

для трёхпростых чисел img. Первая оценка была получена для фиксированных img и img:

img
(13)

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

На настоящий момент получены оценки для двух классов:

1. Трёхпростое число, при фиксированном img и img, удовлетворяющих следующим условиям:

img
(14)

Итоговая оценка для такой ситуации

,
:

img
(15)

2. Трёхпростое число, при фиксированном p и q, удовлетворяющих следующим условиям:

img
(16)

Итоговая оценка для такой ситуации

:

img
(17)

Второй подход к оценке эффективности основан на свойствах функции img

определённой следующим образом:

img
(18)

Теперь укажем теорему, на которой построена другая оценка:

Теорема 2. Пусть img произвольное число, представимое в виде img, где img – простое. Тогда для того, чтобы img было строго псевдопростым по базе img необходима делимость img на img.

Используя теорему 2 и оценки количества делителей, мы получаем верхнюю оценку

для ошибки теста Миллера-Рабина, но только для полупростых чисел:

img
(19)

Однако реальные значения не достигают верхней оценки. Значит эту оценку можно улучшить.

Третий подход к оценке эффективности – вычисление последовательности чисел img – наименьшее строго псевдопростое число для img первых простых чисел. Ж. Женхианг смог получить кандидатов

для значений первых 19 элементов последовательности. До настоящего времени смогли доказать
эту гипотезу только для первых 13 элементов последовательности.

Рассматривая уже полученные результаты, можно сделать вывод о том, что последовательность очень быстро возрастает. Однако эффективный алгоритм поиска очередного алгоритма пока не найден, поэтому поиск следующего элемента последовательности затруднителен.

Наиболее оптимальный переборный алгоритм

, который использовался для поиска последних известных элементов последовательности основан на Теореме 2 и следующих утверждениях:

Утверждение 1. Если для произвольных простых чисел img и img выполняется img и img, то img.

Утверждение 2. Если для произвольных простых чисел img и img выполняется img и img, то img.

Сам алгоритм состоит из двух методов, каждый из которых выполняет перебор возможных кандидатов img по своим критериям.

Первый метод использует НОД для получения всех кандидатов. На вход метод получает число img. В ходе алгоритма вычисляются все img для всех оснований img. Затем вычисляется НОД полученных значений. img получаются путём перебора всех делителей НОД. Второй метод используя утверждения 1 и 2 перебирает все возможные остатки по достаточно большому модулю. После чего получаются перебором всех простых чисел с заданным остатком по модулю.

Поскольку первый метод эффективней на маленьких числах, а второй метод на больших, то первый метод применяется для всех img, где img – верхняя граница отрезка на котором производится поиск, а второй метод для остальных img. Значение границы для методов было получено теоретическим путём для наиболее оптимального раздела.

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

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

Algorithm 1.

img – хэш-таблица, img – граница для перебора, img – набор оснований.

Перебираем все простые числа img от img до img:

Вычисляем все img.

Получаем список всех простых чисел из img с совпадающими значениями img.

Формируем все возможные значения img:

Если img, то перебираем всех кандидатов на строго псевдопростоту с помощью первого метода.

Иначе, с помощью второго.

Если img, то добавляем в img вместе со всеми значениями img.

3. Основные результаты

Поскольку последовательность чисел img растёт достаточно быстро, то рассматриваемые границы для поиска также будут сильно увеличиваться. Это приведёт не только к замедлению времени работы, но и увеличению объёма используемой памяти. Например, img, следовательно, в хэш-таблице будет храниться порядка img элементов, что крайне много для хранения на компьютере. Поэтому необходимо модифицировать алгоритм 1, чтобы он затрагивал меньше памяти.

Для начала рассмотрим распределение простых чисел на отрезке по значению img. Для ускорения вычисления мы введём следующую функцию:

Определение 1. Пусть img и img – произвольные числа, img – простое, a img определяется следующим образом:

img
(20)

Тогда функция img, определяется следующим образом:

img
(21)

Эффективный поиск значения этой функции выполняется следующим алгоритмом:

Алгоритм 2.

img – простое, img – натуральное числа, img

Посчитаем img

Посчитаем img

Пока img не станет равным 1 выполняем:

 img

 img

Значение img устанавливается результатом функции

Вычислительная сложность данного алгоритма img.

Для использования данного алгоритма докажем следующую теорему:

Теорема 3. Пусть img произвольное число, тогда выполняется следующее соотношение:

img
(22)

Доказательство. Пусть img. Тогда возможно 2 варианта:

1. img.

img

imgimgimg найден неверно.

2. img.

img – целое

img → img найден неверно.

Значит остаётся единственный вариант в (21).

Таким образом, заменив вычисление img на img, мы получим тот же результат, но за меньшее время.

4. Обсуждение

После получения распределения простых чисел на отрезке img по значениям img видно, что основная часть простых чисел имеет очень маленькое значение (см. рисунки 1, 2).
Распределение простых чисел по значениям для основания 7

Рисунок 1 - Распределение простых чисел по значениям для основания 7

Распределение простых чисел по значениям для основания 19

Рисунок 2 - Распределение простых чисел по значениям для основания 19

Также можно заметить, что количество простых чисел падает примерно в 2 раза, пока не приблизится к крайне малым значениям (см. рисунок. 3).
Отношение количеств простых чисел на соседних значениях

Рисунок 3 - Отношение количеств простых чисел на соседних значениях

Из-за столь большой скорости падения количества более 90% простых чисел имеет значение img не более 4 (см. рисунок. 4).
Процент оставшегося количества чисел

Рисунок 4 - Процент оставшегося количества чисел

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

Рисунок 5 - Процент оставшегося количества чисел

Таким образом, можно сделать вывод о необходимости разбиения алгоритма на 2 этапа:

1 этап – перебрать все простые числа со значением всех img меньше заданного порогового значения img с помощью алгоритма 2. При этом само значение img перебирать из некоторого фиксированного набора img.

2 этап – перебрать все простые числа со значением хотя бы одного img не меньше img с помощью другого, возможно менее эффективного для большого количества чисел, алгоритма.

Пример такого алгоритма:

Алгоритм 3.

img – список простых чисел, img – список контейнеров для простых чисел

Перебираем все основания img:

Очищаем все контейнеры в img

Перебираем все числа img из img:

Вычисляем img

Переносим img из img в img

Переносим последовательно все простые числа из контейнеров img в img

Вычислительная сложность данного алгоритма img

5. Заключение

В рамках данной работы были представлены текущие результаты по оценке эффективности теста Миллера-Рабина. Было продемонстрировано три разных подхода, сделаны выводы о возможном направлении для каждого подхода. Для модификации был выбран третий подход – поиск последовательности чисел img – наименьшее строго псевдопростое число для img первых простых чисел.

Было обнаружено «бутылочное горлышко» для исходного алгоритма – им оказался расход памяти на хэш-таблицу. Поэтому дальнейшие исследования направлены на оптимизацию расхода памяти.

Были сделаны выводы о распределении простых чисел по значениям img и рассмотрен вариант использования полученных данных для модификации алгоритма.

Была представлена новая схема алгоритма со сравнимым временем работы, но уменьшенным расходом памяти.

Article metrics

Views:889
Downloads:3
Views
Total:
Views:889