Rings of endomorphisms of elliptic curves and Mestre's theorem

Eliptické křivky jsou mocným nástrojem dnešní doby. Jednak přispěly k vyřešení mnoha matematických problémů, ale také nalezly četná uplatnění v aplikacích, jako je například kryptografie založená na eliptických křivkách (ECC). Tato metoda veřejného klíče má velkou budoucnost, neboť v mnohém doplňuje nedostatky známé RSA metody. Jedním z hlavních problémů kryptografie založené na eliptických křivkách je určení řádu eliptické křivky, tedy výpočet počtu bodů eliptické křivky nad prvočíselným polem. Tomuto zásadnímu problému je věnována tato práce. Na určení řádu eliptické křivky existuje řada algoritmů. Pro menší prvočísla (čili pro charakteristiku prvočíselného pole) se užívá metoda založená na přímém výpočtu, tzv. naivní algoritmus. Velkou pomocí v této problematice je Hasseho teorém, který omezuje řád eliptické křivky intervalem. Pro větší prvočísla se s úspěchem používají Shanksův algoritmus a jeho vylepšení Mestreho algoritmus. Oba algoritmy mají dvě části - Baby Step a Giant Step. Shanksův algoritmus je však v určitých případech nepoužitelný a tento problém řeší Mestreho algoritmus, který používá pojem twist eliptické křivky. Díky Mestreho teorému bylo dokázáno, že řád eliptické křivky nad prvočíselným polem muže být spočten pro každé prvočíslo vetší než 457. Důkaz, který spočívá především v isomorfismu okruhu endomorfismů nad eliptickými křivkami a imaginárního kvadratického řádu, je uveden na závěr této práce.The elliptic curves are a powerful tool at present. First, they helped to solve many mathematical problems, but they also found their place in numerous applications, such as Elliptic Curve Cryptography (ECC). This public key encryption has a great future, because it solve the drawbacks of the famous RSA method. One of main the problems of the Elliptic Curve Cryptography is the determination of the elliptic curve’s order, i.e. calculating the number of elliptic curve’s points over the prime field. In this thesis we will deal with this fundamental problem. For determining of elliptic curve’s order there exist several algorithms. For smaller prime numbers (i.e. the characteristics of the prime field) we have the algorithm, which uses direct calculation, called the Naive algorithm. A great assist in this issue is the Hasse’s Theorem, which states that the elliptic curve’s order has a bound - Hasse’s interval. Shank’s algorithm and its improvement Mestre’s algorithm are successfully used for larger prime numbers. Both algorithms have two parts called the Baby Step and the Giant Step. Shank’s algorithm is in some cases unusable, and this problem is solved by Mestre’s algorithm with the twist of elliptic curve. Thanks to Mestre’s Theorem, it was proved that the order of the elliptic curves over the prime field can be computed for each prime number greater than 457. The proof, which consists primarily in the isomorphism of elliptic curve’s endomorphism’s ring and the imaginary quadratic order, is mentioned at the end of this work.