Быстрые алгоритмы вычисления преобразований на основе эллиптических кривых с предварительными вычислениями

10 / 14

Рис. 3. Сравнение средней вычислительной сложности предлагаемого алгорит-
ма as\wNAF (1) и алгоритма Хенкерсона (2) скалярного умножения точки на
подмножестве эллиптических кривых P 192 ⊂ E
begin
/* Предварительные вычисления */
1. P 1 ← P
2. P 2 ← dbl (P )
3. foreach (i = 3, 5, . . . , 2 (2w − (−1)w)/3 − 1) {
4. Pi ← add (Pi −2, P2)
5. }
/* Основные вычисления */
6. Q ← O
7. i ← d − 1
8. while ( i ≥ 0) {
9. j ← 0
10. z ← i
11. while (j ≤ w ) {
12. if ((di , . . . , di−j+1 ) mod 2 ≡ 0) {
13. z ← j
14. }
15. j ← j + 1
16. }
17. Q ← 2 z−1Q
18. if (m > 0) {
19. Q ← d a (Q, Pm)
20. } else {
21. if ( m < 0) {
22. Q ← da (Q, −P −m)
23. } else {
24. Q ← dbl (Q)
25. }
26. }
27. i ← i − t
28. }
29. return( Q)
end
74 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2015. № 3