/ /

MSRI-UP 2010 Research Topic

MSRI-UP 2010: Elliptic Curves and Applications

Home Research Topic People Research Projects Pictures

Topic and Projects

Topic: Elliptic Curves and Applications

An elliptic curve E is an arithmetic-algebraic object: It is simultaneously a nonsingular projective curve with an affine equation, which allows one to perform arithmetic on its points; and a finitely generated abelian group, which allows one to apply results from abstract algebra. The goal for this summer will be to learn about elliptic curves and give applications by using their properties to study problems in other fields.

Students will first take a short course for two (2) weeks to cover any necessary background from abstract algebra and discrete mathematics. For the remainder of the program, the students break up into smaller groups and work on research projects. They will have a choice of one of the following projects:

Project 1: ABC Conjecture

This deceptively simple question was first outlined in 1985 by Joseph Oesterlé and David Masser. Consider three relatively prime positive integers A, B, C, such that A+B=C. Let rad(ABC) denote the product of the distinct prime factors of ABC; computational evidence suggests that there it is rare to have C > rad(ABC). To be more precise, given any positive number e, there should only exist finitely many (A:B:C) such that the quality q(A:B:C) = log(C)/log(rad(ABC)) is greater than 1+e.

This project seeks to use elliptic curves to search for triples (A:B:C) with exceptionally large quality q(A:B:C). The approach will be to use properties of certain families of elliptic curves which are classified according to their isogenous curves. For example, the triple (33:5:25) has a rather low quality of q=1.01898, whereas the triple (3:53:27) has a rather large quality of q=1.42657. These triples correspond to elliptic curves which are 3-isogeneous to each other.

Project 2: Elliptic Curve Cryptography

There are two aspects when discussing secrets: how to safely encrypt a message so that an unauthorized party cannot read it, and how to effectively decrypt a message so that an authorized party can. This project seeks to have students learn about the Discrete Logarithm Problem, by writing computer code. Students will engage in a friendly competition of passing secrets: one encrypts, while the other eavesdrops!

The method of encryption using elliptic curves is a type of Public Key cryptosystem, an idea first put forth by Whitfield Diffie and Martin Hellman in 1976. One takes a message, expresses each character as a positive integer (using say UTF-8), then encodes the message as a positive integer. One can then perform mathematics on this integer using a shared elliptic curve, and then send this encrypted message to a friend. This process is known as Elliptic Curve Diffie-Hellman (ECDH).

The method of decrypting using elliptic curves is a variant of Pollard's (p-1) Algorithm, an idea first put forth by Hendrik Lenstra in 1987. One wishes to solve the Elliptic Curve Discrete Logarithm Problem (ECDLP) by factoring an integer using elliptic curves. One chooses a random point on a random elliptic curve, then uses the group law to eventually find a factor which allows one to invert the discrete logarithms. This process is known as Elliptic Curve Factorization Method (ECM).