polynomi.h

lots Elliptic curve cryptography codes. Use Visual c++ to compile

		ThisType&  operator%=(const ThisType& t) {return *this = *this%t;}

		//!
		ThisType&  operator<<=(unsigned int n) {ShiftLeft(n, ms_fixedRing); return *this;}
		//!
		ThisType&  operator>>=(unsigned int n) {ShiftRight(n, ms_fixedRing); return *this;}

		//! set the coefficient for x^i to value
		void SetCoefficient(unsigned int i, const CoefficientType &value) {B::SetCoefficient(i, value, ms_fixedRing);}

		//!
		void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter) {B::Randomize(rng, parameter, ms_fixedRing);}

		//!
		void Negate() {B::Negate(ms_fixedRing);}

		void swap(ThisType &t) {B::swap(t);}
	//@}

	//! \name UNARY OPERATORS
	//@{
		//!
		bool operator!() const {return CoefficientCount()==0;}
		//!
		ThisType operator+() const {return *this;}
		//!
		ThisType operator-() const {return ThisType(Inverse(ms_fixedRing));}
	//@}

	//! \name BINARY OPERATORS
	//@{
		//!
		friend ThisType operator>>(ThisType a, unsigned int n)	{return ThisType(a>>=n);}
		//!
		friend ThisType operator<<(ThisType a, unsigned int n)	{return ThisType(a<<=n);}
	//@}

	//! \name OTHER ARITHMETIC FUNCTIONS
	//@{
		//!
		ThisType MultiplicativeInverse() const {return ThisType(B::MultiplicativeInverse(ms_fixedRing));}
		//!
		bool IsUnit() const {return B::IsUnit(ms_fixedRing);}

		//!
		ThisType Doubled() const {return ThisType(B::Doubled(ms_fixedRing));}
		//!
		ThisType Squared() const {return ThisType(B::Squared(ms_fixedRing));}

		CoefficientType EvaluateAt(const CoefficientType &x) const {return B::EvaluateAt(x, ms_fixedRing);}

		//! calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
		static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d)
			{B::Divide(r, q, a, d, ms_fixedRing);}
	//@}

	//! \name INPUT/OUTPUT
	//@{
		//!
		friend std::istream& operator>>(std::istream& in, ThisType &a)
			{return a.Input(in, ms_fixedRing);}
		//!
		friend std::ostream& operator<<(std::ostream& out, const ThisType &a)
			{return a.Output(out, ms_fixedRing);}
	//@}

private:
	struct NewOnePolynomial
	{
		ThisType * operator()() const
		{
			return new ThisType(ms_fixedRing.MultiplicativeIdentity());
		}
	};

	static const Ring ms_fixedRing;
};

