×

Elliptic curves over finite fields and the computation of square roots mod p. (English) Zbl 0579.14025

Der erste Teil dieser Arbeit beschreibt einen deterministischen Algorithmus zur Berechnung der Anzahl von Punkten auf elliptischen Kurven über endlichen Körpern \({\mathbb{F}}_ q\). Die Grundidee ist die folgende: Für hinreichend viele Primzahlen \(\ell\) wird die Spur des Frobeniusendomorphismus mittels \(\ell\)-adischer Darstellung approximiert. Anschließend wird ein Verfahren angegeben, das Quadratwurzeln modulo Primzahlen p aus ganzen Zahlen x zieht. Der Zusammenhang zum ersten Algorithmus besteht darin, daß man x als Diskriminante eines Endomorphismenringes einer geeigneten (zu berechnenden) elliptischen Kurve ansieht. Der erste Algorithmus benötigt \(O(\log^ 9q)\) elementare Operationen, der zweite (bei festem x) \(O(\log^ 9p)\).
Reviewer: H.-G.Rück

MSC:

14H45 Special algebraic curves and curves of low genus
14-04 Software, source code, etc. for problems pertaining to algebraic geometry
12-04 Software, source code, etc. for problems pertaining to field theory
11T06 Polynomials over finite fields
14G15 Finite ground fields in algebraic geometry
14H52 Elliptic curves
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI