.. DO NOT EDIT.
.. THIS FILE WAS AUTOMATICALLY GENERATED BY SPHINX-GALLERY.
.. TO MAKE CHANGES, EDIT THE SOURCE PYTHON FILE:
.. "api/gallery/crypto/discrete_log/plot_02_pohlig_hellman.py"
.. LINE NUMBERS ARE GIVEN BELOW.

.. only:: html

    .. note::
        :class: sphx-glr-download-link-note

        :ref:`Go to the end <sphx_glr_download_api_gallery_crypto_discrete_log_plot_02_pohlig_hellman.py>`
        to download the full example code or to run this example in your browser via JupyterLite.

.. rst-class:: sphx-glr-example-title

.. _sphx_glr_api_gallery_crypto_discrete_log_plot_02_pohlig_hellman.py:


Pohlig-Hellman: why the group order must have a large prime factor (1978)
=========================================================================

Pohlig and Hellman noticed that a discrete log in a group of order
n = p1**e1 * p2**e2 * ... splits into small problems, one per prime power,
recombined with the Chinese Remainder Theorem. The cost depends on the
*largest prime factor* of n, not on n. A huge group with a smooth order is
weak.

What to look for
----------------

Two groups of about the same size: one whose order splits into small primes,
one of prime order. Pohlig-Hellman breaks the first almost instantly and
gains nothing on the second. This is why Diffie-Hellman and Schnorr use a
subgroup of large *prime* order, like blockchainkit's ``TEACHING_GROUP``.

The history behind this experiment: :doc:`/history/crypto_breakthroughs`.

.. GENERATED FROM PYTHON SOURCE LINES 23-25

A smooth order falls apart
--------------------------

.. GENERATED FROM PYTHON SOURCE LINES 25-39

.. code-block:: Python

    import matplotlib.pyplot as plt

    import blockchainkit as bk
    from blockchainkit.crypto.systems.discrete_log import factor_order

    smooth_p = 8101  # 8100 = 2**2 * 3**4 * 5**2
    print("order factors:", factor_order(smooth_p - 1))
    secret = 4321
    target = pow(6, secret, smooth_p)  # 6 generates the whole group modulo 8101.
    ph = bk.crypto.pohlig_hellman(6, target, smooth_p, smooth_p - 1)
    bsgs = bk.crypto.baby_step_giant_step(6, target, smooth_p, smooth_p - 1)
    assert ph.exponent == bsgs.exponent == secret
    print("Pohlig-Hellman:", ph.group_operations, "ops; baby-step giant-step:", bsgs.group_operations)





.. rst-class:: sphx-glr-script-out

 .. code-block:: none

    order factors: {2: 2, 3: 4, 5: 2}
    Pohlig-Hellman: 27 ops; baby-step giant-step: 139




.. GENERATED FROM PYTHON SOURCE LINES 40-42

A prime order does not
----------------------

.. GENERATED FROM PYTHON SOURCE LINES 42-49

.. code-block:: Python

    prime_order = bk.crypto.DHGroup(8147, 4073, 4)  # 4073 is prime.
    target = prime_order.public(1234)
    ph_prime = bk.crypto.pohlig_hellman(4, target, prime_order.p, prime_order.q)
    bsgs_prime = bk.crypto.baby_step_giant_step(4, target, prime_order.p, prime_order.q)
    assert ph_prime.exponent == bsgs_prime.exponent == 1234
    assert ph_prime.group_operations >= bsgs_prime.group_operations








.. GENERATED FROM PYTHON SOURCE LINES 50-70

.. code-block:: Python

    fig, ax = plt.subplots(figsize=(7, 4))
    labels = ["smooth order 8100", "prime order 4073"]
    xs = range(2)
    ax.bar(
        [x - 0.18 for x in xs],
        [bsgs.group_operations, bsgs_prime.group_operations],
        0.36,
        label="baby-step giant-step",
    )
    ax.bar(
        [x + 0.18 for x in xs],
        [ph.group_operations, ph_prime.group_operations],
        0.36,
        label="Pohlig-Hellman",
    )
    ax.set_xticks(list(xs), labels)
    ax.set(ylabel="group operations", title="Only the largest prime factor matters")
    ax.legend()
    fig.tight_layout()




.. image-sg:: /api/gallery/crypto/discrete_log/images/sphx_glr_plot_02_pohlig_hellman_001.png
   :alt: Only the largest prime factor matters
   :srcset: /api/gallery/crypto/discrete_log/images/sphx_glr_plot_02_pohlig_hellman_001.png
   :class: sphx-glr-single-img





.. GENERATED FROM PYTHON SOURCE LINES 71-77

Exercise
--------
The teaching group uses p = 2q + 1 with q prime (a "safe prime"). What is
the largest prime factor of p - 1, and what would Pohlig-Hellman cost in the
order-q subgroup? Why would working in the full group modulo p leak one bit
of every exponent?


.. rst-class:: sphx-glr-timing

   **Total running time of the script:** (0 minutes 0.143 seconds)


.. _sphx_glr_download_api_gallery_crypto_discrete_log_plot_02_pohlig_hellman.py:

.. only:: html

  .. container:: sphx-glr-footer sphx-glr-footer-example

    .. container:: lite-badge

      .. image:: images/jupyterlite_badge_logo.svg
        :target: ../../../../lite/lab/index.html?path=api/gallery/crypto/discrete_log/plot_02_pohlig_hellman.ipynb
        :alt: Launch JupyterLite
        :width: 150 px

    .. container:: sphx-glr-download sphx-glr-download-jupyter

      :download:`Download Jupyter notebook: plot_02_pohlig_hellman.ipynb <plot_02_pohlig_hellman.ipynb>`

    .. container:: sphx-glr-download sphx-glr-download-python

      :download:`Download Python source code: plot_02_pohlig_hellman.py <plot_02_pohlig_hellman.py>`

    .. container:: sphx-glr-download sphx-glr-download-zip

      :download:`Download zipped: plot_02_pohlig_hellman.zip <plot_02_pohlig_hellman.zip>`


.. only:: html

 .. rst-class:: sphx-glr-signature

    `Gallery generated by Sphinx-Gallery <https://sphinx-gallery.github.io>`_