Algoritmus Schoofs - Schoofs algorithm - Wikipedia

Schoofův algoritmus je efektivní algoritmus, na který se počítají body eliptické křivky přes konečná pole. Algoritmus má aplikace v kryptografie eliptické křivky kde je důležité znát počet bodů k posouzení obtížnosti řešení problém diskrétního logaritmu v skupina bodů na eliptické křivce.

Algoritmus publikoval René Schoof v roce 1985 a byl to teoretický průlom, protože to byl první deterministický polynomiální časový algoritmus pro počítání bodů na eliptických křivkách. Před Schoofovým algoritmem se přístupy k počítání bodů na eliptických křivkách, jako jsou naivní a baby-step obří krok algoritmy byly z větší části zdlouhavé a měly exponenciální dobu běhu.

Tento článek vysvětluje Schoofův přístup a klade důraz na matematické myšlenky, které jsou základem struktury algoritmu.

Úvod

Nechat ${ displaystyle E}$ být eliptická křivka definováno přes konečné pole ${ displaystyle mathbb {F} _ {q}}$, kde ${ displaystyle q = p ^ {n}}$ pro ${ displaystyle p}$ hlavní a ${ displaystyle n}$ celé číslo ${ displaystyle geq 1}$. Přes pole charakteristik ${ displaystyle neq 2,3}$ eliptická křivka může být dána (krátkou) Weierstrassovou rovnicí

${ displaystyle y ^ {2} = x ^ {3} + Axe + B}$

