ЗНАЙ ИНТУИТ, Лекция, Основи на теорията на числата, използвана в криптографията с публичен ключ
Инверсия по модул m
В много криптографски задачи за дадени числа c, m се изисква да се намери такова число d -1 mod m. Тази нотация за инверсия се дължи на факта, че равенството cd mod m = 1 може да бъде пренаписано като
По този начин умножението по s -1 съответства на делението по s, когато се изчислява по модул m .
Инверсията по модул m може също да бъде изчислена с помощта на обобщения евклидов алгоритъм.
Нека покажем как се прави това. Равенството по-долу означава, че за някакво цяло число k важи равенството cd - km = 1. Като се има предвид, че c и d са съвместни, можем да трансформираме това равенство, както следва:
Следователно можем да изчислим с -1 mod m (или да намерим числото d), използвайки обобщения евклидов алгоритъм. В този случай стойността на променливата k не представлява интерес за нас. Ако числото d се окаже отрицателно, тогава трябва да добавите m към него, тъй като по дефиниция числото mod m е взето от множеството .
Обмисли пример. Нека m = 9, c = 5. Намерете 5 -1 мод 9. Ще извършваме изчисления съгласно обобщения евклидов алгоритъм, записвайки всички изчисления на стъпки.
По този начин получихме 5 -1 мод 9 = 2. Нека проверим: 5 * 2 mod 9 = 10 mod 9 = 1 .
Ключови термини
Алгоритъм на Евклид - математически алгоритъм, който може да се използва за намиране на най-големия общ делител на две числа.
Взаимно прости числа - числа, които нямат общи делители (с изключение на един).
Проблем с факторизацията - намиране на две или повече естествени числа, които дават дадено число при умножаване.
Модулна инверсия - естествено число, което, умножено по модул по дадено число, води до едно.