Floating-Point LLL: Theoretical and Practical Aspects
Floating-Point LLL: Theoretical and Practical Aspects
复制标题
浮点 LLL：理论和实践方面
DOI：
10.1007/978-3-642-02295-1_5
复制
发表时间：
2010
期刊：
影响因子：
--
通讯作者：
D. Stehlé
中科院分区：
文献类型：
--
作者：
D. Stehlé
通过用浮点近似替换用于 Gram-Schmidt 正交化的基础有理算术，可以大大加快教科书 LLL 算法的速度。我们回顾了这一修改在理论上和实践中已经和目前是如何实施的。即使从理论角度来看，使用浮点近似对于 LLL 来说似乎也是很自然的：它是达到与输入向量条目的位长度成二次方的位复杂度的关键，而无需快速整数乘法。后者的位复杂度加强了 LLL 和 Euclid 的 gcd 算法之间的联系。在实际方面，LLL 实现者可能会削弱可证明的变体，以进一步提高其效率：我们强调这些技术。我们还考虑了浮点 LLL 算法的实际行为，特别是它们的输出分布、运行时间和数值行为。经过 25 年的实施，LLL 的实践方面引发的许多问题仍然悬而未决。
The text-book LLL algorithm can be sped up considerably by replacing the underlying rational arithmetic used for the Gram–Schmidt orthogonalisation by floating-point approximations. We review how this modification has been and is currently implemented, both in theory and in practice. Using floating-point approximations seems to be natural for LLL even from the theoretical point of view: it is the key to reach a bit-complexity which is quadratic with respect to the bit-length of the input vectors entries, without fast integer multiplication. The latter bit-complexity strengthens the connection between LLL and Euclid’s gcd algorithm. On the practical side, the LLL implementer may weaken the provable variants in order to further improve their efficiency: we emphasise on these techniques. We also consider the practical behaviour of the floating-point LLL algorithms, in particular their output distribution, their running-time and their numerical behaviour. After 25 years of implementation, many questions motivated by the practical side of LLL remain open.
DOI：
10.1007/978-3-642-02295-1_10
发表时间：
2010
期刊：
--
影响因子：
--
作者：
Alexander May
通讯作者：
Alexander May
影响因子：
2.1
作者：
通讯作者：
--