X Международная студенческая научная конференция Студенческий научный форум - 2018

Необходимость рассмотрения псевдопростых чисел возникла с развитием теории чисел в целом. Вопрос разделения целых чисел на простые и составные рассматривается в разделе делимости в кольце целых чисел. Под простым числом, в теории чисел, подразумевают: натуральное (целое положительное) число, имеющее ровно два различных натуральных делителя — единицу и самого себя, а под составным - числа, которые имеют более одного делителя. Наряду с этим рассматривают и псевдопростые числа, т.е. натуральные числа, обладающие некоторыми свойствами простых чисел, являясь, тем не менее, составными. Также можно сказать, что в зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел: псевдопростые Ферма, псевдопростые Эйлера — Якоби, псевдопростые Фибоначчи и т.д..

Назовем составное нечетное число n псевдопростым по основанию a, если пара чисел a,n удовлетворяет сравнению Ферма = 1(mod n)a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {displaystyle textstyle a^{(n-1)/2}equiv left({frac {a}{n}}right){pmod {n}}}

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

В рамках данной статьи рассмотрим псевдопростые числа Ферма. Названы в честь французского математика, одного из создателей аналитической геометрии и теории чисел, Пьера Ферма (1601-1665). Тест простоты Ферма в теории чисел — это тест простоты натурального числа n, основанный на малой теореме Ферма. Как известно, эта теорема утверждает, что если n – простое, то для всех a, взаимно простых с n, выполняется условие (сравнение Ферма): = 1(mod n) [1].a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {displaystyle textstyle a^{(n-1)/2}equiv left({frac {a}{n}}right){pmod {n}}}

Таким образом, если сравнение Ферма не выполнено, хотя бы для одного числа из множества , то a – составное.

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

В этой связи, разработаны и применяются на практике вероятностные тесты, свободные от указанного недостатка, один из которых тест Соловея — Штрассена, который опирается на малую теорему Ферма и свойства символа Якоби. В самом тесте при тестировании числа n вычисляется символ Якоби a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {displaystyle textstyle a^{(n-1)/2}equiv left({frac {a}{n}}right){pmod {n}}}

Если n — нечетное составное число, то количество целых чисел , взаимнопростых с и меньших , удовлетворяющих сравнению a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {displaystyle textstyle a^{(n-1)/2}equiv left({frac {a}{n}}right){pmod {n}}} (mod n) , не превосходит n 2 {displaystyle {frac {n}{2}}}. Поэтому можно утверждать, что составные числа n называются псевдопростыми Эйлера-Якоби по основанию a, так как они удовлетворяют данное сравнение [2].

Вероятностный тест Соловея – Штрассена, предназначенный для проверки чисел на простоту, был открыт в 1970-х годах Робертом Мартином Соловеем и Фолькером Штрассеном. Основной его задачей является корректное определение того, что простое число является простым, однако для составных чисел с некоторой вероятностью он может дать неверный ответ.

Алгоритм Соловея — Штрассена.

Выбирается случайное число и проверяется условие

Если условие пункта 1 верно, следовательно, ответ «n-составное».

Проверяется справедливость сравнения a ( n − 1 ) / 2 ≡ ( a n ) ( mod n ) {displaystyle textstyle a^{(n-1)/2}equiv left({frac {a}{n}}right){pmod {n}}} (mod n).

Если условие пункта 3 не верно, следовательно, ответ «n-составное».

Если условие пункта 3 верно, следовательно, a является свидетелем простоты числа n

После необходимо выбрать другое случайное число а и повторить алгоритм k раз с условием того, что число является простым с вероятностью [3].

СС С праноаноПроверим число n=17 на простоту с помощью теста Соловея-Штрассена. Выберем параметр точности k=2

k=1

Выберем случайное число

Проверим условие

НОД (13,17)=1;следоватеьно проверяем выполнение сравнения (mod n)

r = = =1

s = = (mod 17)= 1

Получили, что поэтому переходим к следующему циклу.

k=2

Выберем случайное число

Проверим условие

;следоватеьно проверяем выполнение сравнения mod n)

r = = =1

s = = (mod 17)= 1

r = s это последний цикл, следовательно, отсюда делаем вывод, что 17- простое число с вероятностью

Таким образом, при повторении теста Соловея-Штрассена раз, вероятность не отбраковки составного числа не превосходит . На практике степень достоверности теста Соловея — Штрассена является не достаточной, так как для составных чисел с некоторой вероятностью он может дать неверный ответ, поэтому чаще всего используют другие методы, например, тест Миллера-Рабина [3].

Список используемых источников

Коблиц Н., Курс теории чисел и криптографии. — 2-ое. — М.: Научное издательство ТВП, 2001. — С. 149 - 160. — 254 с.

Молдовян, Н.А.Криптография : от примитивов к синтезу алгоритмов: науч. изд. / Н. А. Молдовян, А. А. Молдовян, М. А. Еремеев. - СПб. : БХВ-Петербург, 2004 (Отпеч. в ГУП тип. Наука). - 446 с.

Нестеренко, А.Ю. Введение в современную криптографию. Теоретико-числовые алгоритмы: Курс лекций для специалистов и магистрантов высших учебных заведений. / А.Ю. Нестеренко. — М.: 2011. — С. 79 - 90. — 190 с.

Код для цитирования: Скопировать