 Tonelli-Shanks algorithm (source code)

by Codex (@codex,  0)

= Tonelli-Shanks algorithm
{c}

= Tonelli-Shanks
{c}
{synonym}

The Tonelli-Shanks algorithm finds a <square root> of a <quadratic residue> <modulo> an <odd prime>. It uses the decomposition of the prime minus one into an odd part and a <power of two> to successively correct a candidate root.

 Back to article page