2015-05-10
362
Вычисление m-кратной композиции
ВХОД: точка Р, число m = (mt mt-1…m1)2.
ВЫХОД: Q = [m]P.
1 Q ß O;
2 FOR i = t, t-1, …, 1 DO
3 Q ß [2]Q;
4 IF mi = 1 THEN Q ß Q + P;
5 RETURN Q.
Данный алгоритм требует t удвоений и в среднем t/2 сложений.
Пример: Вычислим [21] P. Здесь 21 = (10101)2 , t = 5.
| i | mi | |||
| : | Q ß O, | Q ß Q + P = P; | ||
| : | Q ß [2] Q = [2] P; | |||
| : | Q ß [2] Q = [4] P, | Q ß Q + P = [5] P; | ||
| : | Q ß [2] Q = [10] P; | |||
| : | Q ß [2] Q = [20] P, | Q ß Q + P = [21] P. |
Вместо 20 сложений было выполнено 4 удвоения и 3 сложения.
