Простые числа. Сравнение эффективности вероятностных методов определения простоты числа

Цель работы: определение наиболее эффективного метод проверки числа на простоту.

Задачи:

1. Оценить актуальность применения простых чисел.
2. Рассмотреть методы определения простоты чисел.
3. Сравнить их и определить наиболее эффективный.

Введение:

Казалось бы, какое практическое применение могут иметь простые числа? Однако, как бы парадоксально это не звучало, значение простых чисел сложно переоценить. Математики, за все время существования этой науки, сталкиваются с проблемами, связанными с генерацией и предсказанием простых чисел большой разрядности. В этом есть необходимость, так как практическое применение простых чисел очень велико: они повсеместно используются в различных алгоритмах шифрования данных, жизненно необходимы для повседневного использования интернета, объясняют множество явлений, связанных с музыкой, природой и окружающим нас миром. Простые числа, которые «простые» только по математическому определению, являются предметом изучения ученых уже много сотен лет, и до сих пор остаются неизученными. Чего стоит только гипотеза Римана, являющейся задачей тысячелетия, смысл которой состоит в решении вопроса генерации простых чисел высокой разрядности.

Все факторы выше говорят нам о том, что популярность области математики, связанной с простыми числами, очень обоснована. Рассмотрим актуальную в настоящее время сферу применения простых чисел – шифрование. Из курса еще школьной арифметики мы знаем, что простые числа являются своеобразными “атомами” умножения. Любое число может быть представлено произведением некоторых простых чисел. Именно это простое свойство и используют в шифровании информации уже на протяжении почти 50 лет, и, что самое главное, до сих пор не найдено эффективное решение получения исходных множителей, кроме как перебором. Таким образом, возникает потребность в постоянной генерации простых чисел высокой разрядности, для поддержания в защищенном состоянии любой системы передачи информации.

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

Тест простоты Ферма

Если n — простое число, то оно удовлетворяет сравнению для любого  которое не делится на .

Выполнение сравнения  является необходимым, но недостаточным признаком простоты числа. То есть, если найдётся хотя бы одно , для которого  то число  — составное; в противном случае ничего сказать нельзя, хотя шансы на то, что число является простым, увеличиваются. Если для составного числа n выполняется сравнение, то число  называют псевдопростым по основанию  . При проверке числа на простоту тестом Ферма выбирают несколько чисел . Чем больше количество , для которых , тем больше шансы, что число  простое. Однако существуют составные числа, для которых сравнение  выполняется для всех  взаимно простых с  — это числа Кармайкла. Тем не менее, тест Ферма довольно эффективен для обнаружения составных чисел

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

В качестве критерия проверки, является ли заданное число  простым или составным, может служить критерий непростоты:

Нечетное число  ≥ 3 является составным тогда и только тогда, когда  является либо полным квадратом, либо найдутся два натуральных числа  и  такие, что: , и .

На критерии непростоты основан известный вероятностный тест Миллера–Рабина, который старается найти пару  , удовлетворяющие критерию непростоты.

Пусть  – число, которое необходимо проверить на простоту. Представим  в виде , где d –нечетно. Назовем произвольное число свидетелем простоты , если выполняется одно из следующих условий:

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

Алгоритм: Пусть число  – нечетно и  , где нечетно. Для каждого числа  от  до  , где  – число проверок в тесте, выполним следующие действия:

1. Вычислим 

2. Проверимусловие . Если оно выполнится, тогда  –свидетель простоты. Перейдем к следующему .

3. Иначе проверим, содержится ли число  в последовательности , где каждый последующий x вычисляется по формуле .

Если ответ положительный, то  – свидетель простоты. Перейдем к следующему.

Иначе, найден свидетель непростоты  . Завершаем тест с сообщением «число  – составное». Если после  проверок окажется  свидетелей простоты, то заканчиваем тест с сообщением « – вероятно простое». Считая, что время умножения логарифмическое, используя быстрое умножение по модулю, сложность работы алгоритма  . Таким образом, время работы алгоритма полиномиально.

Вероятностный тест простоты Соловея–Штрассена

Тест Соловея — Штрассена — вероятностный тест простоты, открытый в 1970-х годах Робертом Мартином Соловеем совместно с Фолькером Штрассеном. Он опирается на малую теорему Ферма и свойства символа Якоби: Если  — нечетное составное число, то количество целых чисел , взаимнопростых с  и меньших , удовлетворяющих сравнению:

 не превосходит .

Составные числа , удовлетворяющие этому сравнению, называются псевдопростыми Эйлера-Якоби по основанию .

Алгоритм

Повторить k раз:

= случайное целое от  до , включительно;

a) если , тогда: вывести, что   — составное и остановиться.

b) если , тогда: вывести, что  — составное и остановиться, иначе вывести, что  — простое с вероятностью  , и остановиться.

Вычислительные эксперименты

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

Таблица 1.

Результаты вычислительных экспериментов

На основе полученных данных можно сделать следующие выводы:

По таблице видно, что скорость работы алгоритма Соловея-Штрассена в среднем меньше, чем скорость работы тестов Ферма и Рабина-Миллера. Это связано с тем, что в алгоритме Соловея-Штрассена необходимо вычисления символа Якоби. Скорость же работы тестов Ферма и Рабина-Миллера практически совпадают, различие не превышает статистической погрешности. Однако при этом тест Ферма обладает недостатком, о котором было сказано ранее – он неправильно определяет простоту чисел Кармайкла. Тест Рабина-Миллера, учитывая схожую скорость работы, лишён этого недостатка, так как полагается на более сильный критерий, чем тест Ферма.

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