//  ============================================================
//
//  inverseEuclid.h
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  NTTL Implementation of:
//      Inverse
//
//  While the NTTL function ExtendedGCD can also be used to 
//  calculate the modular inverse, this function can be
//  optimized to do fewer operations than the full ExtendedGCD.
//
//  ============================================================
#ifndef __nttlHeader_inverseEuclid__
#define __nttlHeader_inverseEuclid__


#include <math.h>


template< class T >
T
InverseEuclid( const T& x, const T& modulus )
//
//  Description:  Returns the inverse of *this, modulo the parameter
//                'modulus'.  Returns 0 if the inverse does not exist.
//  Algorithm:
//  To do:        This method should do something besides returning
//                zero on error (non-existance).  This is one of the
//                methods in dire need of rational error handling.
//
{
  T g0,g1,g2;
  T u0,u1,u2;
  T v0,v1,v2;
  T y;
  
  g0 = ( modulus < 0 ) ? -modulus : modulus;
  g1 = x % g0; 
  u0 = 1;	u1 = 0;
  v0 = 0;	v1 = 1;
  
  while (g1 != 0)
    {
      y = g0/g1;
      g2 = g0 - y*g1;
      g0 = g1;
      g1 = g2;
      
      u2 = u0 - y*u1;
      u0 = u1;
      u1 = u2;
      
      v2 = v0 - y*v1;
      v0 = v1;
      v1 = v2;
    }
  
  g0 = ( modulus < 0 ) ? -modulus : modulus;
  //  reuse v1
  v1 = (v0 * x) % g0;
  if( v1 < 0 )
  {
      v1 = v1 + g0;  // we want a positive modulus
  }
  //
  //  v1 is the GCD.  If it is not 1, then the inverse doesn't exist.
  //
  if ( v1 != 1 )
  {
    v0 = 0;
    return v0;
  }

  //
  //  This should be done before the error check.  It would reduce the
  //  complexity of the error checking calculation...
  //
  if(v0 < 0)	
    v0 = v0 + modulus;
  
  return v0;
}


//  ============================================================


#ifndef __nttlAlgorithm_Inverse__
#define __nttlAlgorithm_Inverse__

template< class T >
inline
T
Inverse( const T& x, const T& modulus )
{
  return InverseEuclid( x, modulus );
}


#endif  //  __nttlAlgorithm_Inverse__


#endif  //  __nttlHeader_inverseEuclid__