Find Elliptic Curve Parameters, a and b, Given Two Points on the Curve

Given two point on the curve $P=(x_1,y_1), Q=(x_2,y_2)$ we can determine the parameters of the short Weierstrass form $y^2 = x^2 + ax +b$. Insert the coordinates of points to the curve equation to get two equations as you did;

\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}

To be able to find $a$ the only problem is the existence of the modular multiplicative inverse of $(x_1 - x_2)$ to the $\bmod n$.

• If $\gcd((x_1 - x_2),n) = 1$ then the modular multiplicative inverse is exist and can be easily found with Extended Euclidean algorithm (Ext-GCD)
• If $\gcd((x_1 - x_2),n) \neq 1$ then there is no inverse (see What if below).
• Note that, in the case $x_1 - x_2 = 0$ then we have $\gcd(0,n) = n.$ In other words, there is no inverse.

Once $a$ is successfully found, finding $b$ is easier. Plug the known into the equation then solve for the only unknown $b$.

SageMath for the modular inverse;

Zn = Integers(12)
a = Zn(5)
b = a^-1
a

if set $a = 4$ then you will get the error: ZeroDivisionError: inverse of Mod(4, 12) does not exist.

What if There is no inverse of $(x_1 - x_2)$ to $\bmod{n}$. Can we find solutions to below?

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

Yes, we can still find solutions to $\ref{a}$ but they will not be unique.

Lemma: If $d$ is the greatest common divisor of a and m then the linear congruence $ax \equiv b \pmod m$ has solutions if and only if $d$ divides $b$. If $d$ divides $b$, then there are exactly $d$ solutions

To find them, from $a/d \cdot x \equiv b/d \pmod{m/d}$. It is clear that $\gcd(a/d,m/d)=1$. Then we can invert $a/d$ and solve for $x$. Then $\{x, x+\dfrac{m}{d},x+\dfrac{2m}{d}, \ldots, x+\dfrac{(d-1)m}{d} \}$ are the $d$ solutions for equation $\ref{a}$.

For each of the solutions, it is expected to have a different $b$, therefore for uniquely determine additional information will be needed.