ВВЕДЕНИЕ 3
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ 5
ПСЕВДОПРОСТЫЕ ЧИСЛА 6
ПСЕВДОПРОСТЫЕ ЧИСЛА ФЕРМА 7
ЧИСЛА КАРМАЙКЛА 9
3. ТЕСТ МИЛЛЕРА-РАБИНА 10
4. ОБОСНОВАНИЕ ТЕСТА МИЛЛЕРА-РАБИНА 17
СВИДЕТЕЛИ ПРОСТОТЫ 17
ЛЖЕСВИДЕТЕЛИ 17
ТЕОРЕМА РАБИНА 17
5. ОЦЕНКА КОЛИЧЕСТВА СВИДЕТЕЛЕЙ ПРОСТОТЫ 21
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 21
РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 23
6. УЛУЧШЕННЫЙ АЛГОРИТМ МИЛЛЕРА-РАБИНА 27

Купить

В современном мире простые числа играют заметную роль в криптографии - науке, занимающейся шифрованием и расшифровкой тайных сообщений.
Несмотря на то, что современные технологии и алгоритмы и позволяют находить простые числа впечатляющей величины, давным- давно подмечено, что множество неизведанных простых чисел никогда не иссякнет. В самом деле, как было показано в 300 г. до н.э. Евклидом, существует бесконечное множество простых чисел. Это достижение можно назвать началом абстрактной теории простых чисел.
Объём данных в наше время растёт невероятно быстрыми темпами, и для защиты растущего количества информации требуются более эффективные методы. Современная криптография использует огромные полупростые числа, которые чрезвычайно сложно факторизовать, отсюда следует что, для построения таких чисел требуется проверка на простоту больших чисел. Поэтому более быстрые и эффективные тесты на простоту являются ключевыми для обеспечения информационной безопасности.
В связи с тем, что многие криптографические системы используют свойства простых чисел, разложение на множители, а также другие родственные теоретико-числовые задачи, технологические и алгоритмические достижения приобрели еще большую важность. Тот факт, что наша способность находить большие простые числа (распознавать их простоту) опережает наши возможности в области разложения на множители, заложен в основу ряда криптографических алгоритмов.
Среди последних достижений в области поиска больших простых чисел можно выделить достижение небезызвестной группы GIMPS (Great Internet Mersenne Prime Search),которые 7 января 2016 года
Некоторые тесты на простоту являются детерминированными, то есть они всегда правильно определяют, является ли число простым или составным. Самый быстрый из известных детерминированных тестов был создан в 2004 году тремя учёными в области информатики: Agrawal, Kayal и Saxena был создан AKS тест, который работал за ~ О ( log (п)6) времени. Несмотря на значительный прорыв, эта скорость по-прежнему довольно медленная по сравнению с потребностями информационной безопасности.
Вероятностные тесты обычно быстрее, но не всегда точны. Эти тесты определяют, удовлетворяет ли nодному или нескольким условиям, которым должны удовлетворять все простые числа. И если n не удовлетворяет этим условиям, мы говорим, что nявляется составным числом. А если nудовлетворяет условиям, то вероятно nявляется простым, но это не значит, что nоднозначно несоставное число.
Существует большое количество детерминированных и вероятностных алгоритмов проверки простоты чисел. Но основным и относительно быстрым из них является алгоритм Миллера-Рабина. Данный алгоритм был предложен Рабином в 1980 году, в котором за основу были взяты результаты, полученные Миллером в его статье от 1976 года, в частности, понятие свидетеля простоты.
Известно, что тест Миллера-Рабина имеет сложность в О ( l o д3(п) ). Используя быстрое преобразование Фурье, время работы можно уменьшить до О ( l о д2(п) ), то есть такой же, как и в тесте простоты Ферма. Но с другой стороны, в случае доказанной истинности ERH тест Миллера-Рабина можно преобразовать в детерминированный тест с временем работы О ( l од4 (п)), что намного быстрее AKS теста.

Купить