NTTL Function - Sqrt

Description

Compute the modular square root of a number.

Header

<nttl/modSqrt.h>

Signature

template< class T >
T
Sqrt( const T &X, const T& p )

Parameters

Name	Type	Description
X	T	The number for which the square root is computed.
p	T	The modulus.

Returns

( T )  The modular square root of X, if it exists.  Zero if the modular square root does not exist.

Example

#include <nttl/modSqrt.h> ... long s = Sqrt( 1239273, 7 );

Algorithms

The default algorithm is the Tonelli/Shanks algorithm.  The implementation is based on [Menezes,van Oorschot,Vanstone] algorithm 3.34 (pg 100).  This is the algorithm used if <nttl/modSqrt.h> is included.

 

As with other nttl functions, alternate algorithms are available:

 

Header	Algorithm
<nttl/modSqrt.h>	Tonneli/Shanks.  This simply includes <nttl/modSqrtTonelli.h>.
<nttl/modSqrtTonelli.h>	Tonelli/Shanks.
<nttl/modSqrtLehmer.h>	(not yet working)  Lehmer's algorithm.  See [Knuth2].
<nttl/modSqrtOld.h>	(not yet working)  The algorithm from ln2.

 

For information on how the alternate algorithms are implelemented, and details on how to use the alternate algorithms, see Algorithm Selection.

To Do

We should consider changing the name of this function to ModSqrt.

 

There are other references for Tonelli/Shanks.  They should be cited.   References for Lehmer's algorithm, and the Old algorithm should also be included.

References

[Menezes,van Oorschot,Vanstone], algorithm 3.34, pg. 100.