.. _sphx_glr_api_gallery_number_theory_modular_arithmetic:

Modular arithmetic
--------------------

The extended Euclidean algorithm, modular inverses, and fast modular
exponentiation.


.. 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="Euclid&#x27;s Elements (Book VII, Propositions 1-2) finds the greatest common divisor by repeating \gcd(a, b) = \gcd(b, a \bmod b) until the remainder vanishes. This script traces the division steps for one pair, recovers Bézout&#x27;s coefficients ax + by = \gcd(a, b) with extended_gcd, and maps how many steps the algorithm needs: the slowest inputs are consecutive Fibonacci numbers (Lamé, 1844).">

.. only:: html

  .. image:: /api/gallery/number_theory/modular_arithmetic/images/thumb/sphx_glr_plot_01_euclidean_algorithm_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/modular_arithmetic/plot_01_euclidean_algorithm`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">Euclid's algorithm and Bézout's identity</div>
    </div>


.. raw:: html

    <div class="sphx-glr-thumbcontainer" tooltip="RSA&#x27;s key generation, encryption, and decryption are exactly mod_inverse (to find the private exponent) and fast_mod_pow (to encrypt/decrypt) -- demonstrated here with small (textbook-toy, NOT cryptographically secure) primes.">

.. only:: html

  .. image:: /api/gallery/number_theory/modular_arithmetic/images/thumb/sphx_glr_plot_02_toy_rsa_thumb.png
    :alt:

  :doc:`/api/gallery/number_theory/modular_arithmetic/plot_02_toy_rsa`

.. raw:: html

      <div class="sphx-glr-thumbnail-title">A toy RSA encryption/decryption round trip</div>
    </div>


.. thumbnail-parent-div-close

.. raw:: html

    </div>


.. toctree::
   :hidden:

   /api/gallery/number_theory/modular_arithmetic/plot_01_euclidean_algorithm
   /api/gallery/number_theory/modular_arithmetic/plot_02_toy_rsa