CoCalc Public FilesSage genom exempel / Elliptiska_kurvor.sagewsOpen with one click!
Download, Raw, Embed
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 Q\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
y2=x3−32x+74\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()[0]
Q = -4P
R = P + Q
p, Q , R
punkter = sum([plot(p, pointsize = 20, color = 'black') for p in [P, Q, R]])
kurva + punkter
((131169:−45094394:1)\displaystyle \left(\frac{131}{169} : -\frac{4509}{4394} : 1\right), (296110000:11540411000000:1)\displaystyle \left(\frac{2961}{10000} : \frac{1154041}{1000000} : 1\right), (131169:−45094394:1)\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 GF(p)\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
y2=x3+2x+1\displaystyle y^2 = x^{3} + 2 x + 1 
E.plot(aspect_ratio = 1)
Hur många punkter innehåller EE?
E.cardinality()
1208\displaystyle 1208
Låt PP vara en punkt i EE med vilken vi kan genererar samtliga punkter i EE.
P = E.gens()[0]  # Funktionen returnera en lista av punkter. Vi väljer med [0] det första av dem.
P
(143:174:1)\displaystyle \left(143 : 174 : 1\right)
Notera att punkten lagras med så kallade projektiva koordinater enligt förhållandet (a:b:c)↔(a/c,b/c)(a : b : c) \leftrightarrow (a/c, b/c). Oändlighetspunkten O\mathcal{O} representeras av (0:1:0)(0 : 1 : 0).
P.xy()  # konvertera till formatet (x, y)
(143\displaystyle 143, 174\displaystyle 174)
Med hjälp av PP kan vi genererar andra punkter på EE.
Q = P + P + P + P + P + P + P + P
Q
(657:489:1)\displaystyle \left(657 : 489 : 1\right)
Vi får samma punkt om vi multiplicerar PP med 8.
8 P
(657:489:1)\displaystyle \left(657 : 489 : 1\right)
Antag att vi vill välja ut en punkt på EE med ett givet xx-värde, t.ex. x=642x = 642, under förutsättning att en sådan punkt finns. Med hjälp av Pari/GP kan vi bestämma motsvarande yy-koordinat.
x = 642
punkter = list(gp.ellordinate(E, x))
punkter
[Mod(862, 1213)\displaystyle \verb|Mod(862, 1213)|, Mod(351, 1213)\displaystyle \verb|Mod(351, 1213)|]
Funktionen reurnerar två yy-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 PP. 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[0])
PARI/GP interpreter 
y = ZZ(lift(punkter[0]))
y
862\displaystyle 862
print parent(y)
Integer Ring 
R = E(x, y)
R
(642:862:1)\displaystyle \left(642 : 862 : 1\right)
Addition av punkter över den elliptiska kurvan är implemeterad.
P + Q
(725:972:1)\displaystyle \left(725 : 972 : 1\right)
38 P + 705 R
(1104:913:1)\displaystyle \left(1104 : 913 : 1\right)
P - P
(0:1:0)\displaystyle \left(0 : 1 : 0\right)
Hur många kopior av QQ måste vi addera för att nå oändlighetspunkten?
n = Q.order()
n
151\displaystyle 151
n Q
(0:1:0)\displaystyle \left(0 : 1 : 0\right)
Låt oss kontrollera att det stämmer genom att verifiera att kQ≠OkQ \neq \mathcal{O} för alla k<nk < n.
all(k Q != E(0, 1, 0) for k in [1..n-1])
True\displaystyle \mathrm{True}
Eftersom PP är en generator för EE, så är ordningen för PP lika med antal element i EE.
P.order()
1208\displaystyle 1208
Den diskreta logaritmen log⁡PQ\log_P Q är det minsta positiva heltal nn sådant att nP=QnP = Q.
P.discrete_log(Q)
8\displaystyle 8
Svaret ovan stämmer med vår definition av QQ. Men även RR kan erhållas med hjälp av PP.
n = P.discrete_log(R)
n
159\displaystyle 159
n P == R
True\displaystyle \mathrm{True}
En illustration av additionen P+QP + 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 kPkP, där k=1,2,…,Nk = 1, 2, \ldots, N, och rita en linje mellan varje par kPkP och (k+1)P(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,…,10PP, 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!