ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Rodion Gorkovenko                    2:5030/1286.6  05 May 2003  10:32:00
 To : Alexandr Zhizhin
 Subject : RSA
 -------------------------------------------------------------------------------- 
 

 04 May 03 08:51, you wrote to me:
 
 AZ> Да я в общем тоже не слишком сведущий. Однако лабу по сабжу необходимо
 AZ> сделать.
 AZ> Задача: реализовать быстрое возведение в степень по модулю :)  Первое
 AZ> отпадает. В long double вроде немного побольше чем 19 знаков.
 
 Скажем так - побольше чем 19 и поменьше чем 20 ;)
 
 AZ> Вообще было бы неплохо иметь в Си целочисленный тип на 80 бит.
 
 Действительно - помню, как-то столкнувшись с такой задачей решили, что проще
 сделать на паскале... А вообще проблема-то невелика - встроенным ассемблером
 загрузить-выгрузить число в сопроцессор... Хотя все операции переписывать
 придется...
 
 AZ> Операция взятия остатка для чисел с плавающей запятой -
 AZ> fmod(double,double) или что то типа того.
 
 Это да, но для такой точности она ничего путевого не скажет, подозреваю...
 Вот сейчас поэксперементировал с взятием остатка от деления 1.24Е+3000 на
 1.23Е+3000 - получилось нецелое число...
 
 RG>> void
 RG>> Power(TLong&result,TLong val,TLong power,TLong mod){
 RG>>   TLong curVal=val;
 RG>>   result=1;
 RG>>   while(power){
 RG>>     if(power&1)
 RG>>       result=(result*curVal)%mod;
 RG>>     curVal=(curVal*curVal)%mod;
 RG>>     power>> =1;
 RG>>   }/*while*/
 RG>> }/*Power*/
 AZ> Здесь ты полностью прав. Такой способ прокатывает. Всё сходится. У
 AZ> меня это немного по другому реализовано реализовано:
 
 Hе, дружище, ты чуть-чуть неправильно понял - в твоем алгоритме E итераций, в
 предложенном Евгением Ключниковым (и описанном мной) log2(E). Идея вкратце
 такова - мы пользуемся тем, что A^(B+C)=A^B*A^C - и расчитываем значение A^X для
 следующих X:
 1,2,4,8,16,32...
 Путем возведения в квадрат каждого предыдущего и потом перемножаем нужные
 значения (то есть те, для которых соответствующий бит в показателе установлен):
 A^25=
 A^11001b=
 A^10000b+A^1000+A^1
 а эти значения мы расчитываем в цикле за 6 итераций...
 
 AZ> Блин, ну это чудовищно медленно.
 
 Hу цикл с Е итерациями где Е порядка 1Е+24 это не просто медленно... это вообще 
 никак ;)
 
 AZ> Мне по мылу Kluchnikov Eugene прислал алгоритмик  там число операций
 AZ> не e, а log2(e).
 
 Вот это оно и есть - вообще учителя программирования любят задавать этот вопрос 
 на засыпку...
 
 AZ> Пока не смог с ним разобратся, обозначения непонятные или я туплю %)
 
 Hичего - я-то его понял исключительно потому, что уже знал, что должно
 получиться %)
 
 AZ> Как это примерно выглядит допустим на  Си.
 
 Вот так, как я выше и написал... ;)
 
 с почтеньем,
 Rodion
 
 ---
  * Origin:  (2:5030/1286.6)
 
 

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

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