s ${ displaystyle A, B in mathbb {F} _ {q}}$. Sada definovaných bodů ${ displaystyle mathbb {F} _ {q}}$ se skládá z řešení ${ displaystyle (a, b) v mathbb {F} _ {q} ^ {2}}$ splnění křivkové rovnice a bod v nekonečnu ${ displaystyle O}$. Za použití skupinové právo na eliptických křivkách omezených na tuto množinu je vidět, že tato množina ${ displaystyle E ( mathbb {F} _ {q})}$ tvoří abelianská skupina, s ${ displaystyle O}$ jako nulový prvek. Abychom mohli spočítat body na eliptické křivce, vypočítáme mohutnost ${ displaystyle E ( mathbb {F} _ {q})}$.Schoofův přístup k výpočtu mohutnosti ${ displaystyle #E ( mathbb {F} _ {q})}$ využívá Hasseova věta o eliptických křivkách spolu s Čínská věta o zbytku a dělící polynomy.

Hasseova věta

Hasseova věta říká, že pokud ${ displaystyle E / mathbb {F} _ {q}}$ je eliptická křivka přes konečné pole ${ displaystyle mathbb {F} _ {q}}$, pak ${ displaystyle #E ( mathbb {F} _ {q})}$ splňuje

${ displaystyle mid q + 1 - # E ( mathbb {F} _ {q}) mid leq 2 { sqrt {q}}.}$

Tento silný výsledek, který poskytl Hasse v roce 1934, zjednodušuje náš problém zúžením ${ displaystyle #E ( mathbb {F} _ {q})}$ do konečné (byť velké) sady možností. Definování ${ displaystyle t}$ být ${ displaystyle q + 1 - # E ( mathbb {F} _ {q})}$a s využitím tohoto výsledku nyní máme výpočetní hodnotu ${ displaystyle t}$ modulo ${ displaystyle N}$ kde ${ displaystyle N> 4 { sqrt {q}}}$, postačuje k určení ${ displaystyle t}$, a tudíž ${ displaystyle #E ( mathbb {F} _ {q})}$. I když neexistuje žádný efektivní způsob výpočtu ${ displaystyle t { pmod {N}}}$ přímo pro generála ${ displaystyle N}$, je možné počítat ${ displaystyle t { pmod {l}}}$ pro ${ displaystyle l}$ malý prime, spíše efektivně. Vybíráme si ${ displaystyle S = {l_ {1}, l_ {2}, ..., l_ {r} }}$ být soubor odlišných prvočísel taková, že ${ displaystyle prod l_ {i} = N> 4 { sqrt {q}}}$. Dáno ${ displaystyle t { pmod {l_ {i}}}}$ pro všechny ${ displaystyle l_ {i} v S}$, Čínská věta o zbytku umožňuje nám počítat ${ displaystyle t { pmod {N}}}$.

Aby bylo možné počítat ${ displaystyle t { pmod {l}}}$ pro nejlepšího ${ Displaystyle l neq p}$, využíváme teorii Frobeniova endomorfismu ${ displaystyle phi}$ a dělící polynomy. Vezměte na vědomí, že vzhledem k prvočíslům ${ Displaystyle l neq p}$ není žádná ztráta, protože vždy můžeme vybrat větší prime, aby se ujistil, že je produkt dostatečně velký. V každém případě se při řešení případu nejčastěji používá Schoofův algoritmus ${ displaystyle q = p}$ protože existují účinnější, tzv ${ displaystyle p}$ adické algoritmy pro pole s malou charakteristikou.

Frobeniova endomorfismus

Vzhledem k eliptické křivce ${ displaystyle E}$ definováno přes ${ displaystyle mathbb {F} _ {q}}$ považujeme body za ${ displaystyle E}$ přes ${ displaystyle { bar { mathbb {F}}} _ {q}}$, algebraické uzavření z ${ displaystyle mathbb {F} _ {q}}$; tj. povolujeme body se souřadnicemi v ${ displaystyle { bar { mathbb {F}}} _ {q}}$. The Frobeniova endomorfismus z ${ displaystyle { bar { mathbb {F}}} _ {q}}$ přes ${ displaystyle mathbb {F} _ {q}}$ sahá až k eliptické křivce o ${ displaystyle phi: (x, y) mapsto (x ^ {q}, y ^ {q})}$.

Tato mapa je totožnost na ${ displaystyle E ( mathbb {F} _ {q})}$ a lze jej rozšířit do bodu v nekonečnu ${ displaystyle O}$, což je a skupinový morfismus z ${ displaystyle E ({ bar { mathbb {F} _ {q}}})}$ pro sebe.

Frobeniova endomorfismus uspokojuje kvadratický polynom, který souvisí s mohutností ${ displaystyle E ( mathbb {F} _ {q})}$ podle následující věty:

Teorém: Frobeniova endomorfismus daná ${ displaystyle phi}$ splňuje charakteristickou rovnici

${ displaystyle phi ^ {2} -t phi + q = 0,}$ kde ${ displaystyle t = q + 1 - # E ( mathbb {F} _ {q})}$

Tak to máme pro všechny ${ displaystyle P = (x, y) v E}$ že ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) + q (x, y) = t (x ^ {q}, y ^ {q})}$, kde + označuje sčítání na eliptické křivce a ${ displaystyle q (x, y)}$ a ${ displaystyle t (x ^ {q}, y ^ {q})}$označit skalární násobení ${ displaystyle (x, y)}$ podle ${ displaystyle q}$ a ze dne ${ displaystyle (x ^ {q}, y ^ {q})}$ podle ${ displaystyle t}$.

Jeden by se mohl pokusit tyto body symbolicky spočítat ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}})}$, ${ displaystyle (x ^ {q}, y ^ {q})}$ a ${ displaystyle q (x, y)}$ jako funkce v souřadnicový kruh ${ displaystyle mathbb {F} _ {q} [x, y] / (y ^ {2} -x ^ {3} -Ax-B)}$ z ${ displaystyle E}$a poté vyhledejte hodnotu ${ displaystyle t}$ který splňuje rovnici. Stupně se však velmi zvětšují a tento přístup je nepraktický.

