ТЕОРИЯ ЧИСЕЛ | Проверка числа на простоту
Простые числа в криптографии
Что такое простые числа и почему криптография так хочет их использовать? Простые числа широко используются в криптографии, потому что они дают больше шансов создать уникальные значения для хэш-функций. Хеш-функции используют модули, а использование комплексных чисел (т. е. Не простых) увеличивает вероятность хеш-коллизий (т. е. Разные входные данные дают один и тот же хэш ). Простые числа увеличивают вероятность создания уникальных значений во время хеширования путем умножения значения на простое число...
Проверка на простоту - одна из краеугольных задач криптографии. Существующие алгоритмы делятся на истинные и вероятностные. Последние выигрывают в скорости, но позволяют лишь с некоторой вероятностью предположить, что исследуемое число является простым. Определение простоты числа необходимо при взломе информации, зашифрованной или подписанной с использованием алгоритма RSA. Для вскрытия такого сообщения необходимо уметь разлагать число на два простых сомножителя, что при больших размерах чисел является нетривиальной задачей.