Приветствую Вас, уважаемые Читатели! Совсем недавно я написал статью про наибольший общий делитель и наименьшее общее кратное, где привел обобщенную формулу их вычисления. Однако, описанная там формула фактически для вычисления этих величин не используется, т.к. она далеко не оптимальна в плане сложности.
Источник: https://euston96.b-cdn.net/wp-content/uploads/2019/05/Euclid.jpg
Впрочем, задача эта уже давно решена: еще в 3 веке до нашей эры Евклид разработал одноименный алгоритм, который на данный момент (конечно, со множеством изменений) является не только одним из самых эффективных алгоритмов теории чисел, но и максимально используемым на практике в криптографии. Поехали!
Итак, задача неизменна: для двух натуральных чисел a и b найти наибольший общий делитель, т.е. наибольшее число, на которое делится и a и b.
Давайте применим данный алгоритм на конкретных величинах, взяв (с потолка) числа 4389 и 641:
Древние математики также называли алгоритм Эвклида "правилом вычитаний"
Первый шаг заключается в поиске такого наибольшего q, которое при умножении на b не превысит a. На первом шаге такое число — это 6. Вычисляем первый остаток и получаем число 543. Дальше по аналогии:
Последнее ненулевое значение остатка r и будет наименьшим общим делителем двух чисел. В данном случае судьба распорядилась таким образом, что взятые случайно числа оказались взаимно-простыми!
Возникает логичный вопрос: а сколько шагов может быть в таком алгоритме ?
Оказывается, существует теорема Ламе, которая утверждает, что количество шагов алгоритма Евклида не превышает упятеренного количества цифр меньшего числа b (для приведенного примера — 15). Т.е. на лицо всего лишь полиномиальная зависимость сложности вычислений, что в числовых алгоритмах подобно "манне небесной".
Еще одна связь обнаруживается между числами q, которые появлялись в алгоритме и представлением рациональных чисел в виде цепных дробей. Только посмотрите, как красиво:
Вообще, цепные дроби изумительной красоты конструкции
Алгоритм Евклида изучен вдоль и поперек, а также усовершенствован. Неудивительно, ведь он находит применение в одной из самых распространенных криптографических систем с открытым ключом RSA, надежность которой основывается на алгоритмической сложности факторизации (разложения на простые множители) больших чисел. Там с помощью алгоритма Евклида вычисляется секретная экспонента d, которая играет роль закрытого ключа и предназначена для дешифрования исходного сообщений.
Сразу прошу прощения, за такое "поверхностное" раскрытие вопроса по поводу RSA. Когда-нибудь продолжу, ведь тема большая.
Вот так древнегреческая математика стоит на страже конфиденциальности. Конечно, когда-нибудь с появлением квантовых компьютеров и RSA канет в лету, но алгоритму Евклида от этого ни тепло ни холодно, ведь он прекрасен сам по себе. Спасибо за внимание!
Читайте также:
- Самый важный среди интегралов
- Математическая константа, в которой зашифрованы все простые числа.
- TELEGRAM и Facebook — там я публикую не только интересные статьи, но и математический юмор и многое другое.
