Разработка и исследование параллельных алгоритмов анализа криптосистем, основанных на задаче дискретного логарифмирования тема диссертации и автореферата по ВАК РФ 05.13.19, кандидат технических наук Сидоров, Игорь Дмитриевич

• Сидоров, Игорь Дмитриевич
• кандидат технических наук
• 2009

Оглавление диссертации кандидат технических наук Сидоров, Игорь Дмитриевич

Определения.

Обозначения и сокращения.

Введение.

1. Анализ известных методов дискретного логарифмирования.

1.1. Появление асимметричной криптографии.

1.2. Асимметричные схемы, основанные на дискретном логарифмировании.

1.2.1. Алгоритм обмена ключами Диффи-Хеллмана.

1.2.2. Бесключевое шифрование Месси-Омуры.

1.2.3. Алгоритм шифрования и подписи Эль-Гамаля.

1.3. Задача дискретного логарифмирования.

1.3.1. Задача ДЛ в общем виде.

1.3.2. Задача ДЛ в мультипликативной группе вычетов по модулю р.

1.3.3. Задача ДЛ в группе точек эллиптической кривой.

1.4. Анализ методов дискретного логарифмирования.

1.4.1. Полный перебор.

1.4.2. Метод Гельфонда.

1.4.3. Встреча посредине.

1.4.4. Метод Шенкса (Giant steps - baby steps).

1.4.5. Метод Полларда.

1.4.5. Встреча на случайном дереве.

1.4.6. Метод базы разложения.

1.4.7. Метод решета числового поля.

1.4.8. Выводы.

1.5. Используемые вычислительные средства.

1.5.1. Классификация параллельных архитектур.

1.5.2. Интерфейс передачи сообщений (MPI).

1.6. Оценка эффективности параллельных программ.

1.6.1. Закон Амдала.

1.6.2. Сетевой закон Амдала.

1.7. Выводы.

2. Разработка алгоритмов решения задачи дискретного логарифмирования в мультипликативной группе вычетов по модулю р.

2.1. Построение задачи дискретного логарифмирования заданной размерности.

2.2. Анализ методов базы разложения и решета числового поля.

2.3. Разработка алгоритма параллельного просеивания.

2.4. Разработка алгоритма параллельного гауссова исключения.

2.5. Алгоритм решения сравнений по составному модулю.

2.6: Применение метода решета числового поля для произвольных основания и экспоненты.

2.7. Реализация метода-базы разложения с помощью разработанных алгоритмов.

2.8: Реализация метода решета числового поля с помощьюразработанных алгоритмов.

2.9. Ускорение решения задачи дискретного логарифмирования с помощью предвычислений.

2.10. Выводы.

3. Решение задачи дискретного логарифмирования в группе точек эллиптической кривой.

3.1. Построение задачи дискретного логарифмирования заданной размерности.

3.2. Анализ методов дискретного логарифмирования на эллиптической кривой.

3.3. Распределение базы точек между процессами.

3.4. Планирование взаимодействия процессов в топологии «полносвязный граф»

3.5. Разработка абстрактного типа данных и выбор структур данных для хранения точек эллиптической кривой.

3.6. Разработка параллельного алгоритма'дискретного логарифмирования методом встречи посередине.

3.7. Разработка параллельного алгоритма дискретного логарифмирования методом встречи на случайном дереве.89*

3.8». Возможность предвычислений.

3.9. Выводы.

4. Теоретическая и экспериментальная оценка эффективности разработанных алгоритмов.

4.1. Теоретические оценки сложности'субэкспоненциальных методов.

4.1.1. Оценка сложности метода базы разложения.

4.1.2. Оценка сложности метода решета числового поля.

4.2. Теоретические оценки сложности экспоненциальных алгоритмов.

4.2.1. Оценка сложности метода встречи посередине.

4.2.2. Оценка сложности метода встречи на,случайном дереве.

4.3. Аппаратные и программные средства, используемые в вычислительных экспериментах-.100 >

4.3.11. Аппаратные средства.

4.3.2. Программные средства.

