Finding small solutions of equations: from cryptanalysis to error-correcting codes


Henry Cohn

Microsoft Research New England

Northeastern University

Thursday, April 15, 2010


Talk at 4:30 p.m. in 509 Lake Hall

Tea at 4:00 p.m. in 544 Nightingale Hall


Abstract:   Many important problems in discrete mathematics and theoretical computer science, such as attacking the RSA cryptosystem or decoding error-correcting codes, can be reduced to finding small solutions of polynomial equations. In this talk, Iíll survey a general approach that has been independently developed in several different areas, and Iíll discuss various applications of these techniques, including recent joint work with Nadia Heninger on a number-theoretic analogue of the problem of decoding algebraic-geometric error-correcting codes. No special background in cryptography or coding theory will be assumed.

Here are some directions to Northeastern University. Lake Hall and Nightingale Hall can be best accessed from the entrance on the corner of Greenleaf Street and Leon Street. The two halls are connected, with no well-defined boundary in between. In particular, 509 Lake Hall is on the same corridor as 544 Nightingale Hall.

There is free parking available for people coming to the Colloquium at Northeastern's visitor parking (Rennaisance Garage). The entrance is from Columbus Avenue. If coming by car, you should park there and take the parking talon. After the lecture, you may pick up the payment coupon from Andrei Zelevinsky.

Home Web page:  Alexandru I. Suciu  Comments to:  
Posted:: April 8, 2010    URL: