Проверка больших простых чисел

Размещено на http://www.allbest.ru/

Введение

криптографический простой число цифровой

Тематика проверки больших простых чисел является ключевой для изучения криптографических методов защиты информации. Почти каждый криптографический алгоритм с открытым ключом требует генерации простого числа размером не менее 512 бит. В процессе использования таких алгоритмов приходится многократно создавать такие числа, причем некоторые алгоритмы требуют простые числа специального вида. Например, алгоритм цифровой подписи (ЦП) стандарта ГОСТ Р 34.11-94 требует генерации двух простых чисел и таких, что является делителем числа

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

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

Рекордно большое простое число

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

Новое простое число, относящееся к классу простых чисел Мерсенна, записывается как , в нем цифр. Оно было получено 25 января 2013 года на компьютере одного из участников проекта -- профессора университета центрального Миссури Кертиса Купера (Curtis Cooper). Прежнее самое большое простое число, полученное в 2008 году, содержало цифр.

"Простые числа очень интересны не только математикам, но и обычным людям, потому что они применяются в криптографии, например, для банковских кодов. Все они основаны на больших простых числах. Чем больше простое число, тем устойчивее шифр. Поэтому есть большой интерес к ним" -- сотрудник Математического института имени Стеклова РАН (МИАН) Николай Андреев.

Проект (Great Internet Mersenne Prime Search), созданный в 1996 году, представляет собой сеть распределенных вычислений, к которой может присоединиться любой желающий. Его цель -- поиск так называемых простых чисел Мерсенна, впервые описанных в 17 веке французским математиком Мареном Мерсенном. "Обычные" простые числа делятся без остатка только на самих себя и на единицу, а простые числа Мерсенна могут быть представлены в виде .

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

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

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

,

где - различные простые числа, .

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

Тесты чисел на простоту

1. Перебор делителей

Перебор делителей - алгоритм факторизации или тестирования простоты числа путем полного перебора всех возможных потенциальных делителей. Обычно перебор делителей заключается в переборе всех целых (как вариант: простых) чисел от 2 до квадратного корня из факторизуемого числа и в вычислении остатка от деления n на каждое из этих чисел. Если остаток от деления на некоторое число равен нулю, то является делителем . В этом случае либо объявляется составным, и алгоритм заканчивает работу (если тестируется простота ), либо сокращается на и процедура повторяется (если осуществляется факторизация ). По достижении квадратного корня из и невозможности сократить ни на одно из меньших чисел, n объявляется простым.

Теорема Вильсона

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

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

Тест Миллера -- Рабина -- вероятностный полиномиальный тест простоты. Позволяет эффективно определять, является ли данное число составным. Однако, с его помощью нельзя строго доказать простоту числа. Тем не менее, тест Миллера -- Рабина часто используется в криптографии для получения больших случайных простых чисел. Алгоритм был разработан Гари Миллером в 1976 и модифицирован Майклом Рабином в 1980 году. Пусть -- нечётное число большее . Число однозначно представляется в виде , где нечётно. Целое число , 1 , называется свидетелем простоты числа , если выполняются два условия:

1. не делится на ;

2. существует целое , , такое, что

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

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

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

Тест Соловея -- Штрассена опирается на малую теорему Ферма и свойства символа Лежандра. Основан на следующем утверждении:

Если -- нечетное составное число, то количество целых чисел, взаимнопростых с , удовлетворяющих сравнению , и таких, что не превосходит .

Тест Люкам - Леммера

Тест Люкам -- Леммера -- эффективный тест простоты для чисел Мерсенна. Этот тест был предложен Люка в 1878 году и в 1930 году усовершенствован Лемером (Lehmer).

Тест Люка -- Лемера базируется на том наблюдении, что простота числа Мерсенна влечёт простоту числа .

Благодаря тесту Люка -- Лемера простые числа Мерсенна удерживают лидерство как самые большие известные простые числа. Именно тест Люка -- Лемера лежит в основе проекта распределённых вычислений, занимающимся поиском новых простых чисел Мерсенна.

Тест Пепина

Тест Пепина состоит в возведении числа 3 в степень (серией из последовательных возведений в квадрат) по модулю Fn. Если результат сравним с -1 по модулю Fn, то Fn является простым, а в противном случае -- составным.

Тест Ферма

Тест Ферма позволяет эффективно определять, является ли данное число простым, однако, с его помощью нельзя строго доказать составность числа.

В основе теста Ферма лежит теорема Ферма. Ее формулировка приведена ниже:

Теорема Ферма (малая)

Если - простое, и не делит a, для любого .

Таким образом, если простое число, то для любого основания a будет выполняться сравнение . Если - составное число, то такое сравнение будет выполняться лишь для некоторых в силу случайного совпадения. На этом факте основан тест Ферма, который проверяет данное сравнение для случайным образом выбранных оснований .

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

Тест Конягина-Померанса

Если для известно полное разложение на простые множители или достаточно большая часть этого разложения, то можно с полиномиальной сложностью проверить, простое n или составное.

Алгоритм проверки простоты числа:

1. Заготавливаем таблицу всех простых чисел, не превосходящих ..

2. В цикле по от до осуществляем шаги 1) - 8) до тех пор, пока не докажем, что - простое или что - составное число:

1) если - составное (см. таблицу ), то F(a) = a - 1 и идём на шаг 8);

2) если - простое и , и идём на шаг 8);

3) иначе проверяем, выполняется ли сравнение: . Если нет, то - составное;

4) используя разложение на простые сомножители, находим порядок числа , т.е. наименьшее натуральное число, такое, что ;

5) проверяем, выполняется ли условие . Если оно не выполняется, то - составное;

6) вычисляем ;

7) если , то - простое;

8) если , то возвращаемся на шаг 1) для следующего значения. Если же , то - составное.

Заключение

Для создания программы была использована интегрированная среда разработки программного обеспечения NetBeans.

Для написания программы, реализующий алгоритм проверки на простоту больших чисел, был использован объектно-ориентированный язык программирования Java.

Для проверки числа на простоту среди многих существующих тестов, таких, как:

Перебор делителей

Теорема Вильсона

Тест Ферма

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

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

Тест Люка-Лемера

Тест Пепина

Тест Агравала-Каяла-Саксены

Тест Конягина-Померанса

Был выбран Тест Конягина-Померанса, основанный на следствие из методе.

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

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

Процесс проверки простоты числа занимает большие простые числа являются неотъемлемой частью многих современных алгоритмов шифрования, повышают эффективность работы криптосистемы с открытыми ключами. Размещено на Allbest.ru