//  ============================================================
//
//  chineseRemainder.h
//
//  Copyright 2002, Dennis Meilicke and Rene Peralta
//
//  ============================================================
//
//  Description:
//
//  NTTL Implementation of:
//      SolveChineseRemainder
//
//  ============================================================
#ifndef __nttl_chineseRemainder__
#define __nttl_chineseRemainder__


#include <vector>
#include <nttl/gcd.h>

template< class T >
T SolveChineseRemainder( const vector< T, allocator<T> >& X, 
                         const vector< T, allocator<T> >& M )
{
	T x, m;
	T u, v;

	m = M[ 0 ];
	x = X[ 0 ];

	for( size_t i=1 ; i<X.size( ) ; i++ )
	{
		ExtendedGCD( m, M[ i ], &u, &v );

		x = u * m * X[ i ] + v * M[ i ] * x;
		m = m * M[ i ];
		x %= m;
	}

	if( x < 0 ) x += m;

	return x;
}


#endif