Недавно наткнулся на дискуссию на форуме "MyMathForum"
Трюк Шамира
С помощью этого метода вычисление суммы двухточечных умножение происходит быстрее, чем вычислять их отдельно. Итак, в основном мы хотим получить результат kP + sQ. Если мы переставим два скаляра в блоках w-битов и перемешивая эти куски, мы получим новый скаляр
кусков окна двойного размера и 2-битного окна. Затем мы можем предварительно вычислить все 22w комбинации iP + jQ с i = 0 ... 2
w − 1
и j = 0 ... 2
w - 1. Наконец, мы запускаем метод обычного окна. Следовательно, число сложений удваивается, но число двойников остается неизменным. Этот трюк можно применять в различных формах. Наиболее тривиальное приложение для проверки подписи ECDSA, где появляется точно такое же выражение, как и выше. Но и нормальные скалярные умножения могут быть
приведены в такой форме. Если, например, мы заранее знаем базовую точку и скаляр
имеет 192 бита, мы можем предварительно вычислить 296P, а затем разбить скаляр для вычисления k96 (296P) + k0P.
Однако, даже если базовая точка заранее не известна, существуют эффективные вычислимые эндоморфизмы для некоторых кривых, которые все еще позволяют набирать скорость, применяя этот метод