4.4. Эффективность алгоритмов, используемых в библиотеках.

4.4.1. Умножение целых чисел.

4.4.2. Возведение в степень.

4.4.3. Нахождение НОД.

4.4.4. Нахождение мультипликативного обратного элемента.

4.5. Экспериментальные оценки эффективности субэкспоненциальных методов.

4.5.1. Определение эффективности распараллеливания.

4.5.2. Влияние размера задачи-на время вычислений.

4.5.3. Определение влияния параметров алгоритмов на время вычислений.

4.6. Экспериментальные оценки эффективности экспоненциальных методов.

4.6.1. Определение эффективности.распараллеливания.

4.6.2. Влияние размера задачи на время вычислений'.

4.6.3. Влияние параметров алгоритмов на время вычислений.

4.7. Методики применения разработанных алгоритмов и программных реализаций

4.7.1. Методика применения субэкспоненциальных алгоритмов.

4.7.2. Методика применения экспоненциальных алгоритмов.

4.8. Оценки стойкости криптографических схем, основанных на задаче ДЛ.

4.9. Выводы.

Введение диссертации (часть автореферата) на тему «Разработка и исследование параллельных алгоритмов анализа криптосистем, основанных на задаче дискретного логарифмирования»

Асимметричная криптография, выдвинутая Диффи и Хеллманом [1] и независимо Мерклом [2], за очень короткий срок оказала большое влияние на развитие информационных технологий. Электронная коммерция, электронные платёжные системы, распространение ПО через глобальные сети были бы невозможны без активного использования алгоритмов симметричной и асимметричной криптографии. Криптография и криптоанализ вышли за стены закрытых институтов, и число публикаций по теме очень велико. К тому же, с большинством статей и книг можно оперативно ознакомиться через Интернет.

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

Стойкость всех алгоритмов асимметричной криптографии базируется на вычислительной сложности решения нескольких фундаментальных задач, таких как задача факторизации (разложения на множители), задача дискретного логарифмирования, задача укладки рюкзака и некоторых других. В качестве объекта исследования в данной работе была выбрана задача дискретного логарифмирования, так как решение этой задачи лежит в основе криптоанализа таких алгоритмов шифрования и цифровой подписи, как Эль-Гамаль[3], ГОСТ Р 34.10-94 [4] и ГОСТ Р 34.10-94 [5].

Решение задачи дискретного логарифмирования требует больших вычислительных мощностей, и сложность этой задачи существенно увеличивается при росте размерности. Последовательные вычисления с использованием одного процессорного ядра займут слишком много времени. Например, для нахождения дискретного логарифма методом базы разложения по модулю простого числа длиной 130 бит необходимо 2776 MIPS-года, что составляет около 359 суток (почти год) работы одного ядра процессора Intel® Xeon® CPU Е5345 с частотой 2.33GHz

6]. Действенным способом ускорения вычислений является использование распределённых многопроцессорных вычислений.

Отличительной чертой современной криптографии является широкая доступность относительно больших вычислительных мощностей. Если в 70-е — 80-е годы двадцатого века алгоритм DES считался практически стойким, то в 1999 году он был взломан с помощью распределённых вычислений путём полного перебора ключей менее чем за сутки [7]. Сегодня вычислительные кластеры широко используются для решения прикладных задач в различных отраслях науки. Оборудование для их построения предлагается по доступным ценам. Кроме того, криптоаналитик-энтузиаст может использовать время простоя имеющихся компьютеров.

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

Имеющиеся в открытой печати статьи в основном описывают некоторые методы решения задач дискретного логарифмирования, такие как решето числового поля, встреча на случайном дереве и т.п. Детали реализации (в том числе распараллеливания трудоёмких этапов вычислений) не разглашаются; приводятся только краткие характеристики проведённых вычислительных экспериментов[8].

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

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

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

В соответствии с целью определены следующие задачи исследования:

- анализ существующих методов дискретного логарифмирования, их времени выполнения и пригодности для распараллеливания;

- разработка параллельных алгоритмов, предназначенных для ускорения • вычислительно сложных участков выбранных методов дискретного логарифмирования;

