modularSquareRoot -- Compute the modular square root.

Synopsis

Usage:

modularSquareRoot(a,n)
Inputs:
- a, an integer,
- n, an integer, positive, squarefree.
Outputs:
- an integer, in 0,...,n-1 representing the square root of a in $\mathbb{Z}/n\mathbb{Z}$, or -1 if it does not exist.

Description

Computes the square root of a in $\mathbb{Z}/n\mathbb{Z}$

i1 : modularSquareRoot(626,1180943)

o1 = 832737

i2 : modularSquareRoot(3,13)

o2 = 4

i3 : modularSquareRoot(7,14)

o3 = 7

i4 : modularSquareRoot(3,14)

o4 = FAIL

o4 : Symbol

Caveat

This should be extended slightly to non squarefree n. We use this function as we have to handle very large numbers. This function is no longer used, as we call Maple to compute the modular square root.

Ways to use modularSquareRoot :

modularSquareRoot(ZZ,ZZ)

For the programmer

The object modularSquareRoot is a method function.