Методы и задачи криптографической защиты информации. Мартынов А.И. - 87 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

a
25
mod n = (a*a
24
) mod n = (a* a
8
*a
16
) mod n =
(a*(( a
2
)
2
)
2
*((( a
2
)
2
)
2
)
2
)mod n = (a*((( a*a
2
)
2
)
2
)
2
)mod n
С продуманным сохранением промежуточных результатов вам
понадобится только шесть умножений:
(((((((a
2
mod n)*a)
2
mod n)
2
mod n)
2
mod n)
2
mod n)
2
*a) mod n
Такой прием называется цепочкой сложений, или методом двоичных
квадратов и умножения. Он использует простую и очевидную цепочку
сложений, в основе которой лежит двоичное представление числа. На языке Cи
это выглядит следующим образом:
unsigned long qe2(unsigned long x, unsigned long y, unsigned
long n) {
unsigned long s, t, u;
int i;
s=1; t=x; u=y;
while (u) {
if(u&1) s=(s*t)%n;
u>>1;
t=(t*t)%n;
}
return(s)

Страницы