.. _sphx_glr_api_gallery_number_theory_factorization:

Integer factorization
---------------------

Pollard's rho method.


.. 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 rho method finds a prime factor p of n in roughly \sqrt p steps, by waiting for a birthday-paradox collision in the sequence x \mapsto x^2 + 1 \bmod p. This script factors the Fermat number F_6 = 2^{64}+1 and plots the step count against the smallest prime factor for a batch of semiprimes.">

.. only:: html

  .. image:: /api/gallery/number_theory/factorization/images/thumb/sphx_glr_plot_01_pollard_rho_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/factorization/plot_01_pollard_rho`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Pollard's rho factorization</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/number_theory/factorization/plot_01_pollard_rho