arrow-left

All pages
gitbookPowered by GitBook
1 of 1

Loading...

Resources and notations

hashtag
References/Resources

  1. Nguyen, P. Q., & Vallée, B. (Eds.). (2010). The LLL Algorithm. Information Security and Cryptography. doi:10.1007/978-3-642-02295-1

    Massive survey, lots of detail if you're extremely interested)

  2. May, A. (2003). New RSA Vulnerabilities Using Lattice Reduction Methods. Universität Paderborn.

    Excellent exposition to LLL and coppersmith as well as showing some RSA attacks via LLL

  3. Lenstra, A. K., Lenstra, H. W., & Lovász, L. (1982). Factoring polynomials with rational coefficients. Mathematische Annalen, 261(4), 515–534. doi:10.1007/bf01457454

    The original LLL paper, quite a nice read overall + proof that LLL works

  4. Coppersmith, D. (1996). Finding a Small Root of a Univariate Modular Equation. Lecture Notes in Computer Science, 155–165. doi:10.1007/3-540-68339-9_14

  5. Coppersmith, D. (1996). Finding a Small Root of a Bivariate Integer Equation; Factoring with High Bits Known. Lecture Notes in Computer Science, 178–189. doi:10.1007/3-540-68339-9_16

    Both of these paper introduces the coppersmith algorithm as well as provide some examples

  6. Waerden, B. L. (1956). Die Reduktionstheorie Der Positiven Quadratischen Formen. Acta Mathematica, 96(0), 265–309. doi:10.1007/bf02392364

hashtag
Notation

  • lattice

    • dimension of lattice

    • volume of lattice

bib_ibi​ a chosen basis for LLL

  • B\mathcal BB matrix whose iiith row vectors is bib_ibi​

  • bi∗b_i^*bi∗​ Gram-Schmidt orthogonalization of bib_ibi​(without normalization)

    • B∗\mathcal B^*B∗matrix whose iiith row vectors is bi∗b_i^*bi∗​

  • μi,j=⟨bi,bj∗⟩⟨bj∗,bj∗⟩\mu_{i,j}=\frac{\langle b_i,b_j^*\rangle}{\langle b_j^*,b_j^*\rangle}μi,j​=⟨bj∗​,bj∗​⟩⟨bi​,bj∗​⟩​ Gram-Schmidt coefficients

  • λi(L)\lambda_i(L)λi​(L) the iiith successive minima of LLL

  • LLL
    dim⁡(L)\dim(L)dim(L)
    vol(L)\text{vol}(L)vol(L)