Schoofovým nápadem bylo provést tento výpočet omezený na procedurální body ${ displaystyle l}$ pro různé malé prvočísla ${ displaystyle l}$. Oprava lichého prime ${ displaystyle l}$nyní přejdeme k řešení problému určování ${ displaystyle t_ {l}}$, definováno jako ${ displaystyle t { pmod {l}}}$, pro dané prvočíslo ${ displaystyle l neq 2, p}$. Pokud bod ${ displaystyle (x, y)}$ je v ${ displaystyle l}$-torzní podskupina ${ displaystyle E [l] = {P v E ({ bar { mathbb {F} _ {q}}}) střední lP = O }}$, pak ${ displaystyle qP = { bar {q}} P}$ kde ${ displaystyle { bar {q}}}$ je jedinečné celé číslo takové, že ${ displaystyle q equiv { bar {q}} { pmod {l}}}$ a ${ displaystyle mid { bar {q}} mid$. Všimněte si, že ${ displaystyle phi (O) = O}$ a to pro jakékoli celé číslo ${ displaystyle r}$ my máme ${ Displaystyle r phi (P) = phi (rP)}$. Tím pádem ${ displaystyle phi (P)}$ bude mít stejné pořadí jako ${ displaystyle P}$. Tak pro ${ displaystyle (x, y)}$ patřící ${ displaystyle E [l]}$, také máme ${ displaystyle t (x ^ {q}, y ^ {q}) = { bar {t}} (x ^ {q}, y ^ {q})}$ -li ${ displaystyle t equiv { bar {t}} { pmod {l}}}$. Proto jsme náš problém zredukovali na řešení rovnice

${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) + { bar {q}} (x, y) equiv { bar {t}} (x ^ { q}, y ^ {q}),}$

kde ${ displaystyle { bar {t}}}$ a ${ displaystyle { bar {q}}}$ mít celočíselné hodnoty v ${ displaystyle [- (l-1) / 2, (l-1) / 2]}$.

Výpočet modulo připraví

The lth dělení polynomu je takový, že jeho kořeny jsou přesně X souřadnice bodů objednávky l. Tedy omezit výpočet ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) + { bar {q}} (x, y)}$ do l-torsion points means computing these expressions as functions in the coordinate ring of E a modulo the lpolynom 5.tý dělení. Tj. pracujeme ${ displaystyle mathbb {F} _ {q} [x, y] / (y ^ {2} -x ^ {3} -Ax-B, psi _ {l})}$. To zejména znamená, že stupeň X a Y definováno prostřednictvím ${ displaystyle (X (x, y), Y (x, y)): = (x ^ {q ^ {2}}, y ^ {q ^ {2}}) + { bar {q}} ( x, y)}$ je maximálně 1 palec y a nanejvýš ${ displaystyle (l ^ {2} -3) / 2}$v X.

Skalární násobení ${ displaystyle { bar {q}} (x, y)}$ lze provést buď pomocí zdvojnásobit a přidat metod nebo pomocí ${ displaystyle { bar {q}}}$polynom 5.tý dělení. Druhý přístup dává:

${ displaystyle { bar {q}} (x, y) = (x _ { bar {q}}, y _ { bar {q}}) = left (x - { frac { psi _ {{ bar {q}} - 1} psi _ {{ bar {q}} + 1}} { psi _ { bar {q}} ^ {2}}}, { frac { psi _ { 2 { bar {q}}}} {2 psi _ { bar {q}} ^ {4}}} vpravo)}$

kde ${ displaystyle psi _ {n}}$ je npolynom 5.tý dělení. Všimněte si, že ${ displaystyle y _ { bar {q}} / rok}$ je funkce v X pouze a označte to ${ displaystyle theta (x)}$.

Musíme rozdělit problém na dva případy: případ, ve kterém ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) neq pm { bar {q}} (x, y)}$a případ, ve kterém ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) = pm { bar {q}} (x, y)}$. Všimněte si, že tyto rovnosti jsou kontrolovány modulo ${ displaystyle psi _ {l}}$.

