Дискретные математические структуры, лекция 5.3: Почему работает RSA

Дискретные математические структуры, лекция 5.3: Почему работает RSA. Реализация криптосистемы RSA требует генерации больших простых чисел — длиной в несколько сотен цифр. Теорема о простых числах гласит, что вероятность того, что случайное число меньше n является простым, приблизительно равна 1/ln 2. Это означает, что вероятность того, что случайно выбранное 200-значное число окажется простым, составляет примерно 1 к 500. Таким образом, большие простые числа можно генерировать методом «угадывания и проверки». Для проверки того, является ли случайно выбранное большое число простым, можно использовать критерий простоты Ферма. Он использует малую теорему Ферма, которая гласит, что a^(n-1) = 1 mod n. В частности, мы можем многократно вычислять a^(n-1) для разных значений a, и если мы всегда получаем 1 mod n, то мы можем быть «почти уверены», что n является простым числом. Мы обсудим, что мы подразумеваем под «почти уверены», используя некоторые основные положения теории чисел. В заключение мы приводим теорему, показывающую, почему функции шифрования и дешифрования RSA являются обратными друг другу. Страница курса: http://www.math.clemson.edu/~macaule/math4190-online.html