.. _sphx_glr_api_gallery_number_theory_elliptic_curves:

Elliptic curves
-----------------

The group law on curves over GF(p), and Lenstra's elliptic-curve
factorization.


.. 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="Pollard&#x27;s p - 1 method finds a prime p \mid n when the group (\mathbb Z/p)^\times, of order p - 1, has only small prime factors; if it does not, the method is stuck. Lenstra (1987) replaced that one group by the groups of points of random elliptic curves y^2 = x^3 + ax + b over \mathrm{GF}(p). By Hasse&#x27;s theorem their orders scatter over [p + 1 - 2\sqrt p,\ p + 1 + 2\sqrt p], so a bad curve is cured by trying another one, until some curve&#x27;s order happens to be smooth.">

.. only:: html

  .. image:: /api/gallery/number_theory/elliptic_curves/images/thumb/sphx_glr_plot_01_lenstra_elliptic_curve_factorization_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/elliptic_curves/plot_01_lenstra_elliptic_curve_factorization`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Lenstra's elliptic-curve factorization</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/number_theory/elliptic_curves/plot_01_lenstra_elliptic_curve_factorization