[las] [at work] Use batch inversion for translating fb elements in the q-lattice
Imported issue: Initially reported by @gaudry in https://gforge.inria.fr/tracker/?group_id=2065&aid=16545
In the lattice siever, for each new special-q we spend a non-negligible
time in fb_root_in_qlattice().
This function is called for each factor base ideal (p,r), and computes
the value of an homography modulo p. The modular inverse should be a
bottleneck, here. The batch inversion trick allows to trade n inversions
modulo the same prime p for 1 inversions and about 3n multiplications.
Three possibilities (from the easiest to the hardest to implement):
-
do the batch inversion only on the algebraic sides, when there are
several roots modulo p.
-
include the rational ideal p as well. (which implies reading the two fb
in parallel with the current code)
-
share this batch inversion over several special-q (which implies saving
additional data in memory)