Găsiți parametrii curbei eliptice, a și b, având în vedere două puncte de pe curbă

Date două puncte pe curbă $P=(x_1,y_1), Q=(x_2,y_2)$ putem determina parametrii formei Weierstrass scurte $y^2 = x^2 + ax +b$. Introduceți coordonatele punctelor în ecuația curbei pentru a obține două ecuații așa cum ați făcut;

\begin{align} y_1^2 &= x_1^3 + ax_1 + b &\pmod{n} \ y_2^2 &= x_2^3 + ax_2 + b &\pmod{n}\ \hline & & \text{subtract}\ 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{align}

Pentru a putea găsi $a$ singura problemă este existenţa inversă multiplicativă modulară de $(x_1 - x_2)$ la $\bmod n$.

• Dacă $\gcd((x_1 - x_2),n) = 1$ atunci inversul multiplicativ modular există și poate fi ușor de găsit cu Algoritm euclidian extins (Ext-GCD)
• Dacă $\gcd((x_1 - x_2),n) \neq 1$ atunci nu există invers (vezi Ce se întâmplă mai jos).
• Rețineți că, în cazul $x_1 - x_2 = 0$ atunci noi avem $\gcd(0,n) = n.$ Cu alte cuvinte, nu există invers.

O singura data $a$ este găsit cu succes, găsind $b$ este mai usor. Introduceți cunoscutul în ecuație, apoi rezolvați singura necunoscută $b$.

SageMath pentru inversul modular;

Zn = numere întregi (12)
a = Zn(5)
b = a^-1
A

dacă este setat $a = 4$ atunci vei primi eroarea: ZeroDivisionError: inversul lui Mod(4, 12) nu există.

Ce-ar fi dacă Nu există inversul lui $(x_1 - x_2)$ la $\bmod{n}$. Putem găsi soluții pentru mai jos?

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

Da, încă putem găsi soluții $\ref{a}$ dar nu vor fi unice.

Lema: Dacă $d$ este cel mai mare divizor comun al lui a și m apoi congruența liniară $ax \equiv b \pmod m$ are solutii daca si numai daca $d$ desparte $b$. Dacă $d$ desparte $b$, atunci sunt exact $d$ solutii

Pentru a le găsi, de la $a/d \cdot x \equiv b/d \pmod{m/d}$. Este clar că $\gcd(a/d,m/d)=1$. Apoi putem inversa $a/d$ si rezolva pt $x$. Atunci $\{x, x+\dfrac{m}{d},x+\dfrac{2m}{d}, \ldots, x+\dfrac{(d-1)m}{d} \}$ sunt cele $d$ soluții pentru ecuație $\ref{a}$.

Pentru fiecare dintre soluții, se așteaptă să aibă o altă soluție $b$, prin urmare, pentru a determina în mod unic, vor fi necesare informații suplimentare.