An elliptic curve $E$ is a set of points satisfying an equation of form $$ y^2 = x^3 + ax + b, $$ where $4a^3 + 27b^2 \ne 0$, together with a "point at infinity", denoted by $\mathcal{O}$.
Let us first draw a graph of a cubic polynomial, followed by the corresponding elliptic curve.
@interact
def _(a=slider(-5, 5, default=-2),
b=slider(-5, 5, default=-2),
xr=range_slider(-10, 10, default=(-3, 3), label="x range"),
yr=range_slider(-10, 10, default=(-5, 5), label="y range")):
x, y = var('x y')
E = x^3 + a*x + b
xlim = (x, *xr)
ylim = (y, *yr)
show(plot(E, xlim))
show(implicit_plot(y^2 == E, xlim, ylim, frame=False, axes=True))
Interactive function <function _ at 0x7f2171260b80> with 4 widgets a: TransformIntSlider(value=-2, descripti…
Let us now demonstrate the group addition operation on the elliptic curve.
@interact
def _(a=slider(-5, 5, default=-2),
b=slider(-5, 5, default=-2),
Px=slider(-10, 10, default=2),
Ps=slider(["-", "+"], default="+", label="Py sign"),
Qx=slider(-10, 10, default=3),
Qs=slider(["-", "+"], default="-", label="Qy sign"),
xr=range_slider(-10, 10, default=(-3, 3), label="x range"),
yr=range_slider(-10, 10, default=(-5, 5), label="y range")):
x, y = var('x y')
s = {"+": 1, "-": -1}
E = x^3 + a*x + b
pts = []
Py = s[Ps] * sqrt(E.subs(x == Px))
if Py.is_real():
pts.append((Px, Py))
Qy = s[Qs] * sqrt(E.subs(x == Qx))
if Qy.is_real():
pts.append((Qx, Qy))
xlim = (x, *xr)
ylim = (y, *yr)
p = implicit_plot(y^2 == E, xlim, ylim, frame=False, axes=True)
if pts:
p += point(pts, color="red", size=50)
if len(pts) > 1:
if pts[0] == pts[1] and Py != 0:
lm = (3*Px^2 + a)/(2*Py)
elif Px != Qx:
lm = (Py - Qy)/(Px - Qx)
else:
pts += [(Px, yr[0]), (Px, yr[1])]
if len(pts) == 2:
Rx = lm^2 - Px - Qx
Ry = lm * (Px - Rx) - Py
R = [(Rx, Ry), (Rx, -Ry)]
pts.append(R[1])
p += point(R[0], color="magenta", size=50)
p += point(R[1], color="brown", size=50)
if Ry != 0:
p += line2d(R, color="cyan")
p += line2d(pts, color="green")
show(p, xmin=xr[0], xmax=xr[1], ymin=yr[0], ymax=yr[1])
Interactive function <function _ at 0x7f216bf055e0> with 8 widgets a: TransformIntSlider(value=-2, descripti…
Let us find the points on the elliptic curve $y^2 = x^3 + x + 6$ over ${\mathbb{Z}_{11}}$.
a = 10
b = 5
p = 17
(4 * a^3 + 27 * b^2) % p
0
from algorithms.ellipticCurves import points, pointSum, pointMultiply
a, b, p = E = (1, 6, 11)
(pts := points(E))
[(), (2, 4), (2, 7), (3, 5), (3, 6), (5, 2), (5, 9), (7, 2), (7, 9), (8, 3), (8, 8), (10, 2), (10, 9)]
len(pts)
13
P = (8, 3)
Q = (3, 6)
pointSum(P, Q, E)
(3, 5)
pointMultiply(5, P, E)
(5, 2)
P = (2, 4)
d = 3
(Q := pointMultiply(d, P, E))
(8, 8)
m = 7
r = 4
(R := pointMultiply(r, P, E))
(10, 9)
(S := pointMultiply(r, Q, E))
(2, 7)
z = m * S[0] % p
(c := (R, z))
((10, 9), 3)
pointMultiply(d, R, E)
(2, 7)
z * S[0]^-1 % p
7