Сложение точек на эллиптической кривой
Сложение точек на эллиптической кривой: через хорду, удвоение через касательную и то же самое по модулю простого числа — основа эллиптической криптографии.
Как решать
На кривой $y^2 = x^3 + ax + b$ точки можно складывать: прямая через $P$ и $Q$ пересекает кривую в третьей точке, и её отражение относительно оси $x$ — это $P + Q$. Для $P + P$ вместо хорды берут касательную. Те же формулы работают по модулю простого $p$ — на этом стоит эллиптическая криптография.
По шагам
- Наклон: для хорды $\lambda = \frac{y_2 - y_1}{x_2 - x_1}$, для касательной (удвоение) $\lambda = \frac{3x_1^2 + a}{2y_1}$.
- Абсцисса результата: $x_3 = \lambda^2 - x_1 - x_2$ (при удвоении $x_2 = x_1$).
- Ордината: $y_3 = \lambda(x_1 - x_3) - y_1$ — это уже отражённая третья точка.
- По модулю $p$: деление — это умножение на обратный по модулю $p$, все вычисления ведите остатками.
Где ошибаются
- Отвечают третьей точкой пересечения, забыв отразить её: знак ординаты нужно поменять (в формуле это уже учтено).
- При удвоении пользуются формулой хорды — знаменатель становится нулём.
- В касательной забывают коэффициент $a$: $\lambda = \frac{3x_1^2 + a}{2y_1}$.
- По модулю $p$ делят как обычные дроби, а не умножают на обратный.