 CoCalc Public FilesSage genom exempel / Elliptiska_kurvor.sagews
Author: Robert Nyqvist

# 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)$
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 += text('Q', Q.xy(), vertical_alignment = 'top', horizontal_alignment = 'right')
PQ = P + Q
addition += text('P + Q', PQ.xy(), vertical_alignment = 'bottom', horizontal_alignment = 'left') 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!