Построение оценок эффективности теста простоты Миллера-Рабина тема диссертации и автореферата по ВАК РФ 05.13.11, кандидат наук Мубараков Булат Газинурович

• Мубараков Булат Газинурович
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Мубараков Булат Газинурович

1.2. Алгоритмы просеивания

1.3. Детерминированные алгоритмы

1.4. Вероятностные тесты простоты

1.5. Тесты простоты, отсекающие числа Кармайкла

1.6. Строго псевдопростые числа

1.7. Заключение по главе

Глава 2. ИССЛЕДОВАНИЕ СВИДЕТЕЛЕЙ ПРОСТОТЫ СОСТАВНЫХ ЧИСЕЛ

2.1. Улучшение оценки теста Миллера-Рабина

2.2. Формулы числа свидетелей для составных чисел

2.3. Формула для подсчета числа свидетелей произвольного составного числа

2.4. Функция частоты распределения свидетелей Гт(и)

2.5. Заключение по главе

Глава 3. СРЕДНЯЯ ЧАСТОТА РАСПРЕДЕЛЕНИЯ СВИДЕТЕЛЕЙ

В ЗАДАННЫХ ИНТЕРВАЛАХ

3.1. Расчет средней частоты для полупростых чисел

3.2. Улучшение асимптотической оценки средней вероятности частоты

3.3. Анализ полученных оценок

3.4. Заключение по главе

ГЛАВА 4. ЭКСПЕРИМЕНТАЛЬНЫЕ РАСЧЕТЫ СРЕДНЕЙ ЧАСТОТЫ ЧИСЛА СВИДЕТЕЛЕЙ

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

4.2. Практический алгоритм подсчета средней частоты числа свидетелей

4.3. Оценка трудоемкости алгоритма подсчета средней частоты

4.4. Вычисление суммы частот по интервалам

4.5. Экспериментальные данные по оценке точности формулы Чебышева

4.6. Расчет суммы частот для полупростых чисел п = pq при фиксированном множителе р

4.7. Расчеты средней частоты по объединенным сериям

4.8. Экспериментальные данные по частоте для чисел п = ^

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

4.10. Важные следствия из теорем 4.4, 4.5 и гипотезы

4.11. Заключение по главе

ЗАКЛЮЧЕНИЕ

БИБЛИОГРАФИЯ

ПРИЛОЖЕНИЯ. Библиотека вспомогательных программ на языке Ру1Ьоп106

7.1. Тексты программ, использованных в диссертации

7.2. Описания процедур, входящих в пакет компьютерных программ

Введение диссертации (часть автореферата) на тему «Построение оценок эффективности теста простоты Миллера-Рабина»

ВВЕДЕНИЕ

Наше исследование посвящено оценке эффективности известного в теории чисел и криптографии теста простоты Миллера-Рабина. Этот тест относится к классу полиномиально вычислимых вероятностных тестов простоты и широко используется для генерации криптографических ключей в ряде популярных протоколов криптографии таких, как RSA, DSS и другие.

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

Тест Миллера-Рабина основан на малой теореме Ферма и допускает ошибки, ошибочно квалифицируя составные числа как вероятно простые. Доля таких ошибок невелика и оценена в теореме Миллера [49] величиной 1/4k, где к- количество итерация в тесте Миллера-Рабина. Иначе говоря, если мы выполним к итераций для проверки простоты нечетного составного числа n > 9, то вероятность ошибочного заключения "n- простое число"будет меньше 1/4k (например, при к = 10 такая вероятность будет меньше одной миллионной).

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

В этой работе мы выполнили глубокий анализ теста Миллера-Рабина, сумели существенно улучшить оценки, данные в теореме Рабина, уменьшив вероятность ошибки с 1/4k до 1/16k. Также мы построили точные формулы для вероятности ошибок для всех видов составных чисел в зависимости

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

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

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

Frn = M,

Фч

где W(n) - число свидетелей простоты числа n, а ф(п) - значение функции Эйлера для n. Если число n-простое, то Fr(n) = 1. Для составных чисел n значение Fr(n) < 0, 25. Чем меньше Fr(n), тем меньше вероятность ошибки теста Миллера-Рабина. Поэтому изучение значений этой функции и ее распределения на различных числовых интервалах представляет важную и актуальную задачу. В третьей главе нашей работы мы занимаемся построением теоретических верхних оценок для средних значений этой функции на различных числовых множествах, что позволяет нам построить асимптотические верхние оценки. Также мы выполняем экспериментальные расчеты

5

по проверке теоретических оценок.

У каждого натурального числа всегда найдется, по-крайней мере, два свидетеля простоты - 1 и п — 1. Такие свидетели простоты мы будем называть тривиальными. Если у составного числа п найден нетривиальный свидетель простоты, то такое п называется строго псевдопростым. Изучение строго псевдопростых чисел является важной задачей теории чисел, поскольку знание строго псевдопростых чисел по заданному множеству баз позволяет превратить вероятностный тест Миллера-Рабина в детерминированный для тех чисел, для которых найдется строго псевдопростое число, превышающее тестируемое число п [44], [45].

Исследование вероятности ошибок в тесте Миллера-Рабина стало возможным благодаря введению специальной функции вероятности частоты Гт(п), которая равна отношению числа свидетелей простоты числа п к функции Эйлера ф(п). Функция Гт(п) принимает значение 1 на простых числах, а на составных числах ее значение не превышает 0,25. Мы ввели естественное понятие средней частоты на заданном множестве составных чисел, как отношение суммы всех частот чисел из этого множества к числу таких чисел. Эта величина точно характеризует вероятность ошибки теста Миллера-Рабина в единичном испытании для произвольного составного числа.

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

Глава 1. ОБЗОР ОСНОВНЫХ ТЕСТОВ ПРОСТОТЫ НАТУРАЛЬНЫХ ЧИСЕЛ

В этой главе мы изучим основные методы и алгоритмы проверки натуральных чисел на простоту. Подробное описание большинство таких процедур можно найти в книгах Кренделла и Померанса "Простые числа: криптографические и вычислительные аспекты"[36] и Ишмухаметова "Методы факторизации натуральных чисел"[19]).

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

• Алгоритмы просеивания, которые вычеркивают все составные числа из заданного интервала, оставляя только простые числа;

• детерминированные тесты, которые точно определяют, является ли заданное число простым или нет;

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

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

Основные понятия и определения

