(EN) METHOD FOR THE CONSTRUCTION OF ELLIPTIC CURVES OVER FINITE FIELDS

(DE) VERFAHREN ZUR KONSTRUKTION ELLIPTISCHER KURVEN ÜBER ENDLICHEN KÖRPERN

(EN) The invention relates to a method for constructing elliptic curves E over finite fields based on the equation M = P + 1 + x (where ‖x‖ ≤ 2√P; P represents a prime power while E represents an elliptic curve over the field F_p comprising P elements), accordingly 4P = x² + y²‖D‖ (where y ϵ N and the discriminant D = f²D₀ of the order of conductor f in the imaginary quadratic number field K of discriminant D₀), by using module functions g so as to have access to large discriminant values ‖D‖. According to the invention, the module functions g are characterized in that the degree of g(&agr;) is a real divisor of h (h being the ideal class number of the order of K to the discriminant D) while the coefficients of the associated minimal polynomials are small.

(DE) Die Erfindung betrifft ein Verfahren zur Konstruktion elliptischer Kurven E über endlichen Körpern ausgehend von der Gleichung M = P + 1 + x (mit ‖x‖ ≤ 2√P; P ist eine Primzahlpotenz und E ist eine elliptische Kurve über dem Körper F_P mit P Elementen), entsprechend 4P = x² + y²‖D‖ (mit y ∈ N und der Diskriminante D = f²D₀ der Ordnung im Führer f im imaginär-quadratischen Zahlkörper K der Diskriminante D₀), unter Nutzung von Modulfunktionen g zum Gewinnen von Zugang zu großen Diskrimantenbeträgen ‖D‖. Erfindungsgemäß ist vorgesehen, dass die Modulfunktionen g die Eigenschaft aufweisen, dass der Grad von g(&agr;) ein echter Teiler von h (h ist die Ideal-klassenzahl der Ordnung von K zur Diskriminante D) ist und die Koeffizienten der zugeordneten Minimalpolynome klein sind.