Případ 1: ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) neq pm { bar {q}} (x, y)}$

Pomocí sčítací vzorec pro skupinu ${ displaystyle E ( mathbb {F} _ {q})}$ získáváme:

${ displaystyle X (x, y) = left ({ frac {y ^ {q ^ {2}} - y _ { bar {q}}} {x ^ {q ^ {2}} - x _ { lišta {q}}}} doprava) ^ {2} -x ^ {q ^ {2}} - x _ { bar {q}}.}$

Všimněte si, že tento výpočet selže, pokud byl předpoklad nerovnosti špatný.

Nyní jsme schopni používat X-koordinovat zúžit výběr ${ displaystyle { bar {t}}}$ na dvě možnosti, a to pozitivní a negativní případ. Za použití y-koordinovaný jeden později určí, který ze dvou případů platí.

Nejprve to ukážeme X je funkce v X sama. Zvážit ${ displaystyle (y ^ {q ^ {2}} - y _ { bar {q}}) ^ {2} = y ^ {2} (y ^ {q ^ {2} -1} -y _ { bar {q}} / rok) ^ {2}}$.Od té doby ${ displaystyle q ^ {2} -1}$ je dokonce nahrazením ${ displaystyle y ^ {2}}$ podle ${ displaystyle x ^ {3} + Axe + B}$, přepíšeme výraz na

${ displaystyle (x ^ {3} + Axe + B) ((x ^ {3} + Axe + B) ^ { frac {q ^ {2} -1} {2}} - theta (x)) }$

a mít to

${ displaystyle X (x) equiv (x ^ {3} + Ax + B) ((x ^ {3} + Ax + B) ^ { frac {q ^ {2} -1} {2}} - theta (x)) { bmod { psi}} _ {l} (x).}$

Tady, zdá se, není správné, zahodíme ${ displaystyle x ^ {q ^ {2}} - x _ { bar {q}}}$?

Teď když ${ displaystyle X equiv x _ { bar {t}} ^ {q} { bmod { psi}} _ {l} (x)}$ pro jednoho ${ displaystyle { bar {t}} v [0, (l-1) / 2]}$ pak ${ displaystyle { bar {t}}}$ splňuje

${ displaystyle phi ^ {2} (P) mp { bar {t}} phi (P) + { bar {q}} P = O}$

pro všechny l- torzní body P.

Jak již bylo zmíněno dříve, pomocí Y a ${ displaystyle y _ { bar {t}} ^ {q}}$ nyní jsme schopni určit, která ze dvou hodnot ${ displaystyle { bar {t}}}$ (${ displaystyle { bar {t}}}$ nebo ${ displaystyle - { bar {t}}}$) funguje. To dává hodnotu ${ displaystyle t equiv { bar {t}} { pmod {l}}}$. Schoofův algoritmus ukládá hodnoty ${ displaystyle { bar {t}} { pmod {l}}}$ v proměnné ${ displaystyle t_ {l}}$ za každé prvočíslo l považováno.

Případ 2: ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) = pm { bar {q}} (x, y)}$

Začínáme s předpokladem, že ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) = { bar {q}} (x, y)}$. Od té doby l je liché prvočíslo, to nemůže být ono ${ displaystyle { bar {q}} (x, y) = - { bar {q}} (x, y)}$ a tudíž ${ displaystyle { bar {t}} neq 0}$. Charakteristická rovnice to dává ${ displaystyle { bar {t}} phi (P) = 2 { bar {q}} P}$. A následně to ${ displaystyle { bar {t}} ^ {2} { bar {q}} equiv (2q) ^ {2} { pmod {l}}}$. To z toho vyplývá q je čtvercové modulo l. Nechat ${ displaystyle q equiv w ^ {2} { pmod {l}}}$. Vypočítat ${ displaystyle w phi (x, y)}$ v ${ displaystyle mathbb {F} _ {q} [x, y] / (y ^ {2} -x ^ {3} -Ax-B, psi _ {l})}$ a zkontrolujte, zda ${ displaystyle { bar {q}} (x, y) = w phi (x, y)}$. Pokud ano, ${ displaystyle t_ {l}}$ je ${ displaystyle pm 2w { pmod {l}}}$ v závislosti na souřadnici y.