- разработка программ, реализующих параллельные алгоритмы дискретного логарифмирования;

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

Методы исследования

Для достижения поставленной цели и решения сформулированных в диссертационной работе задач использовались методы теории вероятностей, теории чисел, теории групп, теории конечных полей, алгебраической геометрии, а также современные методологии построения программных комплексов и систем. При разработке алгоритмов анализа учитывались особенности применения стандарта передачи сообщений MPI (Message Passing Interface).

Научная новизна работы

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

В ходе работы были получены следующие основные результаты:

1. разработаны параллельные алгоритмы просеивания и Гауссова исключения для ускорения субэкспоненциальных методов ДЛ, пригодных для мультипликативной группы числового поля;

2. разработаны параллельные алгоритмы для ускорения экспоненциальных методов ДЛ, пригодных для группы точек эллиптической кривой;

3. проведены исследования влияния параметров алгоритмов и вычислительной системы на время выполнения алгоритмов;

4. разработан алгоритм нахождения решения из сравнений вида х = -st(mod г) при s<r, t<r и НОДЦ, г)ф 1;

5. модифицирован метод решета числового поля для решения задачи ДЛ при любых образующей и экспоненте.

Положения, выносимые на защиту:

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

2. результаты экспериментов показывают эффективность разработанных алгоритмов и программ;

3. модифицированный метод решета числового поля позволяет в отличие от существующих находить решение при произвольной образующей и экспоненте;

4. разработанный алгоритм позволяет решать сравнения вида х = -^"'(modr) при s<r, t<r, НОД(1,г)>1, которые нельзя разрешить напрямую.

Апробация работы

Результаты работы представлялись на региональных, всероссийских и международных конференциях — «Информационная Безопасность-2008», CSIT-2008, РусКрипто-2009 и других. По результатам работы опубликовано 11 печатных работ, среди них 4 тезиса докладов и 7 статей. Две статьи опубликованы в журнале «Известия ТТИ ЮФУ. Технические науки», входящем в перечень изданий, рекомендуемых ВАК. Также было получено 4 свидетельства о регистрации программ для ЭВМ.

Внедрение работы

Результаты работы были использованы в учебном процессе кафедры БИТ ТТИ ЮФУ, а также при выполнении г/б работы № г.р. 01.2.077 04968 - «Разработка и исследование распределённых методов оценки вычислительной стойкости криптоалгоритмов, основанных на задаче разложения на множители и задаче дискретного логарифмирования». Имеются соответствующие акты о внедрении.

Состав и структура диссертации

Представленная диссертация состоит из 4 глав, содержит 31 рисунок, 8 таблиц, 4 приложения.

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

Во второй главе приводятся разработанные параллельные алгоритмы, позволяющие находить дискретный логарифм в мультипликативной группе GF(p) двумя методами — базы разложения и решета числового поля. Также приводятся разработанный вспомогательный алгоритм решения сравнения jc^-jf'Onodr) при s<r, t<r, НОД(1,г)>1 и разработанная модификация метода решета числового поля, позволяющая находить решение в общем случае.

В третьей главе разрабатываются параллельные алгоритмы для решения задачи дискретного логарифмирования в группе точек эллиптической кривой методами встречи посередине и встречи на случайном дереве. Вводится понятие распределённой базы данных. Разрабатывается вариант применения известных структур данных (красно-чёрных деревьев [9]) для решения задачи методом встречи на случайном дереве.

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

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

Заключение диссертации по теме «Методы и системы защиты информации, информационная безопасность», Сидоров, Игорь Дмитриевич

4.9. Выводы

В данной главе были рассмотрены теоретические и экспериментальные оценки сложности для субэкспоненциальных и экспоненциальных методов. Представлены программные и аппаратные средства, с помощью которых производились вычислительные эксперименты. К аппаратным средствам относится вычислительный кластер кафедры БИТ мощностью 56 ГФлопс, к программным — библиотеки GMP и NTL, реализующие множество целочисленных операций. Рассмотрены применяемые в программных библиотеках и разработанных автором абстрактных типах данных алгоритмы, предназначенные для выполнения базовых операций - умножения целых чисел, возведения в степень, нахождения НОД и мультипликативного обратного.

