📄Работа №77613
Тема: Улучшение теста Миллера-Рабина
Характеристики работы
Тип работы
Дипломные работы, ВКР
Предмет
Информационные системы
Объем:
29 листов
Год:
2017
Просмотров:
403
4355
руб.
🛒 Купить работу
Не подходит эта работа?
Закажите новую по вашим требованиям
Узнать цену на написание
Закажите новую по вашим требованиям
Представленный материал является образцом учебного исследования, примером структуры и содержания учебного исследования по заявленной теме. Размещён исключительно в информационных и ознакомительных целях.
Workspay.ru оказывает информационные услуги по сбору, обработке и структурированию материалов в соответствии с требованиями заказчика.
Размещение материала не означает публикацию произведения впервые и не предполагает передачу исключительных авторских прав третьим лицам.
Материал не предназначен для дословной сдачи в образовательные организации и требует самостоятельной переработки с соблюдением законодательства Российской Федерации об авторском праве и принципов академической добросовестности.
Авторские права на исходные материалы принадлежат их законным правообладателям. В случае возникновения вопросов, связанных с размещённым материалом, просим направить обращение через форму обратной связи.
Настоящий учебно-методический информационный материал размещён в ознакомительных и исследовательских целях и представляет собой пример учебного исследования. Не является готовым научным трудом и требует самостоятельной переработки.
📋 Содержание
ВВЕДЕНИЕ 3
2. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ 5
ПСЕВДОПРОСТЫЕ ЧИСЛА 6
ПСЕВДОПРОСТЫЕ ЧИСЛА ФЕРМА 7
ЧИСЛА КАРМАЙКЛА 9
3. ТЕСТ МИЛЛЕРА-РАБИНА 10
4. ОБОСНОВАНИЕ ТЕСТА МИЛЛЕРА-РАБИНА 17
СВИДЕТЕЛИ ПРОСТОТЫ 17
ЛЖЕСВИДЕТЕЛИ 17
ТЕОРЕМА РАБИНА 17
5. ОЦЕНКА КОЛИЧЕСТВА СВИДЕТЕЛЕЙ ПРОСТОТЫ 21
ТЕОРЕТИЧЕСКАЯ ЧАСТЬ 21
РЕЗУЛЬТАТЫ ИССЛЕДОВАНИЯ 23
6. УЛУЧШЕННЫЙ АЛГОРИТМ МИЛЛЕРА-РАБИНА 27
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 теста.
Несмотря на то, что современные технологии и алгоритмы и позволяют находить простые числа впечатляющей величины, давным- давно подмечено, что множество неизведанных простых чисел никогда не иссякнет. В самом деле, как было показано в 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 теста.
ИЛИ
Поиск аналога
🛒 Оформить заказ
⚡ Работу высылаем в течении 5 минут после оплаты.