A totally generic implementation of Coppersmith's method that finds small roots for any modular multivariate polynomial. For example, this supports:
Of course, added complexity leads to lower quality bounds. Optimizations are a work in progress.
See examples.sage for confirmed use cases. For general use, the arguments of small_roots
are:
f
- Multivariate polynomial with small roots. Its base ring should be some sort of integers modulo N
.bounds
- Tuple of bounds for each variable in f.variables()
. This is used to optimize the lattice and does not strictly determine the size of roots returned.m
- Determines how many higher powers of f
and N
to use. Defaults to 1.d
- Determines how many variable shifts to use. Defaults to f.degree()
.