Приведены результаты проведённых с программными моделями экспериментов. Эксперименты, направленные на определение эффективности распараллеливания, показали достаточную эффективность представленных в главах 2, 3 параллельных алгоритмов дискретного логарифмирования: 0.9-0.98 для просеивания, 0.5-0.7 для Гауссова исключения и 0.93-0.97 для построения распределённой базы точек и поиска в ней; кроме того, эффективность распараллеливания остаётся на постоянном уровне при увеличении числа процессорных ядер. Также с помощью экспериментов выявлено влияние параметров алгоритмов на время вычислений. По результатам экспериментов сформированы методики применения, определяющие оптимальные значения параметров алгоритмов.

Выполнены оценки сложности, основанные на показателях производительности современных суперкомпьютеров, прогнозируемой скорости роста и эффективности разработанных алгоритмов. На рассматриваемом гипотетическом вычислителе можно с помощью метода базы разложения решить задачу в Fp* размерностью порядка 200 бит, а используя метод решета числового поля — задачу размерностью порядка 900 бит. Для того же вычислителя максимальная размерность разрешимой задачи дискретного логарифмирования в E(FP) составляет 160 бит.

Заключение

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

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

Определён алгоритм генерации задачи заданной размерности для мультипликативной группы числового поля. Для субэкспоненциальных методов разработаны алгоритмы, распараллеливающие трудоёмкие этапы вычислений — алгоритм параллельного просеивания и алгоритм параллельного Гауссова исключения. Метод решета числового поля модифицирован таким образом, чтобы находить решение при произвольном основании и экспоненте.

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

Для всех типов методов разработан алгоритм нахождения решения из сравнений вида лгг-л'Г^шоёгЗпри s<r, t<r и НОДЦ,г)ф 1. Также для всех методов оценена эффективность предвычислений.

Выбранные методы реализованы в виде программ, что позволило экспериментально оценить эффективность разработанных параллельных алгоритмов.

Представлены результаты проведённых вычислительных экспериментов. Для Т оценки параллельных программ вычислялась эффективность как Е =-1—, где Е

Р*Тр) \ эффективность, р - число задействованных процессорных ядер, Тх,Тр —. время выполнения программы на одном ядре и на р ядрах соответственно.

По результатам экспериментов эффективность распараллеливания этапа просеивания близка к линейной (Е=0.9-1) и сохраняется: на высоком уровне при увеличении., количества задействованных процессорных ядер. Эффективность параллельного Гауссова;исключения заметно ниже линейной (Е=0.4-0.7), и остаётся постоянной; при? увеличении количества задействованных' процессорных ядер:, Эффективность построения, и поиска в> распределённой БД убывает при увеличении количества задействованных процессорных ядер - (Е=0;95 при пяти ядрах, Е-0.5 при двадцати ядрах). , .

Также по результатам-вычислительных экспериментов оценена , зависимость времени вычислений от размерности задачи, исследовано? влияние основных параметров алгоритмов на время вычислений^ даны рекомендации по эффективному выбору параметров в зависимости от размерности задачи и имеющихся вычислительных средств. . '

В целом по результатам экспериментов можно заключить, что субэкспоненциальные методы, дискретного логарифмирования (методы? решета) могут быть эффективно реализованы на распределённых вычислительных: системах. Экспоненциальные методы реализуются менее эффективно, так как они требуют большого объёма оперативной памяти, и плохо распараллеливаются на большом количестве процессорных ядер.

Кроме того, приводятся теоретические оценки; эффективности рассматриваемых методов и выполненные автором оценки стойкости криптосистем, основанных на задаче дискретного логарифмирования, с учётом прогнозирования роста вычислительных мощностей.

Список литературы диссертационного исследования кандидат технических наук Сидоров, Игорь Дмитриевич, 2009 год