//! Ring of polynomials over another ring
template <class T> class RingOfPolynomialsOver : public AbstractEuclideanDomain<PolynomialOver<T> >
{
public:
	typedef T CoefficientRing;
	typedef PolynomialOver<T> Element;
	typedef typename Element::CoefficientType CoefficientType;
	typedef typename Element::RandomizationParameter RandomizationParameter;

	RingOfPolynomialsOver(const CoefficientRing &ring) : m_ring(ring) {}

	Element RandomElement(RandomNumberGenerator &rng, const RandomizationParameter &parameter)
		{return Element(rng, parameter, m_ring);}

	bool Equal(const Element &a, const Element &b) const
		{return a.Equals(b, m_ring);}

	const Element& Identity() const
		{return this->result = m_ring.Identity();}

	const Element& Add(const Element &a, const Element &b) const
		{return this->result = a.Plus(b, m_ring);}

	Element& Accumulate(Element &a, const Element &b) const
		{a.Accumulate(b, m_ring); return a;}

	const Element& Inverse(const Element &a) const
		{return this->result = a.Inverse(m_ring);}

	const Element& Subtract(const Element &a, const Element &b) const
		{return this->result = a.Minus(b, m_ring);}

	Element& Reduce(Element &a, const Element &b) const
		{return a.Reduce(b, m_ring);}

	const Element& Double(const Element &a) const
		{return this->result = a.Doubled(m_ring);}

	const Element& MultiplicativeIdentity() const
		{return this->result = m_ring.MultiplicativeIdentity();}

	const Element& Multiply(const Element &a, const Element &b) const
		{return this->result = a.Times(b, m_ring);}

	const Element& Square(const Element &a) const
		{return this->result = a.Squared(m_ring);}

	bool IsUnit(const Element &a) const
		{return a.IsUnit(m_ring);}

	const Element& MultiplicativeInverse(const Element &a) const
		{return this->result = a.MultiplicativeInverse(m_ring);}

	const Element& Divide(const Element &a, const Element &b) const
		{return this->result = a.DividedBy(b, m_ring);}

	const Element& Mod(const Element &a, const Element &b) const
		{return this->result = a.Modulo(b, m_ring);}

	void DivisionAlgorithm(Element &r, Element &q, const Element &a, const Element &d) const
		{Element::Divide(r, q, a, d, m_ring);}

	class InterpolationFailed : public Exception
	{
	public:
		InterpolationFailed() : Exception(OTHER_ERROR, "RingOfPolynomialsOver<T>: interpolation failed") {}
	};

	Element Interpolate(const CoefficientType x[], const CoefficientType y[], unsigned int n) const;

	// a faster version of Interpolate(x, y, n).EvaluateAt(position)
	CoefficientType InterpolateAt(const CoefficientType &position, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;
/*
	void PrepareBulkInterpolation(CoefficientType *w, const CoefficientType x[], unsigned int n) const;
	void PrepareBulkInterpolationAt(CoefficientType *v, const CoefficientType &position, const CoefficientType x[], const CoefficientType w[], unsigned int n) const;
	CoefficientType BulkInterpolateAt(const CoefficientType y[], const CoefficientType v[], unsigned int n) const;
*/
protected:
	void CalculateAlpha(std::vector<CoefficientType> &alpha, const CoefficientType x[], const CoefficientType y[], unsigned int n) const;

	CoefficientRing m_ring;
};

template <class Ring, class Element>
void PrepareBulkPolynomialInterpolation(const Ring &ring, Element *w, const Element x[], unsigned int n);
template <class Ring, class Element>
void PrepareBulkPolynomialInterpolationAt(const Ring &ring, Element *v, const Element &position, const Element x[], const Element w[], unsigned int n);
template <class Ring, class Element>
Element BulkPolynomialInterpolateAt(const Ring &ring, const Element y[], const Element v[], unsigned int n);

//!
template <class T, int instance>
inline bool operator==(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return a.Equals(b, a.ms_fixedRing);}
//!
template <class T, int instance>
inline bool operator!=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return !(a==b);}

//!
template <class T, int instance>
inline bool operator> (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return a.Degree() > b.Degree();}
//!
template <class T, int instance>
inline bool operator>=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return a.Degree() >= b.Degree();}
//!
template <class T, int instance>
inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return a.Degree() < b.Degree();}
//!
template <class T, int instance>
inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return a.Degree() <= b.Degree();}

//!
template <class T, int instance>
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, a.ms_fixedRing));}
//!
template <class T, int instance>
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, a.ms_fixedRing));}
//!
template <class T, int instance>
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator*(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Times(b, a.ms_fixedRing));}
//!
template <class T, int instance>
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, a.ms_fixedRing));}
//!
template <class T, int instance>
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(const CryptoPP::PolynomialOverFixedRing<T, instance> &a, const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
	{return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, a.ms_fixedRing));}

NAMESPACE_END

NAMESPACE_BEGIN(std)
template<class T> inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b)
{
	a.swap(b);
}
template<class T, int i> inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
{
	a.swap(b);
}
NAMESPACE_END

#endif