David Kohel
University Of Sydney
Applications of class invariants on modular curves
Thursday 24th December, 3:05-4pm
Carslaw 829
A standard problem in elliptic curve cryptography is the selection of
elliptic curves as the basis for a secure cryptosystem. The principle
requirement is that structure of the group of rational points be of
prime or near-prime order. One approach to the problem is to select
curves at random and to count points---an expensive option.
The alternative is to use the theory complex multiplication to construct
elliptic curves with known endomorphism ring structure, whose reduction
is known to have a predetermined number of points. This construction
is also applied to the problem of primality proving. For this purpose
the minimal polynomial of the j-invariant of those curves with fixed
endomorphism ring R is computed over Q, and reduced modulo a prime.
For example for disc(R) = -23, this class polynomial is:
x^3 + 3491750x^2 - 5151296875x + 12771880859375
The disadvantage the size of the coefficients grows in proportion to
the size of the square root of the discrimiant, which limits the
Noting that the function j is a generator for the function field of
the moduli space X(1) of elliptic curves, we can generalize this
construction to use functions on modular curves of higher level which
parametrize an elliptic curve plus additional isogeny structure.
Taking a function on the modular curve X_0(101), the resulting class
polynomial takes the much simpler form:
x^3 - x + 1
We will discuss this construction, its benefits and limitations, and
other applications in constructive class field theory.
|