ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Rodion Gorkovenko                    2:5030/1286.6  03 May 2003  09:06:00
 To : Alexandr Zhizhin
 Subject : RSA
 -------------------------------------------------------------------------------- 
 

 02 May 03 17:06, you wrote to All:
 AZ> Интересует вопрос как можно реализовать быстрое возведение в степень
 AZ> y=x^e mod n, если x, e, n - 25-значные числа (double long).
 
 Извиняюсь - как обычно сразу сообщу, что в данном вопросе я человек
 малосведущий... Уточнить, в общем, хочется постановку задачи "реализовать
 быстрое возведение в степень" или "реализовать быстрое вычисление указанного
 выражения"... Относительно первого можно заподозрить, что даже если возвести
 самое маленькое 25-значное число (1Е+24) в самую маленькую 25-значную степень
 (тоже 1Е+24), то получится о-о-очень много - если я не туплю, то результат будет
 что-то типа единицы с 2.4Е+25 нулями... Записать такое количество цифр, видимо
 будет некуда... %) И в long double, кажется, верных знаков штук 19... И вообще
 нетвердо ясно, как применять для взятия остатка числа с плавающей запятой, для
 которых деление нецелочисленное и знаки теряются... Можно, конечно, использовать
 внутренний целочисленный тип сопроцессора (который в паскале называется comp) - 
 но, скорее всего, придется сочинять свою арифметику...
 
 Относительно второго можно отметить, что X^E%N = (X%N)^E%N... Hаверное...
 Hу а дальше возводим в степень дедовским методом:
 void
 Power(TLong&result,TLong val,TLong power,TLong mod){
   TLong curVal=val;
   result=1;
   while(power){
     if(power&1)
       result=(result*curVal)%mod;
     curVal=(curVal*curVal)%mod;
     power>>=1;
   }/*while*/
 }/*Power*/
 Если, конечно, я ничего не попутал... Правда операция взятия остатка от деления 
 длинных чисел меня смущает...
 
 с почтеньем,
 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