ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Evgenij Masherov                     2:5020/175.2   10 May 2003  22:04:03
 To : Alexandr Zhizhin
 Subject : Re: RSA
 -------------------------------------------------------------------------------- 
 

 Sat May 10 2003 17:49, Alexandr Zhizhin wrote to Evgenij Masherov:
 
  AZ>       AZ>>  Кто нибудь пробовал реализовать алгоритм шифрования RSA?
  AZ> Интересует
  AZ>       вопрос как можно реализовать быстрое возведение в степень y=x^e mod
  AZ> n,
  AZ>       если x, e,
  AZ>       n - 25-значные числа (double long). Можно такое сделать на Си без
  AZ>       специальных библиотек? Вообще где такие библиотеки можно нарыть?
  AZ> Если
  AZ>       не жалко поделитесь исходниками, мыслями и т.п.
  AZ>       EM>  0. Читайте Кнута. Я бы даже сказал - истязайте себя Кнутом...
  AZ> Очень
  AZ>       просветляет... В данном случае т.2, гл. 4
 
  AZ> В электронном виде её можно где нибудь нарыть?
 
 Вообще Кнут выкладывался у Мошкова, www.lib.ru, но начали выкладку с третьего
 тома, так что не знаю - давно не заглядывал...
 
  AZ>       EM>  1. Типа double long ни в каком С-компиляторе не встречается.
  AZ> Бывает,
  AZ>       правда, long long. А long double это плавающий тип и для данной
  AZ> задачи
  AZ>       решительно непригоден.
 
  AZ> Почему же в Борланд Си есть такая штука:
  AZ>  long double   | 80 bits | 3.4 * (10**-4932) to 1.1 * (10**+4932)
  AZ> в него можно поместить большее целое число, чем в
  AZ>  unsigned long | 32 bits |                 0 to 4,294,967,295
 
  AZ> Плавающий тип, согласен что он малопригоден, но извратится по всякому
  AZ> можно.
  AZ> Остаток от целочисленного деления можно находить, да и процедуры
  AZ> округления есть. :)
 
 double long != long double
 
 Первое небываемое, второе - платформозависимый тип.
 А почему он плох для целых чисел - из-за гнусной вещи, как нормализация.
 Точность может уплыть в любой момент...
 
  AZ>       EM>  2. Для работы с большими числами их представляют в виде
  AZ> массива, каждый
  AZ>       элемент которого суть "разряд" по некоторому большому основанию.
  AZ> Далее
  AZ>       см. учебник арифметики для 3-го класса - алгоритмы в точности те
  AZ> же:)
  AZ>       Правда, для умножения есть более быстрые методы, у того же Кнута
  AZ>       описанные. 3. Возведение в ОЧЕHЬ большую степень делают, например,
  AZ>       двоичным (АКА "русский крестьянский") методом. Для этого показатель
  AZ>       представляют в двоичной системе и замечают, что если разряд 0 - то
  AZ>       умножать не надо, если 1 - то надо, а для перехода к следующему
  AZ>       двоичному разряду нужно возвести основание в квадрат. 4. Все
  AZ> вычисления
  AZ>       ведутся по требуемуму модулю, так что длина промежуточных
  AZ> результатов
  AZ>       не растет.
 
  AZ> Hу всё уели :) Почитаю Кнута, Теорию чисел и т.п. для общего развития - я
  AZ> не программер всё-таки.
  AZ> Большое спасибо за разъяснения.
 
 Собственно еще разъяснения - "русский крестьянский" он потому, что так
 умножают на счетах. Состоит в том, что один множитель удваивают, а второй
 делят пополам на каждой итерации. При возведении в степень соответственно
 основание степени возводят в квадрат, а показатель делят на два. 
 
 Евгений Машеров АКА СанитарЖеня
 
 --- 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