##### Department of Mathematics,

University of California San Diego

****************************

### Math 209 - Number Theory

## Dr. Kristin Lauter

#### Microsoft

## Computing modular polynomials and applications to cryptography

##### Abstract:

(Joint work with Denis Charles) The nth modular polynomial parameterizes pairs of elliptic curves with an isogeny of degree n between them. Modular polynomials provide the defining equations for modular curves, and are useful in many different aspects of computational number theory and cryptography. For example, computations with modular polynomials have been used to speed elliptic curve point-counting algorithms. The standard method for computing modular polynomials consists of computing the Fourier expansion of the modular j-function and solving a linear system of equations to obtain the integral coefficients. The computer algebra package MAGMA incorporates a database of modular polynomials for n up to 59. The idea of the talk is to compute the modular polynomial directly modulo a prime p, without first computing the coefficients as integers. Once the modular polynomial has been computed for enough small primes, our approach can also be combined with the Chinese Remainder Theorem (CRT) approach to obtain the modular polynomial with integral coefficients or with coefficients modulo a much larger prime using Explicit CRT. Our algorithm does not involve computing Fourier coefficients of modular functions.

Host: Audrey Terras

### October 14, 2004

### 2:00 PM

### AP&M 7321

****************************