Будем обозначать через Z множество целых чисел,через N - множество натуральных чисел, и через P множество простых чисел.

Zn - кольцо вычетов по модулю натурального числа п. Мультипликативный порядок элемента a = 0 кольца Zn - это наименьшее положительное число t такое, что af mod п = 1. Обозначается символом t = ordn(a).

Функция bin(n) равна по определению степени s, если натуральное число n имеет разложение n = 2s • t, где t- нечетно. Нечетный множитель t будем обозначать через odd(n). Таким образом, произвольное натуральное число n имеем разложение

П = 3Ып(п) • odd(n).

Функция п(х) обозначает количество простых чисел на интервале [2; х]. По известной теореме Чебышева эта функция асимптотически стремится к функции х/ ln х при х ^ с [58].

Гипотеза Римана ГР- это одна из нерешенных проблем математики, утверждающая, что все нетривиальные нули дзета-функции Римана лежат на комплексной прямой ReZ = 1/2.

Обобщенная гипотеза Римана ОГР обобщает гипотезу Римана и имеет важные следствия о распределении простых чисел. В частности, из нее следует, что

ix 1

п(х) = -dt + O(x1/2) J 2 t

Функция GCD(a, b) равна наибольшему общему делителю чисел a

и b.

Малая теорема Ферма. Пусть n-простое число. Тогда для любого положительного а, не являющегося кратным n, выполняется условие

an-1 = 1 mod n. (1.1)

Функция Эйлера ф(п) определена на натуральных числах и по определению равна мощности множества положительных натуральных чисел, меньших n и взаимно простых с n:

ф(п) = \{а : 1 < а < n, GCD(a,n) = 1}|.

Функция Эйлера является мультипликативной. Ее значение можно вычислить по формуле

ф(п) = n П i1 - '

p\n

(произведение берется по всем простым делителям n).

Теорема Эйлера обобщает малую теорему Ферма и утверждает, что если GCD(a,n) = 1, тогда

аф(п) = 1 mod n. (1.2)

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

x2 = a mod p, (1.3)

Если это сравнение не разрешимо, то число а называется квадратичным

невычетом по модулю p.

Пусть p - простое число. Символом Лежандра называется функция /

1, если а - квадратичный вычет по модулю p L(a,p) = ^ = < _ 1, если а - квадратичный невычет по модулю p

0, если p\a.

Символ Лежандра можно вычислить за полиномиальное время, используя следующие соотношения:

(ab\ (a\( b\

1. Мультипликативность =

V p J \pj \pj

p / \pJ \p,

* fa\ fb\

2. = , если a = b mod p

pp

3. (J^) = (-i)C-2-1)/8

4. Закон квадратичной взаимности Гаусса для простых чисел p и q:

/p\ iq mod pV , (p-i)(q-i)

W V P J '

Критерий Эйлера. Пусть p - простое число и a <Е Z*. Число a является квадратичным вычетом тогда и только тогда, когда разрешимо сравнение:

p— 1

x~ = 1 mod p. (1.4)

9

Символ Якоби обобщает понятие символа Лежандра на составные числа п = рГ1 • рг22 • • • • Р? и равен по определению

Алгоритмы просеивания

Решето Эратосфена.Одним из первых алгоритмов нахождения всех простых чисел до некоторого целого числа B принадлежит древнегреческому математику Эратосфену Киренскому (2 в. до н. э.) и известен как решето Эратосфена. Его идея состоит в последовательном исключении из списка целых чисел от 2 до заданной границы B чисел, кратных числам 2, оставляя 2, затем кратных 3, оставляя 3, затем 5,..., и т.д. пока для текущего простого числа p не выполнится соотношение p2 > B.

Асимптотическая вычислительная сложность решета Эратосфена составляет O(B log log B) для таблицы чисел от 2 до верхней границы B. Основным недостатком работы этого алгоритма является использование большого объема памяти, сравнимого с размером границы^, до которой требуется вычисление таблицы простых чисел. В наиболее простой версии решета Эратосфена необходимо выделить память для хранения всех натуральных чисел от 1 до B. Чуть более усложненная версия решета работает только с нечетными числами, тогда требуется памяти в два раза меньше. В работе Аткина и Берштейна [31] предложен более экономичный алгоритм нахождения простых чисел до заданной границы, который уменьшает размер памяти, использованной в решете Эратосфена в фиксированное количество раз.

Более быстрый алгоритм просеивания был предложен в статье Прит-чара ([54]). Он приведен в главе 3 книги Крендела и Померанса ([36])(Алгоритм 3.2.2). Для просеивания всех простых чисел до некоторой границы B требуется O(B lnln B/ ln B) итераций, что на фактор ln B меньше, чем в ис-

ходной версии решета Эратосфена.

Решето Аткина. Решето Аткина - это более экономный вид просеивания, основанный на свойствах неразложимых бинарных квадратичных форм (см.[42]). Квадратичная форма - это функция двух переменных x и y заданная формулой

f (x, y) = ax2 + bxy + cy2.

Если коэффициенты формы f берутся из множества целых чисел, то форма f называется целочисленной.

Натуральное число называется свободным от квадратов (square-free), если оно не делится на квадрат целого числа, большего 1. В основе алгоритма Аткина-Берштейна лежат следующие три теоремы:

Теорема 1.1. (Аткин-Бернштейн, теорема 6.1 [31]). Пусть n - натуральное число вида n = 1 + 4k, k Е Z, свободное от квадратов. Число n является простым тогда и только тогда, когда уравнение

О О

4x + y = n имеет нечетное число решений x > 0, y > 0.

Теорема 1.2. (Аткин-Бернштейн, теорема 6.2 [31]). Пусть n - натуральное число вида n = 1 + 6k, k Е Z, свободное от квадратов. Число n является простым тогда и только тогда, когда уравнение

3x2 + y2 = n имеет нечетное число решений x > 0, y > 0.

Теорема 1.3. (Аткин-Бернштейн, теорема 6.3 [31]). Пусть n - натуральное число вида n = 11 + 12k, k Е Z, свободное от квадратов. Число n является простым тогда и только тогда, когда уравнение

О О

3x — y = n имеет нечетное число решений x >^0, y > 0.

Заметим, что остаток г = п mod 60 произвольного нечетного числа п подпадает под один из случаев перечисленных теорем 6.1-6.3. Алгоритм, предложенный Аткиным и Берштейном, работает следующим образом (см.Ишмухаметов [19]):

1. Заполним нулями массив М чисел от 1 до границы В (0 служит для обозначения составного числа, 1 - для простого). Изменение значения массива М [г] будет означать изменение нуля на единицу или единицы на ноль.

2. Для каждого числа п из интервала просеивания, если г = п mod 60 принадлежит множеству {1,13,17, 29,37, 41,49, 53} будем перечислять положительные значения переменных х и у, и для каждого п из интервала просеивания, удовлетворяющего уравнению 4х2 + у2 = п, изменим значение М [п].

3. Для каждого числа п из интервала просеивания, если г = п mod 60 принадлежит множеству {7,19,31, 43} будем перечислять положительные значения переменных х и у, и для каждого решения уравнения 3х2 + у2 = п из интервала просеивания изменим значение М [п].

4. Для каждого числа п из интервала просеивания, если г = п mod 60 принадлежит множеству {11, 23,47, 59} будем перечислять переменные х > 0, х > у > 0, и для каждого решения уравнения 3х2 — у2 = п из интервала просеивания изменим значение М [п].

По оценке Аткина и Берштейна данный алгоритм использует О (В) число операций и О (В1/2+0(1)) памяти (не считая памяти, необходимой для хранения итоговой таблицы простых чисел от 2 до В).

Детерминированные алгоритмы

Детерминированные алгоритмы проверки простоты дают точный ответ, является ли проверяемое число простым или составным. К простейшим алгоритмам такого вида относится алгоритм перебора, который для заданно-

12

го нечетного числа n выполняет пробное деление n на последовательные нечетные числа от 3 до у/и. Алгоритм перебора имеет экспоненциальную асимптотическую оценку сложности и не может быть использован для проверки сколько нибудь больших чисел.

Проблема построения детерминированного полиномиального теста простоты была известна еще античным математикам. Ее решением занимались Ферма, Эйлер, Лагранж и другие знаменитые математики.

Миллер в своей статье [49] 1976 года первым предложил тест такого рода, однако его тест выполнялся в предположении справедливости недоказанной расширенной гипотезы Римана (РГР).

Чистое решение, не требующее использования РГР, удалось получить только в начале 21 века трем индийским математикам Агравелу, Каялу и Саксене (Agrawal, Kayal and Saxena [24]). Тест, предложенный этими авторами, получил название AKS-теста. Этот тест основан на следующей теореме:

Теорема 1.4. Для произвольных натуральных чисел n > 2 и a взаимно-простого с n число n является простым тогда и только тогда, когда в кольце полиномов Z[x] выполняется следующее полиномиальное соотношение:

(x + a)n = (xn + a) mod n

(здесь x - формальная переменная).

Эта теорема является обобщением для полиномов малой теоремы Ферма.

Пусть n > 2 - натуральное число. AKS-тест работает следующим образом:

1. Проверим, является ли n степенью другого натурального числа. Если n = mk, где k > 2, то остановим тест с выводом "n - составное число.".

2. Найдем наименьшее r такое, что ordr(n) > (log2n)2 (если r и n не взаимно просты, то остановим выполнение теста, т.к. n-составное).

3. Если r > n, то n-составное.

4. Для каждого a от 1 до \Jф(г) log2 n выполним проверку эквивалентности

(x + a)n = (xn + a) (mod n, xr — 1).

Если для какого-то a это условие не выполняется, то число n - составное.

5. Делаем вывод, что n - простое число.

В тесте используется функция ordr (n), означающая мультипликативный порядок r по модулю n, то есть наименьшее число t такое, что rf mod n =1 и функция Эйлера ф(п), равная числу взаимно-простых с n чисел k < n.

Асимптотическая оценка сложности выполнения данного теста равна

1 О

О (log n). Из-за высокой степени полинома AKS тест AKS, хотя и является полиномиальным, но практически бесполезен для тестирования больших натуральных чисел.

Числа Мерсенна и тест Люка-Лемера

В XVII веке французский математик Марен Мерсенн занимался исследованием чисел вида 2n — 1, позднее названных в его честь числами Мерсенна, на предмет их простоты. Поиск простых среди чисел Мерсенна достаточно прост благодаря тесту Люка-Лемера, который был предложен в 1878 году Люком и доказан в 1930 году Лемером. Теорема Лемера утверждает следующее:

Теорема 1.5. Пусть p- простое число. Число Мерсенна M(p) = 2p — 1 является простым тогда и только тогда, когда оно делит нацело p — 1-й

член последовательности {4,14,194,...}, вычисляемой по формуле

4, k = 1,

4,

IS

Sk =

1 Ч-1

2 - 2, k > 1.

Например, пусть p = 5, тогда M(5) = 31. Найдем 4-й член (p — 1 = 4) последовательности Люка S4 = 1942 — 2 = 37634 и вычислим остаток S4 mod 31 = 0. Он равен нулю, значит число 31 - простое.

Тест Люка-Лемера используется в настоящее время для поиска больших простых чисел. Например, самое большое известное на сегодняшний день простое число - это число Мерсенна, равное 282589933 — 1. Оно было открыто Патриком Ларошем в рамках проекта GIMPS 7 декабря 2018 года и содержит 24 862 048 десятичных цифр.

В переписке Мерсенна и Ферма были высказаны ещё несколько идей относительно простых чисел.

Так Ферма обнаружил, что если целое число а не делится нацело на простое число p, то число ap—1 — 1 всегда делится на p (Малая теорема Ферма):

Теорема 1.6. (Малая теорема Ферма) Пусть п-простое число. Тогда для любого положительного а, не являющегося кратным п, выполняется условие

an—1 = 1 mod п. (1.5)

Это условие лежит в основе многих тестов на простоту, которые исследовались известными учеными всего мира, в том числе Эйлером, Лежан-дром и Гауссом. Огромное количество результатов, связанных с простыми числами, было получено Леонардом Эйлером. В частности, Эйлер обобщил малую теорему Ферма. На малой теореме Ферма и теореме Эйлера основаны несколько тестов простоты. Рассмотрим их в следующем параграфе.

Вероятностные тесты простоты

По малой теореме Ферма для всех простых чисел п и положительных целых чисел а, взаимно-простых с п, выполняется условие (1.5). Поскольку для большинства составных чисел это условие не выполняется, то мы имеем простейший тест, отделяющий простые числа от большинства составных. Параметр а используемый в соотношении (1.5) называется базой.

Лейбниц, знаменитый математик и философ, считал, что выбирая а = 2 в качестве базы, можно использовать теорему Ферма для доказательства простоты чисел.К сожалению, Лейбниц был неправ, поскольку существуют числа, дающие ложный "положительный" результат в данном тесте.

Составное число п, для которого (1.5) истинно, называется псевдопростым по базе а. Фактически, псевдопростые числа - это числа, на которых тест Ферма дает ошибку, трактуя составные числа как вероятно простые.

Определение 1.1. Нечетное составное натуральное число п, удовлетворяющее сравнению (1.5) для некоторого целого а, где 0 < а < п — 1 называется псевдопростым по базе а, кратко, ПП(а)-числом.

Теорема 1.7. (Етйдв). Для каждого натурального числа а > 2 количество псевдопростых чисел по основанию а, которые не превосходят х, есть д(п(х)) при х ^ ж. Иными словами, псевдопростые числа встречаются редко по сравнению с простыми числами.

Для псевдопростых чисел, определенных отношением (1.5), эта теорема была впервые доказана Эрдёшом в статье [38]. Теорема еще раз говорит о том, что использование сравнения Ферма может быть очень результативным при распознавании простоты натурального числа. Однако это было известно уже в 17 веке, задолго до появления доказательства Эрдёша благодаря практическому использованию сравнения.

Для уменьшения вероятности ошибочного заключения, можно выполнить проверку соотношения (1.5) на нескольких различных значениях а,

16

однако полностью отсечь составные числа таким образом не удается, поскольку существуют составные числа, которые являются псевдопростыми по всем основаниям а. Впервые пример таких чисел привел математик Р.Д. Кармайкл(Caгmichael) в своей работе, опубликованной в 1912 году [35]. Поэтому они и называются числами Кармайкла.

Определение 1.2. Составные натуральные числа п, для которых при всех натуральных а, 1 < а < п, взаимно-простых с п, выполнено сравнение (1.5), называются числами Кармайкла.

Из этого определения следует, что числа Кармайкла являются псевдопростыми по любой базе а. Кармайкл в данной работе выписал 15 таких чисел и доказал, что каждое такое число является произведением не менее трех простых сомножителей. Наименьшим число Кармайкла является п = 561 = 3 • 11 • 17.

Также Кармайкл высказал гипотезу о том, что чисел Кармайкла -бесконечно много. Позднее выяснилось, что доказательство этого утверждения - очень трудная проблема. Причина высокой сложности задачи в том, что такие числа встречаются достаточно редко. Например, на интервале от 1 до 109 можно найти только 646 чисел Кармайкла, в то время как простых - 50847534. Проблему решили Альфорд, Грэнвилль и Поме-ранс лишь в 1994 году [26], доказав, что существует бесконечное множество чисел Кармайкла.

Числа Кармайкла имеют интересную характеристику, которую впервые опубликовал А.Корсельт в 1899 году за 13 лет до того, как Кармайкл привел пример такого числа. О

Теорема 1.8. (Критерий Корсельта) Целое число п является числом Кармайкла тогда и только тогда, когда оно положительное, составное, не содержит среди своих делителей квадратов и для каждого простого числа р, делящего п, число р — 1 делит п — 1.

17

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

Интересные свойства чисел Кармайкла были найдены Арнаутом [29], [30] и Альфордом [27], [39].

Тесты простоты, отсекающие числа Кармайкла. Тест Лемера

Первым алгоритмом, лишённым недостатка теста Ферма, был тест, предложенный Лемером в 1976 [46]. Этот тест распознавал числа Кармайкла и отсеивал их как составные. Тест Лемера основан на свойствах символов Лежандра и Якоби.

Пусть число n - простое, тогда по малой теореме Ферма an—1 = 1 mod n для всех a, не кратных n. Существует два квадратных корня из 1 по модулю n, 1 и n — 1, поэтому

n—i /a\ , ,

a 2 = = ±1 mod n (1.6)

n

Для составных чисел n формула (1.6) выполняется сравнительно редко. Сам Лемер называл составные числа, удовлетворяющие (1.6), строго псевдопростыми по основанию a (это определение строгой псевдопростоты отличается от современного), поэтому будем называть подобные числа числами Лемера. Заметим, что условие (1.6) влечет условие

an—l = 1 mod n,

поэтому каждое число Лемера является псевдопростым.

Тест Лемера. Пусть n > 1 — натуральное число. Если существует целое a, 1 < a < n, такое, что an—1 = 1 (mod n) и для любого простого делителя q числа n — 1 выполнено условие

n—1

a q ф 1 (mod n) 18

то n простое.

Если такого числа а не существует, то n — составное число.

Лемер доказал, что никакое число Кармайкла n не может удовлетворять (1.6) для всех а, взаимно-простых с n. Для доказательства Кармай-кл использовал утверждение, что числа Кармайкла свободны от квадратов и, значит, представляет собой произведение различных простых чисел n = pi • Р2 • ■■■ • Pt.

Тест Соловея—Штрассена

Недостаток теста Ферма также устраняется в вероятностном тесте Соловея-Штрассена(8о1оуау and Strassen) [52]. Этот тест базируется на критерии Эйлера и, фактически, переформулирует тест Лемера.

Теорема 1.9. Пусть n- нечетно. Число n является простым тогда и только тогда, когда для всех а Е Z*n выполнено условие

а{п-1)/2 = ( а | mod n (1.7)

w

Доказательство. (Более подробное доказательство можно найти в лекциях Золотых [18]). Если n- простое, то условие (1.7) выполнено в силу критерия Эйлера. Пусть n-нечетное число, удовлетворяющее (1.7). Предположим противное, и число n-составное. Тогда, для всех а Е Zn выполняется условие

ап— mod n = 1,

и, значит, n - число Кармайкла. Но по критерию Лемера никакое число Кармайкла не может удовлетворять условию (1.7), это противоречит выбору n.

Тест Соловея-Штрассена обладает значительным преимуществом по сравнению с тестом Ферма. Во-первых, он является менее трудоемким и, после выполнения теста k раз, вероятность ошибки не превосходит (0, 5)k.

Среди 203 миллиона простых чисел, меньших 232, псевдопростых по основанию 2 всего 10403, из них тест Соловея-Штрассена проходят 5367 чисел.

Но на практике степень достоверности теста Соловея-Штрассена не является достаточной. Тест Миллера-Рабина сильнее теста Соловея—Штрассена. Точнее, если при фиксированном a число n проходит тест Миллера-Рабина как вероятно простое, то оно проходит тест Соловея-Штрассена с тем же результатом.

Критерии простоты, основанные на малой теореме Ферма, были также найдены и исследованы Брильхартом, Лемером и Серфриджем [34].

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

Этот тест был разработан в 1976 году Гарри Миллером [49] и модифицирован в 1980 году Майклом Рабиным [55]. Тест Миллера был детерминированным, но опирался на недоказанную обобщенную гипотезу Римана ОГР. Рабин избавился от использования ОГР, но сделал тест вероятностным.

Напомним определение двух функций, введенных в первом параграфе:

Определение 1.3. Пусть n - произвольное натуральное число. Представим n в виде произведения четной и нечетной частей n = 2s•и. Определим функции bin(n) = s и odd(n) = и.

Определение 1.4. Пусть n - нечетное число, и a - целое число, удовлетворяющее неравенству 1 < a < n. Назовем a свидетелем простоты n, если выполняется одно из следующих двух условий:

1b = aodd(n-1) = 1 mod n, , х

< (1.8) 2. (3i) 0 < i < bin(n — 1) b2 = —1 mod n.

Приведем пример. Пусть n =13 и a = 2. Проверим, является ли 2 свидетелем простоты n = 13. Представим n — 1 = 12 в виде 12 = 22 • 3,

тогда bin(n — 1) = 2, odd(n — 1) = 3. Проверим условия (1.8):

1.b = 23 = 1 mod 13,

2. (3i) 0 < i< 2) 82 ф —1 mod 13.

Первое из условий (1.8) не выполнено, но выполнено второе условие: 82 = 64 = — 1 mod 13. Значит, число n - вероятно простое.

Список литературы диссертационного исследования кандидат наук Мубараков Булат Газинурович, 2021 год

Литература

[1] Ishmukhametov S., Mubarakov B. On practical aspects of the Miller-Rabin Primality Test // Lobachevskii Journal of Mathematics.- 2013.- Vol.34 (4).-Р.304-312.(ВАК, Scopus, WoS) (авт. вклад - 0,28 п.л.).

[2] Mubarakov B.G., Mochalov A.S., Rubtsova R.G. Investigation of Distribution of Pseudosimple Numbers // Research Journal of Applied Sciences.- 2015.- Vol.10 (8).- P.358-364. (Scopus) (авт. вклад - 0,15 п.л.).

[3] Каратаев О.Р., Мубараков Б.Г., Мочалов А.С. О повышении эффективности теста простоты Миллера-Рабина// Вестник Казанского технологического университета. - 2015. - Т.18, №17. - C.183-186. (ВАК) (авт. вклад - 0,1 п.л.).

[4] Ишмухаметов Ш.Т., Мубараков Б.Г., Камаль Маад Аль-Анни Вычисление коэффициентов Безу для k-арного алгоритма нахождения НОД // Известия высших учебных заведений. Математика.- 2017.- №11.- C.30-38. (Scopus, WoS, ВАК) (авт. вклад - 0,19 п.л.).

[5] Ishmukhametov S.T., Mubarakov B.G., Rubtsova R.G. On the number of witnesses in the Miller-Rabin primality test // Symmetry. - 2020. - Vol.12 (6). - Номер статьи 890. (Scopus), (авт. вклад - 0,25 п.л.)

[6] Мубараков Б.Г. Исследование рядов простых чисел. // Информационные технологии в системе социально-экономической безопасности России и ее регионов: труды IV Всероссийской научной конференции, Казань, 23-26 апреля 2012 г. / науч. ред. Голицына И.Н. - Казань: КФУ, 2012. -С.158-162.

[7] Мубараков Б.Г. Исследование строго псевдопростых чисел / Сборник трудов II Всероссийского конгресса молодых ученых / гл. ред.: В.О. Никифоров. Вып.2.- Санкт-Петербург: ИТМО, 2013. - С.291-293.

[8] Мубараков Б.Г. О выводе частичных сумм рядов по простым числам / Итоговая научно-образовательная конференция студентов Казанского федерального университета 2012 года: сборник статей. В Т.5. Институт математики и механики им. Н.И. Лобачевского, Институт вычислительной математики и информационных технологий, Институт управления и территориального развития, Институт физики. - Казань: Казан. ун-т, 2012.-С.57-62.

[9] Ишмухаметов Ш.Т., Мубараков Б.Г., Рубцова Р.Г. О проблеме нахождения строго псевдопростых чисел //Информационная безопасность в свете Стратегии Казахстан-2050: сборник трудов I Международной научно-практической конференции (12 сентября 2013 г., Астана). - Астана: Евразийский национальный университет им.Л.Н.Гумилева, 2013. - С.349-353, (авт. вклад - 0,1 п.л.)

[10] Ишмухаметов Ш.Т., Мубараков Б.Г. Об одном классе строго псевдопростых чисел // Эвристические алгоритмы и распределенные вычисления. - 2014. - Т.1, №1. - C.64-73 (авт. вклад - 0,3 п.л.).

[11] Mubarakov B.G., Ishmukhametov Sh.T., Mochalov A.S. Euclidean algorithm for recurrent sequences // Applied Discrete Mathematics and Heuristic Algorithms. - 2015. - Vol.1 (1). - P.23-28 (авт. вклад - 0,13 п.л.).

[12] Мубараков Б.Г. Эффективная оценка теста простоты Миллера-Рабина натуральных чисел / Труды Математического центра имени Н.И.Лобачевского. Т.59 / "Лобачевские чтения - 2020"// Материалы XIX Всероссийской молодежной научной школы-конференции - Казань: Изд-во Академии наук РТ, 2020. - Т.59. - С.106-109.

100

[13] 13. Ishmukhametov S., Rubtsova R., Mubarakov B., Arkan M. On a new algorithm for Computing GCD of integer numbers // Trends in Computer Science and Information Technology. - 2020. - Vol.5 (1). - P.15-17, (авт. вклад - 0,05 п.л.)

[14] Арнольд В.И. Группы Эйлера и арифметика геометрических прогрессий , М.МЦНМО, 2003

[15] Василенко О.Н. Современные способы проверки простоты чисел. Обзор, 1988, Кибернетич. сборн., Вып. 25, С. 162-188

[16] Василенко О.Н. Теоретико-числовые алгоритмы в криптографии, М.: 2003, 328 с.

[17] Гашков С.Б. Упрощенное обоснование вероятностного теста Миллера- Рабина для проверки простоты чисел. Дискрет. матем., 10:4 (1998), p.35—38

[18] Золотых Н.Ю. Лекции по компьютерной алгебре. http://www.uic.unn.ru/ zny/compalg/

[19] Ишмухаметов Ш.Т. Методы факторизации натуральных чисел. - Казанский федеральный университет, Казань, 2011. - 189 c.

[20] Ишмухаметов Ш.Т., Шарифуллина Ф. Ф. О распределении полупростых чисел, Изв. вузов. Математика, 2014, № 8, с.53-59

[21] Ю. В. Нестеренко. Глава 4.4. Как отличить составное число от простого // Введение в криптографию / Под ред. В. В. Ященко. — Питер, 2001. — 288 с.

[22] Чандрасекхаран К. Введение в аналитическую теорию чисел// М.: Мир, 1974ю

[23] Шнайер Б. 3.11.5. Генерация простых чисел // Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си = Applied Cryptography. Protocols, Algorithms and Source Code in C. — М.: Триумф,

2002. — С. 296—300

[24] Agrawal, M., Kayal, N., Saxena, N. PRIMES is in P, Annals of Mathematics. 160 (2).- p.781--793.

[25] L.Adleman, C.Pomerance, R.Rumely. On distinguishing prime numbers from composite numbers, 1983, Ann. Math. V. 117, p. 173—-206

[26] Alford, W.R., Granville A., Pomerance C. On the difficulty of finding reliable witnesses. In Algorithmic Number Theory, First Internat. Symp., ANTS-I; Lecture Notes in Computer Science; Springer: Berlin/Heidelberg, Germany, 1994; p. 116.

[27] W. R. Alford, A. Granville, C. Pomerance. There are Infinitely Many Carmichael Numbers, Annals of Mathematics, 139 , 1994, P.703-722

[28] Amer I., Ishmukhametov, S.T., Rubtsova R.G. Lenstra Factorization Method Convergence Investigation on Elliptic Curves, Research Journal of Applied Sciences 10 (8), 2015, p. 365-370

[29] Arnault, F. Rabin-Miller primality test: composite numbers which pass it, J. Symb. Comput. 1995, 64,p. 355-361.

[30] Arnault, F. Constructing Carmichael numbers which are strong pseudoprimes to several bases. J. Symb. Comput. 1995, 20, 151-161.

[31] A.O.L. Atkin, D. J. Berstein. Prime sieves using binary quadratic forms,

2003, Math. Comp. V. 73 (273), p. 1—8.

[32] A.O.L. Atkin, F. Morain, Elliptic curves and primality proving, 1993, Math. Comp. V. 61 (203), p. 29—67.

[33] E.Bach. Analytic methods in the analysis and design of number-theoretic algorithms, 1985, Cambridge, MA: MIT Press, 48p.

[34] Brillhart J., Lehmer D.H., Selfridge J. New Primality Criteria and Factorizations of 2m ± 1 // Mathematics of Computation. — 1975. — Vol. 29. 130. — p. 620—647.

[35] R.Carmichael. On composite numbers P which satisfy the Fermat congruence aP-1 = 1 (mod P), 1912, The Amer. Math. Monthly 19, pp.2227

[36] Crandall R., Pomerance C. The prime numbers: a computational perspertive // sec.ed. Springer-Verlag, Berlin, 2005, 604 p.

[37] Damgard, I., Landrock, P., Pomerance, C. Average case error estimates for the strong probable prime test. Math. Comput. 1993, 61, p.177-194.

[38] Erdos, P. On almost primes, 1950, Amer. Math. Monthly 57, p. 404-407

[39] Erdos, P. On Pseudoprimes and Carmichael numbers, Publ. Math. Debrecent, 4, 1956, p. 201-206

[40] Erdos, P., Pomerance, C. On the number of false witnesses for a composite number. Math. Comput., 1986, 46,p. 259-279.

[41] Goldwasser S., Kilian J.. Almost all primes can be quickly certified, 1986, Proc. 18-th Ann. ACM Symp. on Theory of Computing, p. 316—329.

[42] Hardy G. H., Wright E. M. An Introduction to the Theory of Numbers, 6-th ed (2008), Oxford: Clarendon Press.

[43] Ishmukhametov S., Sharifullina F. About Power Smooth Numbers, Research

Journal of Applied Sciences 10 (8), 2015, p. 381-384 Ishmukhametov S.,

Rubtsova R., Savelyev N. The Error Probability of the Miller-Rabin Primality

Test, Lobachevskii Journal of Mathematics, 2018, Vol. 39, no.7, p. 1010-1015

103

[44] Jaeschke G. On Strong Pseudoprimes to Several Bases. Math. Comput. 61, 1993, p. 915-926 Univ.Wisc-Madison Tecn.Report,20p.

[45] Jiang J., Deng Y. Strong pseudoprimes to the first 9 prime bases. arXiv:1207.0063v1 [math.NT], June 30, 2012, 12 p.

[46] Lehmer D. Strong Carmichael numbers, 1976, J. Austral. Math. Soc. Ser. A, v.21, pp. 508-510

[47] Lenstra H. Primality testing algorithms (after Adleman, Rumely and Williams), 1981, Bourbaki Seminar. V. 1980/81. (Lect. Notes in Math.; V. 901), pp. 243—257

[48] Maximov K.L., Ishmukhametov S.T. About algorithm of smooth numbers calculation, Research Journal of Applied Sciences 10 (8), 2015, p. 376-380,

[49] Miller G. Riemann's hypothesis and tests for primality, 1976, J. Comput. and Syst. Sci. 1976. V. 13, p. 300—317

[50] Monier L. Evaluation and comparision of two efficient probabilistic primality testing algorithms, 1980, Theor. Comput. Sci. V. 12, p. 97—108

[51] Pomerance, C., Selfridge, J. L., and Wagstaff, S. S. The Pseudoprimes to 25 • 109, Mathematics of Computation, 35, 1980, p. 1003-1026.

[52] Solovay R., Strassen V. A fast Monte-Carlo test for primality, 1977, SIAM J. Comput., v. 6, pp. 84-85

[53] Pomerance, C. On the Distribution of Pseudoprimes, Mathematics of Computation, 37 (156), 1980, p. 587-593

[54] P. Pritchard. A sublinear additive sieve for finding prime numbers. Comm. ACM, 24, 1981, p.18-23.

[55] Rabin M. O. Probabilistic algorithm for testing primality //J. Number

Theor. / D. Goss — Elsevier, 1980, 12 (1), 128-138 7 104w

[56] Washington L. Elliptic Curves: Number Theory and Cryptography, 2-d Ed. (Discrete Mathematics and Its Applications), CRC Press.

[57] Zhang, Z. Finding strong pseudoprimes to several bases. Math. Comput. 2001, 70, 863-872.

[58] Prime Number Theorem. Wikipedia, https://en.wikipedia.org/wiki/Prime_number_theorem#Prime_ number_theorem_for_arithmetic_progressions.

ПРИЛОЖЕНИЯ. Библиотека вспомогательных программ на языке Python

Тексты программ, использованных в диссертации

#Файл MyLib.py

from random import randint from math import sqrt from array import * from itertools import * import time import sys

#Начальный интервал простых чисел

Pr=[2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,

73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,

157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,

239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,

331,337, 347,349,353,359,367,373,379,383,389,397,401,409,419,

421,431,433,439,443,449,457,461,463,467,479,487,491,499,503,

509,521,523,541,547,557,563,569,571,577,587,593,599,601,607,

613,617,619,631,641,643,647,653,659,661,673,677,683,691,701,

709,719,727,733,739,743,751,757,761,769,773,787,797,809,811,

821,823,827,829,839,853,857,859,863,877,881,883,887,907,911,

919,929,937,941,947,953,967,971,977,983,991,997,1009]

f=open('ans.txt','w')

#--- Предварительно вычисленные значения функции Nw(d) для

#d=GCD(p-1,q-1)полупростых чисел n=pq NW=[1,2,6,18,22,50,54,98,86,162,150,242,198,338,294,450, 342,578,486,722,550,882,726,1058,774,1250,1014,1458,1078, 1682,1350,1922,1366,2178,1734,2450,1782,2738,2166,3042, 2150,3362,2646,3698,2662,4050,3174,4418,3078,4802,3750] Q=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] #15 I=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] #15 I=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] #15

DD=[1,7,9,23,25,47,41,79,73,119,97,167,145,223,169,287,241,

359,273,439,361,527,385,623,505,727,537,839,673,959,681,1087,

865,1223,889,1367,1081,1519,1073,1679,1321,1847,1329,2023,

1585,2207,1537,2399,1873]

FS=[1,2,6,22,86,342,1366,5462,21846]

def FilDD():

d=4;i=1;e=4 while d<=100: s=0

while e%2==0:

e=e//2; s+=1 DD[i]=e*e*FS[s]//2-2 d+=2;e=d;i+=1 for i in range(1,51):

f.write(str(DD[i])+',') return

def FindDD(d): s=0;e=d while e%2==0:

e=e//2; s+=1 f=e*e*FS[s]//2-2 return f

def GCD(a,b): if a<b:

c=a;a=b;b=c while b>0:

a,b=b,a%b return a

def GCD_ext(num1, num2): if num1 == 0:

return (num2, 0, 1)

else:

div, x, y = GCD_ext(num2 % numl, numl) return (div, y - (num2 // numl) * x, x)

def PowMod(a,k, n): b=1

while k>0:

if k%2==0: k=k//2 a=(a*a) %n else:

k-=1

b = (b*a)%n

return b

def MR(n, k): if n%2==0:

return 0 b=n-1;s=0 while b%2==0: s+=1

b=int(b/2) for j in range(0, k): sg=0

a = Pr[j] d = PowMod(a,b,n) if d==1: sg=1

continue if d==n-1: sg=1

continue

s1=s

while s1>=1: s1-=1

d=(d*d)%n if d==n-1: sg=1 break if sg==0:

return 0

return 1

def MR2(n, a): b=n-1;s=0 while b%2==0: s+=1

b=int(b/2) d = PowMod(a,b,n) if d==1 or d==n-1:

return 1 while s>=1: s-=1

d=(d*d)%n if d==n-1: return 1

return 0

def Euler(n):

phi=n;i=0;p=2 while p<=phi:

if n%Pr[i]==0:

phi=phi*(p-1)//p i+=1;p=Pr[i] return phi

def WitTable(B): #

Table of function Nw for d<=B d=2

while d<=B:

s=0;m=1;d2=d

while d2%2==0: d2=d2//2 s+=1;m*=4 Nw=int(d2*d2*(m+2)/3) f.write(str(Nw)+',') d+=2

def Per(k,X,Lim): #

S1=0.;n1=0;ti=k;S=0.;n=0;SS=0.;nn=0;ff=0 for i in range (1,k+1): I[i]=i

if i+3<=Lim:

Q[i]=Pr[i+3] if i+4>Lim:

p=Pr[Lim+4]

p1=FindNext(p)

Lim+=1

Pr.append(p1)

ff=0 while 1:

S1,n1=Act(Q,k,X,ff) if S1==1 and n1==0:

f.write('Stop!\n');break; if S1==2 and n1==0: ti=k-1

while ti>0 and I[ti]+1==I[ti+1]: ti-=1 if ti==0:

return S,n I[ti]+=1

if I[ti]+3<=Lim:

Q[ti]=Pr[I[ti]+3] else:

Q[ti]=FindNext(Q[ti]) for i in range(ti+1,k+1): I[i]=I[i-1]+1

if I[i]+3<=Lim:

Q[i]=Pr[I[i]+3] else:

Q[i]=FindNext(Q[i-1])

continue

n+=n1;S+=S1;ff=0 I[k]+=1

if I[k]+3<Lim:

Q[k]=Pr[I[k]+3] else:

Q[k]=FindNext(Q[k]) return S,n

def FindNext(p): k=0

while k==0: p+=2

k=MR(p,2); return p

# Q a transformation #of(p1,p2,...,pk)to(pi1,pi2,...,pik)

def Act(Q,k,X,f):

n=1;ti=k;Nn=0;SS=0 for i in range (1,k+1):

n*=Q[i]; DQ[i]=1 if n>X and f==1:

return 1,0 # finish if n>X:

return 2,0 # continue

T=1

for h in range (1,k): T*=4

while n<=X and ti>0:

ss=1000;DT=1; EF=n Pd=1

for i in range(1,k+1):

p=Q[i]

EF=EF*(p-1)//p # Ef = Euler Function n1=n//(DQ[i]*p) d=GCD(p-1,n1-1) if d==2:

ss=1;d=1 else: s=0

while d%2==0:

d=d//2; s+=1 Pd*=d # Product of all odd(d_i) if s<ss:

ss=s # Find s=min {bin(d_i)} for i in range(0,ss):

DT*=T; W=Pd*(1+(DT-1)//(T-1)) if W!=2:

SS+=W/EF Nn+=1 p=Q[k] if p*n<=X:

n*=p;DQ[k]*=p;continue

ti=k

while Q[ti]*n>X and ti>0: n//=DQ[ti];DQ[ti]=1 ti-=1 if ti==0:

return SS,Nn n*=Q[ti];DQ[ti]=1 return SS,Nn

def Act2(Q,V,X): # used for k=2

S=0;Nn=0;T=4; p1=Q[1];p2=Q[2] n=p1*p2;DT=4;D1=p1 if n>X and V[2]-V[1]==1:

return 1,1 if n>X:

return 0,0 while 1:

ss=1000; EF=n

EF=n*(p1-1)*(p2-1)//p1//p2 # Euler's function

d1=GCD(p1-1,n//D1-1);s=0

while d1%2==0:

d1=d1//2; s+=1 if ss>s: ss=s

d2=GCD(p2-1,D1-1);s=0 while d2%2==0:

d2=d2//2; s+=1 if ss>s: ss=s W=d1*d2*FS[ss] S+=W/EF;Nn+=1 if p2*n<=X:

n*=p2;continue D1*=p1;n=D1*p2 if n>X: break return S,Nn

def Act3(Q,X): S=0;Nn=0;T=4 p1=Q[1];p2=Q[2];n=p1*p2 if n>X and Q[2]==FindNext(Q[1]):

return -1,0 if n>X:

return -1,1 d=GCD(p1-1,p2-1); if d==2:

return 0,1

s=0

while d%2==0:

d=d//2; s+=1 W=d*d*FS[s]/2-2 EF=n*(p1-1)*(p2-1)//p1//p2; return W/EF,1

def Avg2(i,p1,p2,X): S=0;N=0;n=p1*p2 while n<=X: N+=1

d=GCD(p1-1,p2-1) if d==2: i+=1 if i<=168:

p2=Pr[i] else:

p2=FindNext(p2) n=p1*p2 continue if d<100:

ii=(d-2)//2;W=DD[ii] else:

W=FindDD(d) EF=(p1-1)*(p2-1);S+= W/EF i+=1 if i<=168:

p2=Pr[i] else:

p2=FindNext(p2) n=p1*p2

return S,N

Описания процедур, входящих в пакет компьютерных программ

Pr[168] - массив простых чисел от 2 до 1009.

NW[ ] - массив значения функции Nw(d/2), равной числу свидетелей для полупростого числа n = pq по НОД d = GCD(p — 1,q — 1). Используется для ускорения вычисления не модифицированной средней частоты. DD[ ] - массив числа нетривиальных свидетелей для полупростых чисел n = pq, DD[(d — 4)/2] = NW2(n), d = GCD(p — 1,q — 1). FS[ ] - массив предварительно вычисленных значений функции

4s — 1

FS (s) = 1 + -^-,

входящей в формулу числа свидетелей полупростого числа. def FilDD() - функция, используемая для построения массива DD (см. выше). Сохраняет найденные значения в файл.

def FindDD(d)- функция, используемая для вычисления числа свидетелей для аргументов, превышающих значения, для которых значения сохранены в массиве DD.

def GCD(a,b) - процедура вычисления НОД по алгоритму Евклида.

def GCD_ext(num1, num2)- процедура, реализующая расширенный алгоритм Евклида. Используется для вычисления обратных по модулю элементов.

def PowMod(a,k, n)- вычисляет ak mod n по быстрому алгоритму возведения в степень.

def MR(n, k)- процедура проверки нечетного числа n на простоту с использованием k раундов теста Миллера - Рабина. Параметры a берутся

последовательно из множества простых чисел Pr.

115

def МК2(п, а) - процедура проверки нечетного числа п на простоту с использованием одного раунда теста Миллера - Рабина с заданным значением параметра а.

def Еи1ег(п) - функция Эйлера. Вычисление производится по формуле

где произведение берется по всем простым делителям п.

def "^1ТаЫе(В) - процедура, используемая для заполнения массива NW (см. выше).

def Рег(к,Х,Ыш) - первая основная процедура алгоритма вычисления средней частоты. Выполняет следующие операции:

1. Заполняется исходную выборку 1[ ] последовательными элементами 1, 2,... к. В дальнейшем по описанному в главе 4 алгоритму выполняется перебор всяких выборок (г\, г2, ... ги) из к элементов с учетом ограничения

2. Заполняется массив Q[ ] последовательными простыми числами, начиная с p = 11: Q = [11,13,... Pr[k + 4]].

3. Вызывает процедуру Act, которая строит всевозможные наборы степеней

(ri, i2, ... rk) для заданной выборки (q1, q2, ... qk) с учетом ограничения

Массив РЯ состоит из текущих значений степеней минус 1 РЯЩ = Т{ — 1. Такое хранение показателей степеней используется для удобства перебора всех показателей степеней и перехода от одного значения п к следующему.

def РМ^х^р)- ищет следующее за р простое число.

Ргг • Pi2 • .. .Ргк < X.

n = qi1 • q22 • ...qrkk < X.

def Act(Q,k,X,f) - вторая основная процедура алгоритма вычисления средней частоты. Выполняется перебор показателей степеней выборки Q по алгоритму, описанному в главе 4. Строит последовательность чисел n и вычисляет число свидетелей n, вычисляет частоту f = Fr(n), суммирует частоты и возвращает сумму частот и количество обработанных значений n для последующего вычисления средней частоты.

def Act2(Q,V,X) - выполняет те же задачи, что и процедура Act(Q,k,X,f), но содержит упрощенный алгоритм для случая полупростых чисел. Работает быстрее, чем общая процедура.

def Act3(Q,X) - выполняет те же задачи, что и процедура Act(Q,k,X,f), но содержит упрощенный алгоритм для случая полупростых чисел. Работает быстрее, чем общая процедура и Act2(Q,V,X).

def Avg2(i,p1,p2,X) - процедура, которая по заданной паре простых чисел (p1,p2) и ограничителю X перебирает последующие пары простых чисел (порядок однозначно определен алгоритмом главы 4), вычисляет n = p1p2, находит число свидетелей Nw(n), функцию Эйлера ф(п), вычисляет частоту, суммирует частоту S и количество N рассмотренных чисел. Возвращает сумму частот S и количество N.