1. W. Diffie and М.Е. Hellman, "New Directions in Cryptography", IEEE Transactions on Information Theory, v. IT-22, n. 6, Nov 1976, pp. 644-654.

2. R.C. Merkle, "Secure Communication Over Insecure Channels", Communications of the ACM, v.21, n. 4, 1978, pp. 294-299.

3. Шнайер Б. Прикладная криптография. Протоколы, алгоритмы, исходные тексты на языке Си. М.: Издательство ТРИУМФ, 2003 - 816 е.: ил.

4. ГОСТ Р 34.10-94 Информационная технология. Криптографическая защита информации. Процедуры выработки-и проверки электронной цифровой подписи на базе асимметричного криптографического алгоритма.

5. ГОСТ Р 34.10-2001 Информационная технология. Криптографическая защита информации. Процессы формирования и проверки электронной цифровой подписи.

6. Formal Press Release; US government standard broken in less than a day; January 19th, 1999 Электронный ресурс. Режим доступа: http://www.distributed.net/des/release-desiii.txt, свободный.

7. Закон Мура Электронный. ресурс. Режим доступа: http://ru.wikipedia.Org/wiki/3aKOHMypa, свободный

8. Красно-черные деревья Электронный ресурс. Режим доступа: http://algolist.manual.ru/ds/rbtree.php, свободный.

9. R.L. Rivest, A. Shamir, L.M. Adleman, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems", Communications of the ACM, v. 21, n. 2, Feb 1978, pp.120-126

10. R.L. Rivest, A. Shamir, L.M. Aldeman, "On Digital* Signatures and: Public Key Cryptosystems", MIX Laboratory for Computer Science, Technical Report, MIT/LCS/TR-212, Jan 1979.

11. Ростовцев A.F., Маховенко Е.Б. Теоретическая криптография. — СПб:: АНО НПО «Профессионал», 2005. — 480 е., ил.

12. Элементарное введение в эллиптическую криптографию: Протоколы криптографии на эллиптических кривых. — М.: КомКнига, 2006. 280 с.

13. Т. ElGamal, "A Public-Key Cryptosystem and a Signature Scheme Based on Discrete Logarithms", Advances in Cryptology: Proceedings of CRYPTO 84, Springer-Verlag, 1985, pp. 1-18.

14. T.ElGamal; "A Public-Key Cryptosytem and a Signature Scheme Based on Discrete Logarithms", IEEETransactions onInformation Theory, v. IT-31, n. 4,. 1985, pp. 469472.16; Каргополов М.И-VМерзляков

15. Курош А.Г.Теория групп: Mi: Наука;1967."

