Open in CoCalc

Elliptiska kurvor

typeset_mode(True) implicit_multiplication(True)

Det rationella fallet

Låt oss börja med att kort studera en elliptisk kurva över kroppen $\mathbb{Q}$.
E = EllipticCurve(QQ, [-3/2, 7/4]) print E
Elliptic Curve defined by y^2 = x^3 - 3/2*x + 7/4 over Rational Field
E
$\displaystyle y^2 = x^{3} - \frac{3}{2} x + \frac{7}{4}$
Det är enkelt att rita kurvan.
kurva = E.plot(aspect_ratio = 1, xmax = 2.75) show(kurva) Illustration av addiion över en elliptisk kurva.
P = E.gens() Q = -4P R = P + Q p, Q , R punkter = sum([plot(p, pointsize = 20, color = 'black') for p in [P, Q, R]]) kurva + punkter
($\displaystyle \left(\frac{131}{169} : -\frac{4509}{4394} : 1\right)$, $\displaystyle \left(\frac{2961}{10000} : \frac{1154041}{1000000} : 1\right)$, $\displaystyle \left(\frac{131}{169} : -\frac{4509}{4394} : 1\right)$) %html <h2> Ellitpiska kurvor över ändliga kroppar </h2> Det är lika enkelt att definiera en elliptisk kurva över kroppen $\mathrm{GF}(p)$.

Ellitpiska kurvor över ändliga kroppar

Det är lika enkelt att definiera en elliptisk kurva över kroppen $\mathrm{GF}(p)$.
p = 1213 E = EllipticCurve(GF(p), [2, 1]) print E
Elliptic Curve defined by y^2 = x^3 + 2*x + 1 over Finite Field of size 1213
E
$\displaystyle y^2 = x^{3} + 2 x + 1$
E.plot(aspect_ratio = 1) Hur många punkter innehåller $E$?
E.cardinality()
$\displaystyle 1208$
Låt $P$ vara en punkt i $E$ med vilken vi kan genererar samtliga punkter i $E$.
P = E.gens() # Funktionen returnera en lista av punkter. Vi väljer med  det första av dem. P
$\displaystyle \left(143 : 174 : 1\right)$
Notera att punkten lagras med så kallade projektiva koordinater enligt förhållandet $(a : b : c) \leftrightarrow (a/c, b/c)$. Oändlighetspunkten $\mathcal{O}$ representeras av $(0 : 1 : 0)$.
P.xy() # konvertera till formatet (x, y)
($\displaystyle 143$, $\displaystyle 174$)
Med hjälp av $P$ kan vi genererar andra punkter på $E$.
Q = P + P + P + P + P + P + P + P Q
$\displaystyle \left(657 : 489 : 1\right)$
Vi får samma punkt om vi multiplicerar $P$ med 8.
8 P
$\displaystyle \left(657 : 489 : 1\right)$
Antag att vi vill välja ut en punkt på $E$ med ett givet $x$-värde, t.ex. $x = 642$, under förutsättning att en sådan punkt finns. Med hjälp av Pari/GP kan vi bestämma motsvarande $y$-koordinat.
x = 642 punkter = list(gp.ellordinate(E, x)) punkter
[$\displaystyle \verb|Mod(862, 1213)|$, $\displaystyle \verb|Mod(351, 1213)|$]
Funktionen reurnerar två $y$-värden. Notera att gp.ellordinate returnerar en Pari/GP-lista, därför omvandlar vi den med funktionen list till en datatyp som Sage förstår. Vi väljer den första av dem när vi definierar en punkt $P$. För att undvika eventuella problem då vi längre fram ska utföra beräkningar typomvandlar vi utdata från Pari/GP till en datatyp som passar Sage.
print parent(punkter)
PARI/GP interpreter
y = ZZ(lift(punkter)) y
$\displaystyle 862$
print parent(y)
Integer Ring
R = E(x, y) R
$\displaystyle \left(642 : 862 : 1\right)$
Addition av punkter över den elliptiska kurvan är implemeterad.
P + Q
$\displaystyle \left(725 : 972 : 1\right)$
38 P + 705 R
$\displaystyle \left(1104 : 913 : 1\right)$
P - P
$\displaystyle \left(0 : 1 : 0\right)$
Hur många kopior av $Q$ måste vi addera för att nå oändlighetspunkten?
n = Q.order() n
$\displaystyle 151$
n Q
$\displaystyle \left(0 : 1 : 0\right)$
Låt oss kontrollera att det stämmer genom att verifiera att $kQ \neq \mathcal{O}$ för alla $k < n$.
all(k Q != E(0, 1, 0) for k in [1..n-1])
$\displaystyle \mathrm{True}$
Eftersom $P$ är en generator för $E$, så är ordningen för $P$ lika med antal element i $E$.
P.order()
$\displaystyle 1208$
Den diskreta logaritmen $\log_P Q$ är det minsta positiva heltal $n$ sådant att $nP = Q$.
P.discrete_log(Q)
$\displaystyle 8$
Svaret ovan stämmer med vår definition av $Q$. Men även $R$ kan erhållas med hjälp av $P$.
n = P.discrete_log(R) n
$\displaystyle 159$
n P == R
$\displaystyle \mathrm{True}$
En illustration av additionen $P + Q$.
addition = point(P.xy()) addition += text('P', P.xy(), vertical_alignment = 'bottom', horizontal_alignment = 'right') addition += point(Q.xy()) addition += text('Q', Q.xy(), vertical_alignment = 'top', horizontal_alignment = 'right') PQ = P + Q addition += point(PQ.xy()) addition += text('P + Q', PQ.xy(), vertical_alignment = 'bottom', horizontal_alignment = 'left') addition.show() Vi kan även markera alla punkter $kP$, där $k = 1, 2, \ldots, N$, och rita en linje mellan varje par $kP$ och $(k+1)P$.
def rita_kP(P, N) : kP = P bild = point(P.xy()) for k in [2..N] : bild += point((kP + P).xy()) bild += line([kP.xy(), (kP + P).xy()]) kP += P bild.show(aspect_ratio=1)
Punktera $P, 2P, \ldots, 10P$.
rita_kP(P, 10) Samtliga punkter (vi bestämmer alla punkter utom oändlighetspunkten för att undvika programkörningsfel).
rita_kP(P, P.order() - 1) Försök följa polygontåget om du kan!