tonellishanks module

Pure-Python implementation of the Tonelli-Shanks algorithm for calculating a square root modulo a prime.

tonellishanks(integer: int, prime: int) → Optional[int]

Return the least nonnegative residue modulo prime that is the square root of integer modulo prime (where prime is a prime number).

>>> tonellishanks(4, 7)
2
>>> tonellishanks(2, 7)
3
>>> all(tonellishanks(n ** 2, 17) in (n, 17 - n) for n in range(1, 17))
True

Integer inputs are always interpreted as representing the corresponding least nonnegative residue modulo prime.

>>> tonellishanks(9, 7)
3
>>> tonellishanks(-5, 7)
3
>>> tonellishanks(-12, 7)
3
>>> tonellishanks(0, 7)
0

The result None is returned for inputs that are not a square modulo prime.

>>> tonellishanks(3, 7) is None
True

Any attempt to invoke this function with an argument that does not have the expected types (or does not fall within the supported range) raises an exception.

>>> tonellishanks('abc', 19)
Traceback (most recent call last):
  ...
TypeError: 'str' object cannot be interpreted as an integer
>>> tonellishanks(16, {})
Traceback (most recent call last):
  ...
TypeError: 'dict' object cannot be interpreted as an integer
>>> tonellishanks(25, -1)
Traceback (most recent call last):
  ...
ValueError: prime modulus must be a positive integer

This implementation has been adapted from the version presented at Tonelli-Shanks algorithm on Rosetta Code.