Eliptická křivka: Porovnání verzí

Z Wikipedie, otevřené encyklopedie
Smazaný obsah Přidaný obsah
Bez shrnutí editace
Bez shrnutí editace
Řádek 23: Řádek 23:


Pokud by nastala situace, kdy <math>P=Q</math> a <math>y=0</math>, jeho zdvojením tečna protne eliptickou křivku v nekonečnu v pomyslném bodě O, řekneme tedy, že <math>2P=O</math>. Pokud bychom chtěli bod P ztrojnásobit, získáme opět bod P, neboť platí <math>3P=2P+P=O+P=P</math>.
Pokud by nastala situace, kdy <math>P=Q</math> a <math>y=0</math>, jeho zdvojením tečna protne eliptickou křivku v nekonečnu v pomyslném bodě O, řekneme tedy, že <math>2P=O</math>. Pokud bychom chtěli bod P ztrojnásobit, získáme opět bod P, neboť platí <math>3P=2P+P=O+P=P</math>.

==== Algebraicky ====
Další možností, jak sčítat body na eliptické křivce, je použití algebraických výpočtů. Tento způsob je nutný například u kryptografie na bázi eliptických křivek.

V první řadě musíme určit směrnici přímky, na které leží body P a Q. Tuto směrnici s vypočítáme jako <math>\textrm{tg}\, \alpha</math>, tedy <math>s=\frac{y_{p}-y_{q}}{x_{p}-x_{q}}</math>.

Díky Viète-Newtonovým vztahům můžeme říct, že pokud Q &ne; &minus;P, pak <math>x_{R} = s^2 - x_{P} - x_{Q}</math>, <math>y_{R} = s(x _{P}-x_{Q}) - y_{P}</math>.

Verze z 29. 10. 2010, 15:40

Eliptická křivka je hladká spojitá křivka, na které definujeme bod O, což je bod v nekonečnu.

Její rovnice je , což lze upravit na tzv. Weierstrassův tvar .

Pokud platí, že , kde a, b jsou koeficienty z Weierstrassova tvaru, pak není křivka nesingulární (má ostrý bod) a nejedná se tedy o eliptickou křivku.

Eliptická křivka nad reálnými čísly

Eliptickou křivku nad reálnými čísly můžeme definovat jako skupinu souřadnic [x;y], které vyhovují rovnici , kde a, b, x, y ∈ .

Pokud je daná eliptická křivka nesingulární, může zformovat grupu.

Sčítání bodů na eliptické křivce

Graficky

Grupy eliptických křivek jsou aditivní grupy, to znamená, že základní operace je zde sčítání. Sčítání dvou bodů na eliptické křivce je definováno geometricky.

Opačný bod k bodu P[x;y] je bod −P[x;−y], je tedy zobrazen osovou souměrností posle osy x. Ke každému bodu P existuje bod −P.

Předpokládejme, že body P a Q jsou dva různé body na eliptické křivce a že −P ≠ Q. Abychom tyto dva body sečetli graficky, musíme jimi proložit přímku, která eliptickou křivku protne ještě v právě jednom bodě. Tento bod můžeme nazvat −R. Obraz tohoto bodu je hledaný bod R, kde platí .

Pokud by platilo, že , pak můžeme říct, že že bod Q je opačný k bodu P, tedy že mají stejnou souřadnici x. Sečteme-li tyto dva body (proložíme-li jimi přímku), nezískáme další průsečík s eliptickou křivkou. Tato přímka však eliptickou křivku protne v nekonečnu v pomyslném bodu O, můžeme tedy říct, že .

Pokud by nastala situace, že , pak bychom mohli říct, že chceme bod P zdvojnásobit. Tuto operaci učiníme tak, že uděláme tečnu k eliptické křivce s bodem dotyku P. Tato tečna protne eliptickou křivku v právě jednou bodě, který můžeme nazvat −R, jeho obraz R je bod, který hledáme.

Pokud by nastala situace, kdy a , jeho zdvojením tečna protne eliptickou křivku v nekonečnu v pomyslném bodě O, řekneme tedy, že . Pokud bychom chtěli bod P ztrojnásobit, získáme opět bod P, neboť platí .

Algebraicky

Další možností, jak sčítat body na eliptické křivce, je použití algebraických výpočtů. Tento způsob je nutný například u kryptografie na bázi eliptických křivek.

V první řadě musíme určit směrnici přímky, na které leží body P a Q. Tuto směrnici s vypočítáme jako , tedy .

Díky Viète-Newtonovým vztahům můžeme říct, že pokud Q ≠ −P, pak , .