Type: Seminar

Distribution: World

Expiry: 9 Jan 2008

ALTERATION TO PREVIOUSLY ADVERTISED SEMINAR! The seminar on Wednesday will be a double-header. Note also change of room. Speaker: Damien Stehle Title: Hard Lattice Problems & Strong Reductions Time & Place: 3pm-3:45pm, Wednesday 9 January, Carslaw 535 Abstract: Continuing talk of Monday 7 January. Topics include . Lattice point enumeration . Strong reductions . Enumeration and strong reductions together . Hard lattice functions . Applications of strong reductions in cryptanalysis and computer arithmetic . New and further developments Speaker: Nicolas Brisebarre Title: Machine-efficient polynomial approximants Time & Place: 4:10pm-4:55pm, Wednesday 9 January, Carslaw 535 Abstract: Polynomial approximations are often used when implementing functions on a computing system. In most cases, the polynomial that best approximates (for a given distance and in a given interval) a function has coefficients that are not exactly representable with a finite number of bits. And yet, the polynomial approximations that are actually implemented do have coefficients that are represented with a finite - and sometimes small - number of bits: this is due to the finiteness of the floating-point representations (for software implementations), and to the need to have small, hence fast and/or inexpensive, multipliers (for hardware implementations). We then have to consider polynomial approximations for which the degree-$i$ coefficient has at most $m_i$ fractional bits: in other words, it is a rational number with denominator $2^{m_i}$. We provide one general method, based on linear programming, for finding the best polynomial approximation under this constraint and another method, fast and efficient, based on lattice reduction, that gives a very good approximant under this constraint. Moreover, our methods also apply if some other constraints (such as requiring some coefficients to be equal to some predefined constants, or minimizing relative error instead of absolute error) are required. This is a joint work with Sylvain Chevillard, Jean-Michel Muller and Serge Torres.