Главная страница


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)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

 Тема:    Автор:    Дата:  
 RSA   Alexandr Zhizhin   02 May 2003 17:06:27 
 RSA   Rodion Gorkovenko   03 May 2003 09:06:00 
 Re: RSA   Alexandr Zhizhin   04 May 2003 08:51:14 
 RSA   Rodion Gorkovenko   05 May 2003 10:32:00 
 Re: RSA   Alexandr Zhizhin   10 May 2003 17:48:13 
 RSA   Rodion Gorkovenko   14 May 2003 17:20:00 
 RSA   Evgenij Masherov   04 May 2003 18:50:08 
 Re: RSA   Alexandr Zhizhin   10 May 2003 17:49:43 
 Re: RSA   Evgenij Masherov   10 May 2003 22:04:03 
 RSA   Marckel Barsuckov   10 May 2003 22:16:29 
Архивное /ru.algorithms/3300ad4a283d.html, оценка 2 из 5, голосов 10
Яндекс.Метрика
Valid HTML 4.01 Transitional