внює O , тобто є нейтральним елементом складання. Далі запускається цикл з кількістю кроків, рівним довжині k у двійковій формі запису. На кожному кроці якщо k i = 1, то Q складається з точкою P . Наприкінці кожного кроку P подвоюється. Алгоритм складається тільки з операцій додавання двох точок та операцій подвоєння точки. Тому обчислювальний час алгоритму залежить тільки від часу обчислення суми двох точок і від часу подвоєння точки.
Якщо точка P відома заздалегідь, то можна зробити деякі попередні обчислення для підвищення ефективності алгоритму. Наприклад, обчисливши всі крапки 2P, 2 2 P ... 2 t-1 P можна значно прискорити обчислення скалярного твору. Обчислювальний час алгоритму буде залежати тільки від часу обчислення суми двох точок.
Алгоритм генерації випадкових кривих
Алгоритм цифрового підпису з використанням еліптичних кривих (ECDSA) прийнятий і описаний в різних стандартах. Серед них ANSI X9.62, FIPS 186-2 (NIST), IEEE 1363-2000, ISO/IEC 14888-3, ISO/IEC 15946-3, SEC-1, SEC-2 та ін
Далі ми опишемо основні рекомендації стандарту ANSI X9.62 ECDSA. До еліптичним кривим пред'являються такі вимоги:
. Криві розглядаються або над простими полями (порядок q яких дорівнює простому числу p ), або над полями характеристики два (у яких q = 2 m ).
. Для представлення елементів поля використовується або стандартний базис, породжуваний тричленного або пятичленную, або гаусів нормальний базис (GNB). p align="justify"> 3. Крива E задається вибором двох елементів a, b поля GF (q) . У разі p> 2 вона має вигляд y 2 = x 3 + ax + b , а в разі p = 2 вид y 2 ...
