Алгоритм 3.3. Возведение в степень (справа-налево)

ВХОД: Целые числа а, х=(x _t x _t-1 …х _o)₂, p.

ВЫХОД: Число у=а^х mod p.

1. у 1, sа.

2. FOR i =0, 1,..., t DO

3. IF х_i= 1 THEN yy·s mod p;

4. ss·s mod p.

5. RETURN y.

Чтобы показать, что по представленному алгоритму действительно вычисляется у согласно (3.6), запишем степени переменных после каждой итерации цикла. Пусть х= 100=(1100100)₂, как в примере 2.1, тогда:

i: 0 1 2 3 4 5 6

х_i: 0 0 1 0 0 1 1

у: 1 1 а⁴ а⁴ а⁴ а³⁶ а¹⁰⁰

s: а² а⁴ а⁸ а¹⁶ а³² а⁶⁴ а¹²⁸

Приведенных в данном разделе сведений из теории чисел будет достаточно для описания основных криптографических алгоритмов и методов.

Дата добавления: 2014-01-11