|
|
ru.algorithms- RU.ALGORITHMS ---------------------------------------------------------------- From : Evgenij Masherov 2:5020/175.2 04 May 2003 18:50:08 To : Alexandr Zhizhin Subject : RSA --------------------------------------------------------------------------------
Fri May 02 2003 17:06, Alexandr Zhizhin wrote to All:
AZ> Кто нибудь пробовал реализовать алгоритм шифрования RSA? Интересует
AZ> вопрос как можно реализовать быстрое возведение в степень y=x^e mod n,
AZ> если x, e,
AZ> n - 25-значные числа (double long). Можно такое сделать на Си без
AZ> специальных библиотек? Вообще где такие библиотеки можно нарыть? Если не
AZ> жалко поделитесь исходниками, мыслями и т.п.
0. Читайте Кнута. Я бы даже сказал - истязайте себя Кнутом... Очень
просветляет... В данном случае т.2, гл. 4
1. Типа double long ни в каком С-компиляторе не встречается. Бывает, правда,
long long. А long double это плавающий тип и для данной задачи решительно
непригоден.
2. Для работы с большими числами их представляют в виде массива, каждый
элемент которого суть "разряд" по некоторому большому основанию. Далее см.
учебник арифметики для 3-го класса - алгоритмы в точности те же:) Правда, для
умножения есть более быстрые методы, у того же Кнута описанные.
3. Возведение в ОЧЕHЬ большую степень делают, например, двоичным (АКА "русский
крестьянский") методом. Для этого показатель представляют в двоичной системе и
замечают, что если разряд 0 - то умножать не надо, если 1 - то надо, а для
перехода к следующему двоичному разряду нужно возвести основание в квадрат.
4. Все вычисления ведутся по требуемуму модулю, так что длина промежуточных
результатов не растет.
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
Архивное /ru.algorithms/3300ad4a283d.html, оценка из 5, голосов 10
|