Resources and notations

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

Notation

  • LL lattice

    • dim(L)\dim(L)dimension of lattice

    • vol(L)\text{vol}(L)volume of lattice

  • bib_i a chosen basis for LL

    • B\mathcal B matrix whose iith row vectors is bib_i

  • bib_i^* Gram-Schmidt orthogonalization of bib_i(without normalization)

    • B\mathcal B^*matrix whose iith row vectors is bib_i^*

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

  • λi(L)\lambda_i(L) the iith successive minima of LL