maths.tonelli_shanks

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

legendre_symbol(→ int)	Compute the Legendre symbol (residue / prime).
tonelli_shanks(→ int)	Return a modular square root of residue modulo odd prime prime.

Module Contents

maths.tonelli_shanks.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

maths.tonelli_shanks.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