maths.tonelli_shanks
====================

.. py:module:: maths.tonelli_shanks

.. autoapi-nested-parse::

   Tonelli-Shanks algorithm for modular square roots.

   Given an odd prime modulus ``prime`` and an integer ``residue``, find an
   integer ``root`` such that ``root ** 2 ≡ residue (mod prime)``, or report that
   no square root exists.

   The algorithm is efficient when ``prime ≡ 3 (mod 4)`` (a single
   exponentiation) and uses the full Tonelli-Shanks procedure for
   ``prime ≡ 1 (mod 4)``.

   https://en.wikipedia.org/wiki/Tonelli%E2%80%93Shanks_algorithm



Functions
---------

.. autoapisummary::

   maths.tonelli_shanks.legendre_symbol
   maths.tonelli_shanks.tonelli_shanks


Module Contents
---------------

.. py:function:: legendre_symbol(residue: int, prime: int) -> int

   Compute the Legendre symbol (residue / prime).

   Returns 1 if residue is a quadratic residue modulo prime (and residue
   is not divisible by prime), -1 if it is a non-residue, and 0 if
   residue ≡ 0 (mod prime).

   >>> legendre_symbol(2, 7)
   1
   >>> legendre_symbol(3, 7)
   -1
   >>> legendre_symbol(14, 7)
   0
   >>> legendre_symbol(5, 11)
   1


.. py:function:: tonelli_shanks(residue: int, prime: int) -> int

   Return a modular square root of ``residue`` modulo odd prime ``prime``.

   If both roots exist, the smaller non-negative representative is returned.
   Raises ValueError when ``residue`` is not a quadratic residue, or when
   ``prime`` is not a valid odd prime modulus for this routine.

   >>> tonelli_shanks(5, 41)
   13
   >>> pow(13, 2, 41)
   5
   >>> tonelli_shanks(2, 7)
   3
   >>> pow(3, 2, 7)
   2
   >>> tonelli_shanks(10, 13)
   6
   >>> tonelli_shanks(0, 11)
   0
   >>> tonelli_shanks(8, 17)
   5
   >>> pow(5, 2, 17)
   8
   >>> tonelli_shanks(3, 7)
   Traceback (most recent call last):
       ...
   ValueError: 3 is not a quadratic residue modulo 7
   >>> tonelli_shanks(5, 4)
   Traceback (most recent call last):
       ...
   ValueError: prime must be an odd prime
   >>> tonelli_shanks(5, 1)
   Traceback (most recent call last):
       ...
   ValueError: prime must be an odd prime