Reducing lattice bases to find small-height values of univariate polynomials

D.J. Bernstein

    Research output: Chapter in Book/Report/Conference proceedingChapterAcademic


    This paper illustrates, improves, and unifies a variety of previous results on finding divisors in residue classes (Lenstra, Konyagin, Pomerance, Coppersmith, Howgrave-Graham, Nagaraj), divisors in short intervals (Rivest, Shamir, Coppersmith, Howgrave-Graham), modular roots (Håstad, Vallée, Girault, Toffin, Coppersmith, Howgrave-Graham), highpower divisors (Boneh, Durfee, Howgrave-Graham), and codeword errors beyond half distance (Sudan, Guruswami, Goldreich, Ron, Boneh).
    Original languageEnglish
    Title of host publicationAlgorithmic Number Theory
    EditorsJ.P. Buhler, P. Stevenhagen
    Place of PublicationCambridge
    PublisherCambridge University Press
    ISBN (Print)978-0-521-80854-5
    Publication statusPublished - 2008

    Publication series

    NameMathematical Sciences Research Institute Publications


    Dive into the research topics of 'Reducing lattice bases to find small-height values of univariate polynomials'. Together they form a unique fingerprint.

    Cite this