Найдите параметры эллиптической кривой, a и b, учитывая две точки на кривой

Даны две точки на кривой $P=(x_1,y_1), Q=(x_2,y_2)$ мы можем определить параметры короткой формы Вейерштрасса $y^2 = x^2 + топор +b$. Вставьте координаты точек в уравнение кривой, чтобы получить два уравнения, как вы это сделали;

\начать{выравнивать} y_1^2 &= x_1^3 + ax_1 + b &\pmod{n} \ y_2^2 &= x_2^3 + ax_2 + b &\pmod{n}\ \hline & & \text{вычитание}\ y_1^2 - y_2^2 &= x_1^3 - x_2^3 + a (x_1 - x_2) &\pmod{n}\ (y_1 ^ 2 - y_2 ^ 2) - (x_1 ^ 3 - x_2 ^ 3)&= a (x_1 - x_2) &\pmod{n}\ [(y_1^2 - y_2^2) -(x_1^3 - x_2^3)] \cdot (x_1 - x_2)^{-1}&= a &\pmod{n}\ \end{выравнивание}

Чтобы иметь возможность найти $а$ проблема только в существовании модульный мультипликативный обратный из $(x_1 - x_2)$ к $\bмод п$.

• Если $\gcd((x_1 - x_2),n) = 1$ тогда модулярная мультипликативная обратная существует и может быть легко найдена с помощью Расширенный алгоритм Евклида (Ext-GCD)
• Если $\gcd((x_1 - x_2),n) \neq 1$ тогда нет обратного (см. Что, если ниже).
• Отметим, что в случае $x_1 - x_2 = 0$ тогда у нас есть $\gcd(0,n) = n.$ Другими словами, обратного нет.

Один раз $а$ успешно найден, находя $b$ это проще. Подставьте известное в уравнение, затем найдите единственное неизвестное. $b$.

SageMath для модульной инверсии;

Zn = целые числа (12)
а = Zn(5)
б = а^-1
а

если установлено $а = 4$ то вы получите ошибку: ZeroDivisionError: инверсия Mod(4, 12) не существует.

Что, если Нет обратного $(x_1 - x_2)$ к $\bmod{n}$. Можем ли мы найти решения ниже?

$$(y_1^2 - y_2^2) -(x_1^3 - x_2^3)= a (x_1 - x_2) \pmod{n} \label{a}\tag{1}$$

Да, мы все еще можем найти решения для $\ref{а}$ но они не будут уникальными.

Лемма: Если $д$ является наибольшим общим делителем a и m, то линейная конгруэнция $ax \equiv b \pmod m$ имеет решения тогда и только тогда, когда $д$ делит $b$. Если $д$ делит $b$, то есть ровно $д$ решения

Чтобы найти их, из $a/d \cdot x \equiv b/d \pmod{m/d}$. Ясно, что $\gcd(а/д,м/д)=1$. Тогда мы можем инвертировать $а/д$ и решить для $х$. затем $\{x, x+\dfrac{m}{d},x+\dfrac{2m}{d}, \ldots, x+\dfrac{(d-1)m}{d} \}$ являются $д$ решения уравнения $\ref{а}$.

Ожидается, что для каждого из решений будет свой $b$, поэтому для однозначного определения потребуется дополнительная информация.