ModularSquareRoot(...)

[Jeffrey Walton]

Hi Wei,

The following code has not been bench marked. I wanted to offer in
case others wanted to use.

Jeff

//
// Taken from Handbook of Applied Cryptography
//   Menezes, van Oorschot, and Vanstone
//   ISBN 0-8493-8523-7
//   pp. 100-02
CryptoPP::Integer ModularSquareRoot(const CryptoPP::Integer &a, const
CryptoPP::Integer &p) {

   //
   // Does the root exist?
   //
   if( -1 == CryptoPP::Jacobi( a, p ) ) { return CryptoPP::Integer::Zero(); }

   //
   // Algorithm 3.36, p. 100
   //
   // O((lg p)^3) bit operations
   //
   if( 3 == p%4 ) {

                return CryptoPP::ModularExponentiation( a, (p+1)/4, p );
   }

   //
   // Algorithm 3.37, p. 101
   //
   // O((lg p)^3) bit operations
   //
   if( 5 == p%8 ) {

       CryptoPP::Integer d = CryptoPP::ModularExponentiation( a, (p-1)/4, p );

       if( CryptoPP::Integer::One() == d ) {

           return CryptoPP::ModularExponentiation( a, (p+3)/8, p );
       }

       if( p-1 == d ) {

           // 2*a * CryptoPP::ModularExponentiation( 4*a, (p-5)/8, p ) ) % p
           return ( (a << 1) * CryptoPP::ModularExponentiation( (a <<
2), (p-5)/8, p ) ) % p;
       }
   }

   //
   // Algorithm 3.39, p. 101
   //
   // O((lg p)^3) bit operations
   //
   // Use when p-1 = (2^s)*t, with s large
   //
   // CryptoPP::Integer b = 2;
   // do {
   //     b++;
   // } while( -1 != CryptoPP::Jacobi( ( b.Squared() - 4*a ), p ) );
   // f = x^2 - bx + a in Z_p[x]
   // // r will be an Integer
   // r = CryptoPP::ModularExponentiation( x, (p+1)/2, f );
   // return r;

   //
   // Algorithm 3.34, p. 100
   //
   // O((lg p)^4) bit operations
   //
   return CryptoPP::ModularSquareRoot( a, p );
}