РЕФЕРАТ 3
ВВЕДЕНИЕ 5
1 Тесты на простоту 7
1.1 Тест Ферма 7
1.2 Тест Соловея - Штрассена 8
1.3 Тест Рабина - Миллера 10
2 Факторизация целых чисел 12
2.1 Метод пробных делений 12
2.2 Метод Ферма 12
2.3 p-метод Полларда 13
2.4 (р - 1)-метод Полларда 14
2.5 Метод эллиптических кривых 17
3 Особенности программной реализации 23
3.1 Класс больших чисел 23
3.2 Программные реализации p-метода Полларда 24
3.2 Программная реализация метода эллиптических кривых 25
4 Особенности аппаратной реализации 28
5 Экспериментальные результаты 29
ЗАКЛЮЧЕНИЕ 32
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ 33
ПРИЛОЖЕНИЕ А Текст программ 34
ПРИЛОЖЕНИЕ B Модульная схема 54
В настоящее время в любых сетях используется шифрование информации для защиты от вмешательства третьих лиц. Для шифрования используются различные криптосистемы, такие как RSA, DSA, система Эль Гамаля, протокол Диффи - Хеллмана и другие [1]. Тот факт, что задача факторизации больших чисел есть задача предполагаемой большой вычислительной сложности, лежит в основе различных криптосистем, таких, например, как RSA [2].
Факторизация или разложение на множители целых чисел - одна из древнейших проблем теории чисел [3]. Методы факторизации целых чисел затрагивают такие области математики, как теория чисел, поля Галуа, эллиптические кривые (метод эллиптических кривых), квантовые вычисления (метод Шора) и т.д. В настоящей работе рассматриваются и анализируются некоторые известные методы факторизации. При решении задачи факторизации затрагивается ряд других задач, непосредственно связанных с ней, таких как тесты на простоту и генерация больших простых чисел.
Соответственно, параллельно с решением задачи факторизации целых чисел исследователи занимались нахождением больших простых чисел и разработкой тестов на простоту. Например, П. Ферма, создавший первый тест на простоту, также предложил метод факторизации, названный в его честь. В XVII - XIX вв., помимо Ферма, над вопросами простоты числа и разложения составных чисел работали такие ученые, как Мерсенн, Гаусс, Эйлер и другие. Прорыв в данной области наступил в XX веке, когда появились криптографические алгоритмы, использующие большие простые числа [4].
В 1977 г. создатели алгоритма RSA предложили для тестового взлома 129значное составное число. Многие ученые приняли этот вызов и начали работу над быстрыми алгоритмами факторизации, способными разложить это число [5]. В результате этого соревнования были созданы различные методы факторизации, некоторые из которых будут рассмотрены в данной работе.
Предложенное число RSA-129 было разложено на простые множители в 1994 г. с помощью алгоритма квадратичного решета в результате долгой работы, потребовавшей использования сети компьютеров и полгода вычислений [1].
В настоящей работе подробно рассматриваются два известных метода факторизации, p-метод Полларда и метод эллиптических кривых. Методы были программно реализованы, причем для p-метода Полларда были разработаны последовательная и параллельная программные реализации. С разработанными программными реализациями были проведены компьютерные эксперименты. В работе также представлена разработанная нами аппаратная реализация p-метода Полларда, поскольку аппаратные реализации содержат естественные возможности для параллельных вычислений.
Структура работы следующая. В первой главе кратко описываются три теста на простоту - тест Ферма, тест Соловея - Штрассена и тест Рабина - Миллера. Анализируются достоинства и недостатки каждого из методов. Во второй главе рассмотрены различные методы факторизации. В третьей главе представлено описание разработанных автором программных реализаций для таких методов факторизации, как p-метод Полларда и метод эллиптических кривых. В главе 4 мы описываем разработанную нами аппаратную реализацию p-метода Полларда. В пятой главе приведены результаты проведенных нами компьютерных экспериментов с разработанными реализациями. В заключении представлен краткий обзор выполненной работы и перечислены возможные направления дальнейших исследований. Тексты программ приведены в приложении А. Модульная схема аппаратной реализации приведена в приложении B.
В ходе данной работы нами были изучены и программно реализованы два метода факторизации - p-метод Полларда и метод эллиптических кривых. Эксперименты подтвердили, что метод эллиптических кривых работает быстрее, чем p-метод Полларда; для параллельной реализации p-метода Полларда нами было достигнуто ускорение □(р1/4). Кроме того, p-метод Полларда был реализован аппаратно на СБИС ПЛ Altera Cyclone V GX. В настоящий момент разработанная реализация работает для чисел максимальной длины 16 бит. В дальнейшем мы планируем усовершенствовать аппаратную реализацию и провести с ней соответствующие эксперименты. Для проведения экспериментов был разработан генератор больших простых чисел, который генерирует простое число длиной до 512 бит за 40,5 секунд.
Мы также планируем в дальнейшем либо улучшить существующий класс больших чисел, либо использовать готовые классы подобного рода; усовершенствовать реализацию второй стадии метода Ленстры; доработать аппаратную реализацию p-метода Полларда для работы
