.. _sphx_glr_api_gallery_number_theory_primality:

Primality
-----------

Trial division, Miller-Rabin, and the sieve of Eratosthenes.


.. 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="Rabin&#x27;s 1980 randomization of Miller&#x27;s test declares n &quot;probably prime&quot; after k random witnesses; for a composite n each witness is fooled with probability at most 1/4, so the error shrinks like 4^{-k}. This script shows the test exposing a Carmichael number that fools Fermat&#x27;s test, measures the error rate against the number of rounds for two hard composites, and certifies a 39-digit prime far beyond trial division&#x27;s reach.">

.. only:: html

  .. image:: /api/gallery/number_theory/primality/images/thumb/sphx_glr_plot_01_miller_rabin_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/primality/plot_01_miller_rabin`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The Miller-Rabin probabilistic primality test</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="The Lucas-Lehmer test decides whether M_p = 2^p - 1 is prime with only p - 2 modular squarings. This script rediscovers every Mersenne prime with exponent below 1300 -- including M_{521} through M_{1279}, found by Raphael Robinson on the SWAC computer in 1952 -- and plots the exponents, which grow roughly geometrically.">

.. only:: html

  .. image:: /api/gallery/number_theory/primality/images/thumb/sphx_glr_plot_02_lucas_lehmer_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/primality/plot_02_lucas_lehmer`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Mersenne primes and the Lucas-Lehmer test</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="Sieves all primes up to 100,000 and compares the prime-counting function \pi(n) against the prime number theorem&#x27;s approximation n/\ln n.">

.. only:: html

  .. image:: /api/gallery/number_theory/primality/images/thumb/sphx_glr_plot_03_prime_counting_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/primality/plot_03_prime_counting`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">The prime-counting function and the prime number theorem</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/number_theory/primality/plot_01_miller_rabin
   /api/gallery/number_theory/primality/plot_02_lucas_lehmer
   /api/gallery/number_theory/primality/plot_03_prime_counting