Schoof, René Elliptic curves over finite fields and the computation of square roots mod p. (English) Zbl 0579.14025 Math. Comput. 44, 483-494 (1985). 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 Cited in 15 ReviewsCited in 138 Documents 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 Keywords:finite fields; factorization; polynomials; computational number; theory; algorithm; number of points on elliptic curves over finite; field; Frobenius; square root PDFBibTeX XMLCite \textit{R. Schoof}, Math. Comput. 44, 483--494 (1985; Zbl 0579.14025) Full Text: DOI