СТОХАСТИЧЕСКИЙ АНАЛИЗ ТЕСТА ПРОСТОТЫ ФЕРМА

I. ВСТУПЛЕНИЕ

А. Вступление

Задача определения простоты числа является одной из самых важных в теории чисел. За всю историю развития математики как науки, ученые не могли найти эффективный способ решения этой задачи. Все изменилось в 1640 году после открытия Малой теоремы Ферма, на основе которой был построен  вероятностный Тест простоты Ферма. В дальнейшем задачей ученых стало доказательство данной теоремы, нахождение ошибок и неточностей в работе теста. За последние 50 лет лет исследования в области теории простых чисел принесли немало открытий. Так в 1970-х годах были открыты вероятностные тесты Миллера-Рабина и Соловея-Штрассена, основанные на открытии Ферма. Но настоящим открытием в данной области стал, предложенный в 2002 году индийскими математиками детерминированный алгоритм полиномиальной сложности, более известный как АКS. Хотя данный алгоритм классифицируется как детерминированный, метод также основан на версии Малой теоремы Ферма.

Б. Стохастический процесс

Стохастический и случайный процесс в математике являются взаимозаменяемыми понятиями. В теории вероятностей данный процесс – это семейство случайных величин, индексируемых некоторым параметром, чаще всего играющих роль времени или координат. [1] Случайный (стохастический) процесс – это процесс, поведение которого не является детерминированным, и последующее состояние такой системы описывается как величины, которые могут быть предсказаны, или случайны. [5] Соответственно в статье будет рассмотрен тест простоты Ферма как функция, результатом которой является вероятностная величина.

II ВЕРОЯТНОСТНЫЕ ТЕСТЫ ПРОСТОТЫ

Тест на простоту представляет собой алгоритм определения того, является ли входное число простым. Из всех разделов математики, это понятие наиболее часто применимо в криптографии. В отличие от целочисленной факторизации, тесты простоты обычно не дают простых факторов, а только указывают, является ли входное число простым или нет. [2]

Все тесты простоты можно разделить на две большие группы: истинные(детерминированные) и вероятностные. Первая группа дает точный результат при определении простоты либо составности числа, при помощи второй получаем результат с некоторой вероятностью. Многие популярные тесты на простоту являются вероятностными. Вероятностные тесты являются более строгими, чем эвристические, в том смысле, что они дают доказуемые границы вероятности предельной точности результата. Среди наиболее известных стоит упомянуть тесты Миллера-Рабина, Ферма, Соловея-Штрассена, Форбениуса.  Эти тесты используют, кроме проверяемого числа n, некоторые другие числа a, которые выбираются случайным образом из некоторого множества. Вероятность ошибки на выходе может быть уменьшена путем повторения теста с несколькими независимо выбранными значениями a.

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

• Выберем случайное число а.
• Далее проверяется некоторое равенство (соответствующее выбранному тесту) с участием a и заданного числа n. Если равенство не может быть верным, то n является составным числом, a определяем как “свидетельство” составности, и прекращаем тестирование.
• В противном случае повторяем с шага 1 до достижения необходимой точности.

III. МАЛАЯ ТЕОРЕМА ФЕРМА

А. Описание

Как известно, Малая теорема ферма гласит о том, что если p простое число, то для любого целого числа a число a p - a кратно p. Данное утверждение в обозначениях модульной арифметики можно выразить следующим образом:

a^p ≡ a (mod p)                                                                  (1)

Проверем выполнение равенства (1) на практике. Возьмём для наглядного примера числа a = 4 и p = 5. При возведении a в степень p получим 105 = 1024. Переносим значение a по модулю p в левую сторону выражения 1024 - 4 = 1020. Полученное значение является целым числом кратным значению модуля p (5 × 204 = 1020).

Также данную теорему можно выразить по-другому. При условии, что a не делится на p, формула (1) принимает следующий вид:

a ^p-1 ≡ 1(mod p)                                                               (2)

Возьмём все те же a = 4 и p = 5. то 4 ^5-1 = 1(mod 5), а 256 -1 = 255 = 0 (mod 5) = 5 × 51, таким образом 255, кратно 5 (модулю p). В словесной форме это будет звучать следующим образом: если р – простое число, то для любого натурального а, не делящегося на р, разность а^р-1-1 делится на р.

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

Малая теорема Ферма является основой теста простоты Ферма и одним из фундаментальных результатов иcследований в теории элементарных чисел. Теорема названа в честь Пьера де Ферма, которую он сформулировал в 1640 году. Она называется «малой теоремой», чтобы избежать отождествления с последней теоремой Ферма.

Б. Обобщение

Малая теорема Ферма – это частный случай теоремы Эйлера. Для доказательства этого утверждения достаточно провести пару не сложных вычислений: для любого модуля n и любого целого a взаимно простого с n:

φ (n) ≡ 1 (mod n)                                                                (3)

где φ (n) обозначает конечную функцию Эйлера (которая подсчитывает целые числа от 1 до n, взаимно простые с n).

Теорема Эйлера действительно является обобщением потому, что если n – простое число, то φ (n) = n - 1. Теорема Эйлера включает в себя следующее утверждение: если a, n, x, y являются целыми числами с n положительными и a и n взаимно простыми, то если x, y, то mod φ (n), то a^x ≡ a^y. Это следует из того, что x = y + φ(n) ^k, поэтому a ^x = a ^{y + φ(n)k} = a ^y (a ^φ(n)) ^k ≡ a ^y 1 ^k ≡ a ^y (mod n). [3] Данный частный случай с n-простым числом можно считать следствием Малой теоремы Ферма. В этой форме теорема находит много применений в криптографии и, в частности, лежит в основе вычислений, используемых в методе шифрования открытого ключа RSA. Малая теорема Ферма также связана с функцией Кармайкла и теоремой Кармайкла, а также с теоремой Лагранжа в теории групп.

IV. ВЕРОЯТНОСТНЫЙ АНАЛИЗ ТЕСТА ПРОСТОТЫ ФЕРМА И ЧИСЛА КАРМАЙКЛА

А. Вероятностный анализ теста простоты Ферма

Согласно Малой теореме Ферма, если n простое число и целое число a не делится на n, то:

a ^{n -1} ≡ 1 (mod n)                                                               (4)

Отсюда следует, что если для некоторых значений сравнение (4) нарушается, то можно утверждать, что n является составным.

Исходя из вышесказанного, условие теста простоты можно определить следующим образом: если n  – простое число, то оно удовлетворяет сравнению {\displaystyle a^{n-1}\equiv 1{\pmod {n}}}(4) для любого a, которое не делится на n. Но стоит отметить, что выполнение сравнения (4), является необходимым, но не достаточным условием, для подтверждения простоты. То есть, если найдётся хотя бы одно a, для которого {\displaystyle a^{n-1}\not \equiv 1{\pmod {n}}}сравнение (4) ложно, то число n — составное. Теперь можно прописать вероятностный алгоритм, который отличает составные числа от простых.

1) Мы случайным образом выбираем число a, 1 <a <n и проверяем для этого числа свойство (4).

2) Если оно нарушено, то число n составное.

3) Если сравнение выполнено, возвращаемся к шагу 1.

Что бы определить вероятность ошибки для одного шага алгоритма воспользуемся формулой ꜫ^k, где k – количество итераций, а ꜫ ≤ φ(n)/n , где φ(n) – функция Эйлера (равная количеству натуральных чисел, меньших {\displaystyle n}n и взаимно простых с ним). Вероятность ошибки рассчитывается для составных чисел, так как этот тест может принять составное число за простое, но не наоборот. [6] Очевидно, что с увеличением количества шагов, вероятность ошибки будет стремиться к нулю.

В случае составного числа n, имеющего только большие делители, ꜫ будет приблизительно равна 1, то есть существуют числа, для которых вероятность ошибки при проверке их на простоту тестом Ферма близка к 1. [6] Такие составные числа, которые при прохождении теста Ферма ведут себя как простые называются числами Кармайкла в честь американского математика Роберта Кармайкла. К примеру, составное число n, обладающее свойством (4) для любого целого числа a с условием, что a и N взаимно простые будет считаться числом Кармайкла. Другими словами, число Кармайкла – это составное число n, которое является псевдопростым числом для каждой базы b (b = n-1).