16. Новиков; Ф.А, Дискретная математика для программистов: Учебник для вузов. 3-е изд.- СПб.: Питер, 20081 384 с.: ил.- (Серия "Учебник для вузов!').

17. Schoof R. Counting points on elliptic curves over finite fields // Journal de Theorie,des Nombres de Bordeaux. 1995. Vol. 7. p. 219-254.

18. Нечаев В.И. Элементы криптографии. Основы теории защиты информации. М:: Высшая школа, 1999.

19. Don Coppersmith, Andrew М. Odlzyko and Richard Schroeppel, Discrete logarithms in GF(p). Algorithmica 1 (1986), 1-15

20. J.M. Pollard. Monte-carlo methods for index computation (mod p). Mathematics of computation 32 (1978)

21. Gordon D. Discrete logarithms in GF(p) using the number field sieve // SLAM Journal on Discrete Mathematics. 1993. Vol. 6. P. 124-138

22. Weber D. An implementation of the general number field sieve to compute discrete logarithms mod p. // Advances in Cryptology EUROCRYPT '1995. Lecture notes in Computer Science. Springer - Verlag. 1995. Vol. 921. P. 95-105.

23. Судоплатов C.B., Овчинникова E.B. Дискретная математика: Учебник. 2-е изд., перераб. - М.: ИНФРА-М; Новосибирск: Изд-во НГТУ, 2007. - 256 с. - (Высшее образование).

24. Классификация параллельных вычислительных систем Электронный ресурс. -Режим доступа: http://ru.wikipedia.org/wiki/Kлaccификaцияпapaллeльныxвычиcлитeльныxcиcт ем; свободный.

25. Воеводин В.В., Воеводин Вл. В. Параллельные вычисления. Спб.: БХВ-Петербург, 2002г.

26. Кнут, Дональд, Эрвин. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с англ. : Уч. Пос. М. : Издательский дом «Вильяме», 2000. - 720 с. : ил. - Парал. тит. англ.

27. Ахо, Альфред В., Хопкрофт, Джон, Ульман, Джеффри Д. Структуры данных и алгоритмы. : Пер. с англ. : М. : Издательский дом «Вильяме», 2001. 384 с. : ил. — Парал. тит. англ.

28. Немнюгин С.А., Стесик O.JI. Параллельное программирование для многопроцессорных вычислительных систем. СПб.: БХВ-Петербург, 2002. — 400 е.: ил.

29. Простое число Софи Жермен. Электронный ресурс. — Режим доступа: Ьйр://ш^1к1ре<11а.ог§/ш11а/ПростоечислоСофиЖермен, свободный

30. R. Solovay and V. Strassen, «А Fast Monte-Carlo Test for Primality," SIAM journal on Computing, v. 6; Mar 1977, pp. 84-85; erratum in ibid, v. 7, 1978, p. 118.

31. M.O. Rabin, "Probabilistic Algorithm for Testing Primality," Journal- of Number Theory, v. 12, n. 1, Feb 1980; pp. 128-138.

32. G.L. Miller, "Riemann's Hypothesis and Tests for Primality," Journal of Computer Systems Science, v. 13, п. 3-, Dec 1976, pp. 300-317.

33. Писсанецки С. Технологияфазреженных матриц. М:: Мир; 1988.

34. Кнут, Д.Э: Искусство программирования, том- 2. Получисленные алгоритмы, 3-е издание.: Пер. с англ. : Уч. пос. М. : Издательский дом «Вильяме», 2001. - 832 с. : ил. - Парал. тит. англ.

35. Бабенко JI.K., Сидоров И.Д. Параллельный алгоритм дискретного логарифмирования методом решета числового поля .// Изв. ЮФУ. Технические науки. 2008. - №8. - С. 199-203.

36. Сидоров ИД. Нахождение дискретного логарифма методом решета числового поля для негладких образующей и экспоненты. // Неделя = науки 2008; Сб. тезисов, Том 2. - Таганрог; Изд-во ТТИ ЮФУ, 2008. - 464 с.

37. А. Г. Ростовцев. О выборе эллиптической кривой над простым полем для построения криптографических алгоритмов* «Проблемы информационной безопасности. Компьютерные системы», СПб., 19991 № 3. С. 37-40

38. Кнут, Дональд Эрвин. Искусство программирования, том 3. Сортировка и поиск,, 2-е изд. : Пер. с англ. : Уч. пос. Ml : Издательский дом «Вильяме», 2000. - 832" с. : ил. — Парал. тит. англ.

39. Красно-чёрное дерево. Электронный ресурс. — Режим доступа: http://m.wikipedia.0rg/wiki/KpacH0-4epH0e^n,epeB0, свободный

40. Кнут, Дональд, Эрвин. Искусство программирования, том 1. Основные алгоритмы, 3-е изд. : Пер. с англ. : Уч. Пос. — М. : Издательский дом «Вильяме», 2000. — 720 с. : ил. Парал. тит. англ.

41. Харт, Джонсон, М. Системное программирование в среде Windows, 3-е издание, : Пер, с англ. — М. : Издательский дом "Вильяме", 2005. — 592 е.: ил. — Парал. тит. англ.

42. NTL: A Library for doing Number Theory Электронный ресурс. Режим доступа: http://www.shoup.net/ntl/, свободный

43. The GNU Multiple Precision Bignum Library Электронный ресурс. Режим доступа: http://gmplib.org/, свободный

44. ТОР 500 Электронный ресурс. Режим доступа: http://www.top500.org/, свободный