Skip to main content
placeholder image

Adaptive precision floating point LLL

Journal Article


Download full-text (Open Access)

Abstract


  • The LLL algorithm is one of the most studied lattice basis

    reduction algorithms in the literature. Among all of its variants, the

    floating point version, also known as L2, is the most popular one, due to

    its efficiency and its practicality. In its classic setting, the floating point

    precision is a fixed value, determined by the dimension of the input

    basis at the initiation of the algorithm. We observe that a fixed precision

    overkills the problem, since one does not require a huge precision to

    handle the process at the beginning of the reduction. In this paper, we

    propose an adaptive way to handle the precision, where the precision

    is adaptive during the procedure. Although this optimization does not

    change the worst-case complexity, it reduces the average-case complexity

    by a constant factor. In practice, we observe an average 20% acceleration

    in our implementation.

Publication Date


  • 2013

Citation


  • Plantard, T., Susilo, W. & Zhang, Z. (2013). Adaptive precision floating point LLL. Lecture Notes in Computer Science, 7959 104-117. Brisbane, QLD Adaptive precision floating point LLL

Scopus Eid


  • 2-s2.0-84884481182

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=2330&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/1321

Has Global Citation Frequency


Number Of Pages


  • 13

Start Page


  • 104

End Page


  • 117

Volume


  • 7959

Place Of Publication


  • Germany

Abstract


  • The LLL algorithm is one of the most studied lattice basis

    reduction algorithms in the literature. Among all of its variants, the

    floating point version, also known as L2, is the most popular one, due to

    its efficiency and its practicality. In its classic setting, the floating point

    precision is a fixed value, determined by the dimension of the input

    basis at the initiation of the algorithm. We observe that a fixed precision

    overkills the problem, since one does not require a huge precision to

    handle the process at the beginning of the reduction. In this paper, we

    propose an adaptive way to handle the precision, where the precision

    is adaptive during the procedure. Although this optimization does not

    change the worst-case complexity, it reduces the average-case complexity

    by a constant factor. In practice, we observe an average 20% acceleration

    in our implementation.

Publication Date


  • 2013

Citation


  • Plantard, T., Susilo, W. & Zhang, Z. (2013). Adaptive precision floating point LLL. Lecture Notes in Computer Science, 7959 104-117. Brisbane, QLD Adaptive precision floating point LLL

Scopus Eid


  • 2-s2.0-84884481182

Ro Full-text Url


  • http://ro.uow.edu.au/cgi/viewcontent.cgi?article=2330&context=eispapers

Ro Metadata Url


  • http://ro.uow.edu.au/eispapers/1321

Has Global Citation Frequency


Number Of Pages


  • 13

Start Page


  • 104

End Page


  • 117

Volume


  • 7959

Place Of Publication


  • Germany