.. _sphx_glr_api_gallery_number_theory_lattice:

Lattice reduction
-------------------

The LLL algorithm and integer relations.


.. raw:: html

  <div id='sg-tag-list' class='sphx-glr-tag-list'></div>


.. raw:: html

    <div class="sphx-glr-thumbnails">

.. thumbnail-parent-div-open

.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="A lattice has infinitely many bases, and a basis of long, nearly parallel vectors hides its structure. Lenstra, Lenstra and Lovász (1982) gave a polynomial-time algorithm that turns any basis into a reduced one, of short and nearly orthogonal vectors. They needed it to factor polynomials with rational coefficients; it has since become a universal tool, from breaking knapsack cryptosystems to discovering integer relations among real numbers.">

.. only:: html

  .. image:: /api/gallery/number_theory/lattice/images/thumb/sphx_glr_plot_01_lll_lattice_reduction_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/lattice/plot_01_lll_lattice_reduction`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Lenstra-Lenstra-Lovász lattice reduction algorithm</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/number_theory/lattice/plot_01_lll_lattice_reduction