Li q Ukázalo se, že to není čtvercové modulo l nebo pokud rovnice neplatí pro žádný z w a ${ displaystyle -w}$, náš předpoklad ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) = + { bar {q}} (x, y)}$ je tedy nepravdivé ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}}) = - { bar {q}} (x, y)}$. Charakteristická rovnice dává ${ displaystyle t_ {l} = 0}$.

Další případ ${ displaystyle l = 2}$

Pokud si vzpomínáte, naše první úvahy případ vynechávají ${ displaystyle l = 2}$. Protože předpokládáme q být lichý, ${ displaystyle q + 1-t equiv t { pmod {2}}}$ a zejména ${ displaystyle t_ {2} equiv 0 { pmod {2}}}$ kdyby a jen kdyby ${ displaystyle E ( mathbb {F} _ {q})}$ má prvek pořadí 2. Podle definice přidání do skupiny musí být jakýkoli prvek pořadí 2 ve formě ${ displaystyle (x_ {0}, 0)}$. Tím pádem ${ displaystyle t_ {2} equiv 0 { pmod {2}}}$ právě když je polynom ${ displaystyle x ^ {3} + Axe + B}$ má kořen v ${ displaystyle mathbb {F} _ {q}}$, právě když ${ displaystyle gcd (x ^ {q} -x, x ^ {3} + sekera + B) neq 1}$.

