Notes for UMich EECS 598 (2015): Lecture 3

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’.

Lenstra–Lenstra–Lovász algorithm

This section is an interactive implementation of Lenstra–Lenstra–Lovász algorithm and needs JavaScript to run. The source code is available under the MIT license.

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 $B_{0}$ (an integer matrix with entries of magnitude less than $2^{20})$ and tap the button. The implementation will compute an LLL-reduced basis $B$ and the unimodular change-of-basis matrix $W$ s.t. $B_{0} W = B .$ (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 $B :$
Change-of-basis matrix $W :$

Coppersmith algorithm

I find it rather unnatural to say $‘ h (B x)$ is short’. I paraphrase the idea here.

Suppose we want to find all small zeros (with absolute value at most $B)$ of a monic polynomial $f (x) = f_{0} + f_{1} x + \dots + f_{d - 1} x^{d - 1} + x^{d}$ modulo $N .$ We do this by finding a polynomial $h (x)$ such that

the zeros of $f (x)$ modulo $N$ are also ones of $h (x)$ modulo $N;$
the small zeros of $h (x)$ modulo $N$ are also zeros of $h (x)$ as an integer-coefficient polynomial.

In particular, we consider $h (x) = a_{0} N + a_{1} N x + \dots + a_{d - 1} N x^{d - 1} + a_{d} f (x) = h_{0} + h_{1} x + \dots + h_{d - 1} x^{d - 1} + h_{d} x^{d},$ where $a_{0}, \dots, a_{d}$ are integers and $h_{0}, \dots, h_{d}$ are the coefficients of $h (x) .$ Clearly, any zero of $f (x)$ modulo $N$ is also a zero of $h (x)$ modulo $N .$ To ensure the small zeros of $h (x)$ modulo $N$ are also zeros of $h (x)$ as an integer-coefficient polynomial, so we require $h (x) \in (- N, N) \forall x \in [- B, B] .$ A sufficient condition of the above inequality is that $∣ h_{i} B^{i} ∣ < \frac{N}{d + 1}$ for $i = 0, \dots, d .$ If we define $v = = def = (h_{0}, h_{1} B, \dots, h_{d - 1} B^{d - 1}, h_{d} B^{d}) (a_{0} N + a_{d} f_{0}, (a_{1} N + a_{d} f_{1}) B, \dots, (a_{d - 1} N + a_{d} f_{d - 1}) B^{d - 1}, a_{d} B^{d}),$ a sufficient condition of the above inequality is that $∣ v ∣ < \frac{N}{d + 1} .$ Moreover, the possible $v ’s$ are exactly non-zero points in the lattice generated by $B = ⎝ ⎜ ⎜ ⎜ ⎜ ⎜ ⎜ ⎛ N N B ⋱ N B^{d - 1} f_{0} f_{1} B ⋮ f_{d - 1} B^{d - 1} B^{d} ⎠ ⎟ ⎟ ⎟ ⎟ ⎟ ⎟ ⎞ .$ Therefore, we can use LLL algorithm to compute a short $v,$ recover $h (x)$ from it and solve it over the reals.

Question. The form of $h (x)$ as a multiple of $f (x)$ plus a lower-degree polynomial (that vanishes modulo $N)$ 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 $N$ 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 $N$ 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 $B$ looked like the companion matrix of $f (x) .$ I soon realised it did not.