Алгоритм скалярного умножения для эллиптической кривой
на хабре есть статья по данной тематике https://habr.com/ru/post/335906/
Для операции сложения там все описано подробно, а для умножения одна единственная формула.
Допустим у нас есть входные данные. Px, Py. [4,6.78]
Подскажите как найти для этих точек Qx, Qy
Ответы (1 шт):
Здесь на слайде 7 есть формула сложения точек и формула удвоения точки эллиптической кривой:
https://mipt.ru/education/chair/radio_engineering/infsec/2008/seminars/Seminar_6.pdf
Под удвоением точки понимаем операцию Q = 2 * P = P + P
- Путь простой, но медленный
Для Q = n * P производим n сложений точки P: Q = (((P + P) + P) + P) + ...
Складывать точки мы умеем по формуле со слайда.
Это работает медленно.
- Можно быстрее
Для нахождения точки Q = n * P применим алгоритм, работающий так же, как и бинарное возведение в степень.
Например, для Q = 6 * P:
Q = 6 * P = 2 * (P + 2 * P)
В получившемся выражении фигурируют только операции сложения и удвоения, а их мы умеем выполнять.
Псевдокод:
Q = P
Пока n > 0:
Если n - чётное, то Q = 2 * Q, n = n / 2
иначе Q = P + 2 * Q, n = (n - 1) / 2
Подробнее:
https://e-maxx.ru/algo/binary_pow
https://moluch.ru/archive/15/1426/