Введение

Вы знакомы с уроком по современной криптографии? На последней проверке пользователи чаще всего задавали такой вопрос:

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

Например, если я выберу случайным образом два больших простых числа, скажем, P1=709 и P2=733

и перемножу их, получив N = P1 * P2

N = 709 * 733 = 519697 (эта операция легко вычисляется)

У меня в итоге будет некое большое число (519697), и я буду знать, как оно раскладывается на множители (709 * 733)

А теперь представьте, что я скрыл его разложение на простые множители и предоставил вам следующее:

519697 = ? * ? (это сложно вычислить)

Если я вас попрошу разложить это число на простые множители, с чего начать решение такой задачи? Не волнуйтесь, этот вопрос многих поставит в тупик! Чтобы ответить на него, придётся перебирать множество возможных делителей. Перемножить два числа можно быстро (и легко), а вот поиск простых делителей — это долгая (сложная) операция. Этот простой факт лежит в основе алгоритма шифрования RSA.

Чтобы понять разницу, взгляните на анимированную схему

Хотя, прежде чем продолжить, вернёмся к первому шагу и ответим на важный вопрос. Когда мы случайным образом выбираем два больших простых числа, насколько быстро это можно сделать? Насколько проста такая задача?

Если подумать, то вы в конечном счёте согласитесь, что этот шаг требует как минимум проверки, является ли случайно сгенерированное число (например, 99194853094755497) простым или составным. Есть ли у вас на калькуляторе для этого специальная кнопка?

IУ меня такой нет… Почему?

Чтобы ответить на этот вопрос, рассмотрим следующую задачу…