Coppersmith´s method uses lattice basis reduction to find small roots of polynomials modulo an integer of possibly unknown factorization, a lovely theorem which has many applications in the cryptanalysis of RSA. In the realm of the polynomials, it turns out that the analogue of Coppersmith´s theorem gives a new variant of the Guruswami-Sudan method for efficient list-decoding of Reed-Solomon codes. In this talk, we will develop a framework for solving these problems and show how the lattice method can be extended to more general settings, such as multiple simultaneous equations or solving equations modulo ideals in the ring of integers of a number field.
Penn Mathematics Colloquium
Wednesday, February 5, 2014 - 4:30pm
Nadia Heninger
University of Pennsylvania