Простые числа

Схема, иллюстрирующая алгоритм Диффи — Хеллмана. Имеются два абонента, Алиса и Боб, желающие общаться втайне. Они открыто договариваются о двух числах (простое число р и другое число g, имеющие определенные свойства). И Алиса, и Боб выполняют некоторые операции с этими числами и с еще одним целым числом, которое они держат в секрете, а затем открыто посылают друг другу результаты. Теперь и Алиса, и Боб выполняют с полученным результатом еще одну операцию и получают один и тот же ответ, который будет для них секретным кодом. Потенциальный шпион, перехвативший результаты, посланные Алисой и Бобом, не может сгенерировать секретный код, имея лишь эту информацию.

Предположим теперь, что вместо банок с краской в магазине находятся простые числа. Возьмем любые два, например, 7 и 13, и перемножим их (аналогично смешиванию краски). В результате мы получим 7 х 13 = 91.

Тогда возникает вопрос: можно ли узнать, какие простые числа были перемножены, чтобы в результате получилось 91? Для ответа на него надо взять список простых чисел и проделать несколько проверок. Казалось бы, простое решение, как и в случае определения цвета красок, если в магазине было всего около десятка основных цветов.

Но с простыми числами все намного сложнее.

Например, ни у кого не хватит терпения проверить, что число 1409 305 684 859 является результатом умножения простых чисел 705 967 и 1996 277, особенно если учесть, что эти два простых числа взяты из списка простых чисел между 1 и 2000000, а там таких «всего лишь» 148933. Однако мы живем в эпоху высоких технологий, и, конечно, эту задачу можно довольно быстро решить с помощью хорошей программы и мощного компьютера. Хотя все зависит от того, насколько большой этот магазин красок. Не следует также забывать, что количество простых чисел не просто очень большое, а бесконечное.

Пара простых чисел в приведенном выше примере содержит лишь несколько цифр. Если мы возьмем простые числа, каждое из которых содержит сотни цифр, то время, которое потребуется компьютерной программе на простой перебор всех возможных вариантов — метод «грубой силы», как говорят криптографы, — будет больше, чем предполагаемое время существования Земли.

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

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

* * *