Notes for UMich EECS 598 (2015) are for Lattices in Cryptography virtually instructed by Chris Peikert (i.e., I taught myself using resources made available by him). This entry is for lecture 3, LLL, Coppersmith.
In this note, I implement Lenstra–Lenstra–Lovász algorithm and write down another paraphrasing of Coppersmith algorithm (the worse bound). Due to the nature of personal notes, I will not formally put references.
Question. There’s a sentence in the lecture note:
… Therefore, the theorem does appear to yield an efficient factoring algorithm.
It comes with a footnote:
However, it can be used to factor when some partial information about a factor is known.
The two sentences should be contrasting each other. The text should be ‘the theorem does not yield an efficient factoring algorithm’ so the footnote could be led by ‘however’.
This section is an interactive implementation of Lenstra–Lenstra–Lovász algorithm and cannot be printed. The source code is available under the MIT license.
Enter the input basis (an integer matrix with entries of magnitude less than and tap the button. The implementation will compute an LLL-reduced basis and the unimodular change-of-basis matrix s.t. (I thought about having an animated, step-by-step implementation, but then thought that would be too much for me. The source code is available under the MIT license.)
- The algorithm failed to maintain an invariant. This could be due to the input matrix not being full-rank or an interesting bug. Please inform the author if you believe this is an interesting bug.
- The algorithm failed to terminate within 65536 rounds. This could be due to the algorithm taking longer or an interesting bug. Please inform the author if you believe this is an interesting bug.
- LLL-reduced basis
- Change-of-basis matrix
I find it rather unnatural to say is short’. I paraphrase the idea here.
Suppose we want to find all small zeros (with absolute value at most of a monic polynomial modulo We do this by finding a polynomial such that
- the zeros of modulo are also ones of modulo
- the small zeros of modulo are also zeros of as an integer-coefficient polynomial.
In particular, we consider where are integers and are the coefficients of Clearly, any zero of modulo is also a zero of modulo To ensure the small zeros of modulo are also zeros of as an integer-coefficient polynomial, so we require A sufficient condition of the above inequality is that for If we define a sufficient condition of the above inequality is that Moreover, the possible are exactly non-zero points in the lattice generated by Therefore, we can use LLL algorithm to compute a short recover from it and solve it over the reals.
Question. The form of as a multiple of plus a lower-degree polynomial (that vanishes modulo resembles the proof of the fundamental theorem of algebra using Rouché’s theorem. When using Rouché’s theorem, there is no multiple because we do not have integrality constraint over the resultant function, and there is no restriction on the lower-degree polynomial vanishing modulo because we do not take modulo. The outcome of applying Rouché’s theorem is that the zeros are brought to the origin. The outcome of LLL algorithm is that the zeros modulo become zeros over the integers. Can there be some connection between the ideas of Coppersmith algorithm and the proof of the fundamental theorem of algebra?
Removed. Initially I thought the matrix looked like the companion matrix of I soon realised it did not.