Пример числа Кармайкла: число 1729, которое делится на 7, 13 и 19, но распознается тестом как простое. В связи с тем, что 1728 делится на каждое из чисел 6, 12, 18, с помощью Малой теоремы Ферма легко проверить, что 1729 число Кармайкла. Номер 1729 – третий номер в ряде чисел Кармайкла. Кроме того, 1729 – это число Рамануджана-Харди (наименьшее число, которое можно представить в виде суммы двух кубов двумя способами).

Б. Усовершенствование алгоритма

В 1976 году Миллер предложил заменить тест (4) проверкой несколько других условий. Если n простое число, то n-1 = 2^St, где t нечетно то, согласно Малой теореме Ферма для каждой пары взаимно простых a и n хотя бы одна из скобок в произведении (a^t-1) × (a^t+1) × ( a^2t+1)×…×(a^{2^ s-1}+1)=a ^N-1-1) делится на n.

Целое число a, 1 <a <n считается подходщим для n, если нарушается одно из следующих двух условий:

I) n не делится на a,

II) a^t ≡ 1 mod n или содержит целое k, 0 ≤k < s, такое что a^{(2 ^ k) t} ≡ -1(mod n). [4]

В противном случае, нет подходящих чисел а для простого n. Если n составное число, то согласно теореме Рабина, их не менее ¾ (n-1). Теорема Рабина утверждает, что составное нечетное число n имеет не более φ (n)/4 различных свидетельств простоты, где φ (n) – функция Эйлера. [4]

Теперь можно прописать вероятностный алгоритм, который отличает составные числа от простых.

1) Мы случайным образом выбираем число a, 1 <a <n и проверяем для этого числа свойства I и II.

2) Если хотя бы одно из них нарушено, то число n составное.

3) Если условия I и II выполнены, возвращаемся к шагу 1.

Из сказанного выше следует, что составное число не будет определяться как составное после однократного выполнения шагов 1) – 3) с вероятностью не более ¼. [4] Но вероятностный результат не определяет проверяемое составное число как составное, после k повторений, так как остается вероятность ошибочного результата, не превышающая значения (¼) ^k.

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

V. ВЫВОДЫ

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

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

В современной криптографии тест Ферма в “чистом” виде используется крайне редко. Ученые математики неоднократно занимались исследованием малой теоремы Ферма, многим из них, удалось добиться успеха в усовершенствовании данного теста простоты. Одним из ярких примеров является тест Миллера-Рабина, Соловея-Штрассена и детерменированный AKS тест.

Список литературы:

1. Дуб, Джозеф Лео. Вероятностные процессы / Пер. с англ. Р. Л. Добрушина и А. М. Яглома; Под ред. А. М. Яглома. – Москва: Изд-во иностр. лит., 1956. – 605 с.; – ст. 46 и 47.
2. Поклингтон, Х. С. Определение простоты или составности больших чисел по теореме Ферма, – 1914. – ст. 29-30.
3. Функция Эйлера: статья из Википедии [Электронный ресурс] – Режим свободного доступа: https://ru.wikipedia.org/wiki/Функция_Эйлера
4. Е.О. Черноусова (Ежова). Стохастический анализ в задачах, – 30 с. – ст. 20-21.
5. Стохастический процесс: статья из Википедии [Электронный ресурс] – Режим свободного доступа: https://en.wikipedia.org/wiki/Stochastic_process
6. Ферма, Пьер, Таннери, П.; Генри, C., ред., Творчество Ферма. Том 2. –Париж: Готье-Виллар, – 1894. – ст. 206 - 212.
7. Теоремы Эйлера и Ферма. Тест Ферма на простоту: Статья на сайте Хэлпикс.орг [Электронный ресурс] – Режим свободного доступа: https://helpiks.org/6-5771.html