По мере того как мы будем изучать курс «Математические основы криптологии» мы будем возвращаться к этой теме.
Задача получение простых чисел во многом зависит от того как ставить эту задачу.
Методы:
1) Самый древний способ получения простых чисел, как мы уже знаем, -
решето Эратосфена.
2) Формульный метод. С помощью формул можно получить некоторое множество чисел, но оно ограниченно. Простейшие:
а) целочисленные полиномы(в общем случае не решают задачу получение бесконечного множества простых чисел.)
б) экспоненциальная функция. (множество получаемое на основе данного способа, как мы уже говорили, ограничено по мощности.
этот способ имеет больший интерес для анализа криптошифра.
в) праймориальная формула. Пока не известно можно ли по этой формуле получить бесконечное число простых чисел.
3. ТЕСТИРОВАНИЕ
Задано некоторое число m и проверяется по определенному алгоритму, является ли оно простым. Так называемое тестирование на простоту. Этот способ используется в современных криптографических системах с открытым ключём. Берется некоторое большое число (сотни десятичных знаков) и по отношению к этому числу начинается тестирование.
Существует 2 метода тестирования на простоту:
1)строгие тесты(детерминированные).
отвечают на вопрос простое или составное однозначно.
2)вероятностные тесты.С помощью них мы можем говорить только с некоторой вероятностью, что данное число простое. При этом вероятность может быть сколь угодна близка к единице. Но эти
методы гораздо быстрее, нежели строгие, по отношению к большим числам. Т.е. когда информация не столь важна(для шифрование) мы можем рискнуть, и с некоторой вероятностью, использовать вместо простого числа составное.
Метод, объединяющий в себе как вероятностные, так и детерминированные методы называется комбинированным методом. Т.е. сначала мы выясняем, с некоторой вероятностью, что число m простое и потом по отношению к нему применяем строгий метод и в итоге это более оптимально чем сразу применять к некоторому большому числу строгий тест.
С понятием «строгие тесты» связанно такое понятие как «факторизация». Факторизация – разложение заданного числа на простые сомножители.
В 19 веке предложен тест проверки чисел Мерсена на простоту. Это был один из первых строгих тестов.
Так как же определить является ли число Мерсена простым или составным? Существует метод, причем достаточно эффективный для больших чисел.