Algoritmus

    Vstup: 1. Eliptická křivka ${ displaystyle E = y ^ {2} -x ^ {3} -Ax-B}$. 2. Celé číslo q pro konečné pole ${ displaystyle F_ {q}}$ s ${ displaystyle q = p ^ {b}, b  geq 1}$. Výstup: Počet bodů E přes ${ displaystyle F_ {q}}$. Vyberte si sadu lichých prvočísel S neobsahující p takhle ${ displaystyle N =  prod _ {l  in S} l> 4 { sqrt {q}}.}$    Dát ${ displaystyle t_ {2} = 0}$ -li ${ displaystyle  gcd (x ^ {q} -x, x ^ {3} + sekera + B)  neq 1}$, jiný ${ displaystyle t_ {2} = 1}$.    Vypočítejte dělící polynom ${ displaystyle  psi _ {l}}$. Jsou provedeny všechny výpočty ve smyčce níže v ringu ${ displaystyle  mathbb {F} _ {q} [x, y] / (y ^ {2} -x ^ {3} -Ax-B,  psi _ {l}).}$    Pro ${ displaystyle l  v S}$ dělat:        Nechat ${ displaystyle { bar {q}}}$ být jedinečné celé číslo takhle ${ displaystyle q  equiv { bar {q}} { pmod {l}}}$ a ${ displaystyle  mid { bar {q}}  mid$.        Vypočítat ${ displaystyle (x ^ {q}, y ^ {q})}$, ${ displaystyle (x ^ {q ^ {2}}, y ^ {q ^ {2}})}$ a ${ displaystyle (x _ { bar {q}}, y _ { bar {q}})}$.           -li ${ displaystyle x ^ {q ^ {2}}  neq x _ { bar {q}}}$ pak            Vypočítat ${ displaystyle (X, Y)}$.            pro ${ displaystyle 1  leq { bar {t}}  leq (l-1) / 2}$ dělat:                -li ${ displaystyle X = x _ { bar {t}} ^ {q}}$ pak                    -li ${ displaystyle Y = y _ { bar {t}} ^ {q}}$ pak                        ${ displaystyle t_ {l} = { bar {t}}}$;                    jiný                        ${ displaystyle t_ {l} = - { bar {t}}}$.        jinak pokud q je čtvercové modulo l pak            vypočítat w s ${ displaystyle q  equiv w ^ {2} { pmod {l}}}$            vypočítat ${ displaystyle w (x ^ {q}, y ^ {q})}$            -li ${ displaystyle w (x ^ {q}, y ^ {q}) = (x ^ {q ^ {2}}, y ^ {q ^ {2}})}$ pak                ${ displaystyle t_ {l} = 2 t}$            jinak pokud ${ displaystyle w (x ^ {q}, y ^ {q}) = (x ^ {q ^ {2}}, - y ^ {q ^ {2}})}$ pak                ${ displaystyle t_ {l} = - 2 t}$            jiný                ${ displaystyle t_ {l} = 0}$        jiný            ${ displaystyle t_ {l} = 0}$    Použijte Čínská věta o zbytku počítat t modulo N        z rovnic ${ displaystyle t  equiv t_ {l} { pmod {l}}}$, kde ${ displaystyle l  v S}$. Výstup ${ displaystyle q + 1-t}$.

Složitost

Většina výpočtu je převzata z vyhodnocení ${ displaystyle phi (P)}$ a ${ displaystyle phi ^ {2} (P)}$, pro každý prime ${ displaystyle l}$, to je výpočetní technika ${ displaystyle x ^ {q}}$, ${ displaystyle y ^ {q}}$, ${ displaystyle x ^ {q ^ {2}}}$, ${ displaystyle y ^ {q ^ {2}}}$ za každé prvočíslo ${ displaystyle l}$. To zahrnuje umocňování v kruhu ${ displaystyle R = mathbb {F} _ {q} [x, y] / (y ^ {2} -x ^ {3} -Ax-B, psi _ {l})}$ a vyžaduje ${ displaystyle O ( log q)}$ násobení. Od stupně ${ displaystyle psi _ {l}}$ je ${ displaystyle { frac {l ^ {2} -1} {2}}}$, každý prvek v kruhu je polynom stupně ${ displaystyle O (l ^ {2})}$. Podle věta o prvočísle, jsou kolem ${ displaystyle O ( log q)}$ prvočísla velikosti ${ displaystyle O ( log q)}$, což dává ${ displaystyle l}$ je ${ displaystyle O ( log q)}$ a my to získáme ${ displaystyle O (l ^ {2}) = O ( log ^ {2} q)}$. Tedy každé násobení v kruhu ${ displaystyle R}$ vyžaduje ${ displaystyle O ( log ^ {4} q)}$ násobení v ${ displaystyle mathbb {F} _ {q}}$ což zase vyžaduje ${ displaystyle O ( log ^ {2} q)}$ bitové operace. Celkově počet bitových operací pro každé prvočíslo ${ displaystyle l}$ je ${ displaystyle O ( log ^ {7} q)}$. Vzhledem k tomu, že tento výpočet je třeba provést pro každou z ${ displaystyle O ( log q)}$ prvočísla, celková složitost Schoofova algoritmu se ukáže být ${ displaystyle O ( log ^ {8} q)}$. Použití rychlé polynomiální a celočíselné aritmetiky to snižuje na ${ displaystyle { tilde {O}} ( log ^ {5} q)}$.

Vylepšení Schoofova algoritmu

V 90. letech Noam Elkies, následován A. O. L. Atkin, vymyslel vylepšení základního algoritmu Schoofa omezením množiny prvočísel ${ displaystyle S = {l_ {1}, ldots, l_ {s} }}$ považována za prvočísla určitého druhu. Tito se začali jmenovat Elkiesova prvočísla a Atkinova prvočísla. Prime ${ displaystyle l}$ se nazývá Elkies prime, pokud je charakteristická rovnice: ${ displaystyle phi ^ {2} -t phi + q = 0}$ rozdělí se ${ displaystyle mathbb {F} _ {l}}$, zatímco Atkin prime je prime, který není elkies prime. Atkin ukázal, jak kombinovat informace získané z Atkinových prvočísel s informacemi získanými z Elkiesových prvočísel, aby vytvořil efektivní algoritmus, který se stal známým jako Algoritmus Schoof – Elkies – Atkin. Prvním problémem, který je třeba řešit, je zjistit, zda daný prime je Elkies nebo Atkin. K tomu využíváme modulární polynomy, které vycházejí ze studia modulární formy a výklad eliptické křivky nad komplexními čísly jako mříže. Jakmile jsme určili, ve kterém případě se nacházíme, místo použití dělící polynomy, jsme schopni pracovat s polynomem, který má nižší stupeň než odpovídající dělící polynom: ${ displaystyle O (l)}$ spíše než ${ displaystyle O (l ^ {2})}$. Pro efektivní implementaci se používají pravděpodobnostní algoritmy pro hledání kořenů, což z ní činí Algoritmus Las Vegas spíše než deterministický algoritmus. Za heuristického předpokladu, že přibližně polovina připraví až ${ displaystyle O ( log q)}$ svázané jsou Elkiesovy prvočísla, získá se algoritmus, který je efektivnější než Schoofův, s očekávanou dobou chodu ${ displaystyle O ( log ^ {6} q)}$ pomocí naivní aritmetiky a ${ displaystyle { tilde {O}} ( log ^ {4} q)}$ pomocí rychlé aritmetiky. Ačkoli je známo, že tento heuristický předpoklad platí pro většinu eliptických křivek, není známo, že platí ve všech případech, dokonce ani za GRH.

Implementace

V systému bylo implementováno několik algoritmů C ++ Mike Scott a jsou k dispozici u zdrojový kód. Implementace jsou zdarma (žádné podmínky, žádné podmínky) a využívají MIRACL knihovna, která je distribuována pod AGPLv3.

• Schoofův algoritmus implementace pro ${ displaystyle E ( mathbb {F} _ {p})}$ s prime ${ displaystyle p}$.
• Schoofův algoritmus implementace pro ${ displaystyle E ( mathbb {F} _ {2 ^ {m}})}$.

Viz také

• Kryptografie eliptické křivky
• Počítání bodů na eliptických křivkách
• Polynomy dělení
• Frobeniova endomorfismus

Reference

• R. Schoof: Elliptic Curves over Finite Fields and the Computation of Square Roots mod str. Matematika. Comp., 44 (170): 483–494, 1985. Dostupné na http://www.mat.uniroma2.it/~schoof/ctpts.pdf
• R. Schoof: Počítání bodů na eliptických křivkách přes konečná pole. J. Theor. Nombres Bordeaux 7: 219–254, 1995. Dostupné na http://www.mat.uniroma2.it/~schoof/ctg.pdf
• G. Musiker: Schoofův algoritmus pro počítání bodů ${ displaystyle E ( mathbb {F} _ {q})}$. Dostupné v http://www.math.umn.edu/~musiker/schoof.pdf
• V. Müller: Die Berechnung der Punktanzahl von elliptischen kurven über endlichen Primkörpern. Diplomová práce. Universität des Saarlandes, Saarbrücken, 1991. Dostupné na http://lecturer.ukdw.ac.id/vmueller/publications.php
• A. Enge: Eliptické křivky a jejich aplikace v kryptografii: Úvod. Kluwer Academic Publishers, Dordrecht, 1999.
• L. C. Washington: Eliptické křivky: teorie čísel a kryptografie. Chapman & Hall / CRC, New York, 2003.
• N. Koblitz: Kurz teorie čísel a kryptografie, postgraduální texty z matematiky. No. 114, Springer-Verlag, 1987. Druhé vydání, 1994