The ModularSquareRoot function computes a non-negative integer $y$ such that $y^2=x\mathbf{mod}n$ if possible. If not possible, an error message is displayed.

When x has more than one square root, any one of them may be returned.

$\mathrm{with}\left(\mathrm{NumberTheory}\right)\:$

$\mathrm{residues}≔\left\{\mathrm{seq}\left(i^2\mathbf{mod}37\,i\=0..36\right)\right\}$

$\mathrm{residues}≔\left\{0\,1\,3\,4\,7\,9\,10\,11\,12\,16\,21\,25\,26\,27\,28\,30\,33\,34\,36\right\}$

$\mathrm{evalb}\left(30\∈\mathrm{residues}\right)$

$\mathrm{true}$

$\mathrm{ModularSquareRoot}\left(30\,37\right)$

$17$

${17}^2\mathbf{mod}37$

$30$

$\mathrm{evalb}\left(24\∈\mathrm{residues}\right)$

$\mathrm{false}$

$\mathrm{ModularSquareRoot}\left(24\,37\right)$

Error, (in NumberTheory:-ModularSquareRoot) 24 is a quadratic non-residue modulo 37

The NumberTheory[ModularSquareRoot] command was introduced in Maple 2016.

For more information on Maple 2016 changes, see Updates in Maple 2016.