//  ============================================================
//
//  modSqrtCmn.h
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  Functions common to all of the modular square root
//  functions.  
//
//  ============================================================
//
//  Functions:
//      ModSqrtCmn - If a square root can be computed directly,
//                   then this function will do so.  If it
//                   cannot, then this function will return
//                   zero, and one of the more complicated
//                   functions will have to be called.
//
//      ModSqrtQNR - Used by many of the other functions.  Find
//                   a quadratic non-residue.
//
//  ============================================================
#ifndef __nttlHeader_modSqrtCmn__
#define __nttlHeader_modSqrtCmn__


#include <nttl/jacobi.h>


enum enumModSqrtCmn
{
  enumModSqrtQNR,
  enumModSqrtFound,
  enumModSqrtNotFound
};


template< class T >
enumModSqrtCmn
ModSqrtCmn( const T &X, const T& p, T *S )
//
//  Return false if X is a QNR mod p.
//  If X is a quadratic residue mod p, then set S equal to the 
//  square root of X mod p, and return true.
//
{
  nttlTraits< T > t;

  //
  //  If the Jacobi is -1, then there is no square root.
  //  This should probably throw an exception...
  //
  if( Jacobi( X, p ) == -1 )
    return enumModSqrtQNR;

  //  Jacobi( X, p ) == 0, then do we have to test X%p==0, below?
    
  T x = X % p;
  if( x == 0 )
  {
    // is this really true?  Or is this another exception?
    *S = 0;
    return enumModSqrtFound;
  }

  if( x == 1 )
  { 
    // Note that this takes are of p == 2
    *S = 1;
    return enumModSqrtFound;
  }
    
  if( ( p % 4 ) == 3 )
  {
    *S = t.Power( x, (p+1)/4, p );
    return enumModSqrtFound;
  }

  if( ( p % 8 ) == 5 )
  {
    T aux = t.Power( x, (p-1)/4, p ); // this is a square root of 1 mod p
        
    if( aux == 1 )
    {
      *S = t.Power( x, (p+3)/8, p );
      return enumModSqrtFound;
    }

    //*S = ( ((p + 1) / 2) * t.Power( (4*x), (p+3)/8, p ) ) % p;
    //per Cohen, an alternative to this is 
    *S = ( 2 * x * t.Power( (4*x), (p-5)/8, p ) ) % p;
    //  what if p=5?
    return enumModSqrtFound;
  }
    
  return enumModSqrtNotFound;
}


template< class T >
inline
T
ModSqrtQNR( const T& p )
{
  T qnr;
  short j;
  for( qnr = 2 ; ; ++qnr )
  {
    j = Jacobi( qnr, p );
    if( j == -1 )
      break;
  }
  return qnr;
} 


#endif  //  __nttlHeader_modSqrtCmn__