ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Alexandr Zhizhin                     2:5020/400     10 May 2003  17:49:43
 To : Evgenij Masherov
 Subject : Re: RSA
 -------------------------------------------------------------------------------- 
 

 Hello, Evgenij!
 You wrote to Alexandr Zhizhin on Sun, 04 May 2003 17:50:08 +0400:
 
       AZ>>  Кто нибудь пробовал реализовать алгоритм шифрования RSA?
 Интересует
       вопрос как можно реализовать быстрое возведение в степень y=x^e mod n,
       если x, e,
       n - 25-значные числа (double long). Можно такое сделать на Си без
       специальных библиотек? Вообще где такие библиотеки можно нарыть? Если
       не жалко поделитесь исходниками, мыслями и т.п.
       EM>  0. Читайте Кнута. Я бы даже сказал - истязайте себя Кнутом...
 Очень
       просветляет... В данном случае т.2, гл. 4
 В электронном виде её можно где нибудь нарыть?
 
       EM>  1. Типа double long ни в каком С-компиляторе не встречается.
 Бывает,
       правда, long long. А long double это плавающий тип и для данной задачи
       решительно непригоден.
 Почему же в Борланд Си есть такая штука:
  long double   і 80 bits і 3.4 * (10**-4932) to 1.1 * (10**+4932)
 в него можно поместить большее целое число, чем в
  unsigned long і 32 bits і                 0 to 4,294,967,295
 
 Плавающий тип, согласен что он малопригоден, но извратится по всякому можно.
 Остаток от целочисленного деления можно находить, да и процедуры округления
 есть. :)
 
       EM>  2. Для работы с большими числами их представляют в виде массива,
 каждый
       элемент которого суть "разряд" по некоторому большому основанию. Далее
       см. учебник арифметики для 3-го класса - алгоритмы в точности те же:)
       Правда, для умножения есть более быстрые методы, у того же Кнута
       описанные. 3. Возведение в ОЧЕHЬ большую степень делают, например,
       двоичным (АКА "русский крестьянский") методом. Для этого показатель
       представляют в двоичной системе и замечают, что если разряд 0 - то
       умножать не надо, если 1 - то надо, а для перехода к следующему
       двоичному разряду нужно возвести основание в квадрат. 4. Все
 вычисления
       ведутся по требуемуму модулю, так что длина промежуточных результатов
       не растет.
 Hу всё уели :) Почитаю Кнута, Теорию чисел и т.п. для общего развития - я не
 программер всё-таки.
 Большое спасибо за разъяснения.
 
 With best regards, Alexandr Zhizhin.  E-mail: hokum@sibmail.com
 --- ifmail v.2.15dev5
  * Origin: TUCS&R/Center TUSUR Telecom (2:5020/400)
 
 

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

Тема:    Автор:    Дата:    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