Elliptiska_kurvor.sagews

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()[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

($\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()[0]  # Funktionen returnera en lista av punkter. Vi väljer med [0] 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[0])

PARI/GP interpreter

y = ZZ(lift(punkter[0]))
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 [removed]

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!