polynomi.h

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

#ifndef CRYPTOPP_POLYNOMI_H
#define CRYPTOPP_POLYNOMI_H

/*! \file */

#include "cryptlib.h"
#include "misc.h"
#include "algebra.h"

#include <iosfwd>
#include <vector>

NAMESPACE_BEGIN(CryptoPP)

//! represents single-variable polynomials over arbitrary rings
/*!	\nosubgrouping */
template <class T> class PolynomialOver
{
public:
	//! \name ENUMS, EXCEPTIONS, and TYPEDEFS
	//@{
		//! division by zero exception
		class DivideByZero : public Exception 
		{
		public: 
			DivideByZero() : Exception(OTHER_ERROR, "PolynomialOver<T>: division by zero") {}
		};

		//! specify the distribution for randomization functions
		class RandomizationParameter
		{
		public:
			RandomizationParameter(unsigned int coefficientCount, const typename T::RandomizationParameter &coefficientParameter )
				: m_coefficientCount(coefficientCount), m_coefficientParameter(coefficientParameter) {}

		private:
			unsigned int m_coefficientCount;
			typename T::RandomizationParameter m_coefficientParameter;
			friend class PolynomialOver<T>;
		};

		typedef T Ring;
		typedef typename T::Element CoefficientType;
	//@}

	//! \name CREATORS
	//@{
		//! creates the zero polynomial
		PolynomialOver() {}

		//!
		PolynomialOver(const Ring &ring, unsigned int count)
			: m_coefficients((size_t)count, ring.Identity()) {}

		//! copy constructor
		PolynomialOver(const PolynomialOver<Ring> &t)
			: m_coefficients(t.m_coefficients.size()) {*this = t;}

		//! construct constant polynomial
		PolynomialOver(const CoefficientType &element)
			: m_coefficients(1, element) {}

		//! construct polynomial with specified coefficients, starting from coefficient of x^0
		template <typename Iterator> PolynomialOver(Iterator begin, Iterator end)
			: m_coefficients(begin, end) {}

		//! convert from string
		PolynomialOver(const char *str, const Ring &ring) {FromStr(str, ring);}

		//! convert from big-endian byte array
		PolynomialOver(const byte *encodedPolynomialOver, unsigned int byteCount);

		//! convert from Basic Encoding Rules encoded byte array
		explicit PolynomialOver(const byte *BEREncodedPolynomialOver);

		//! convert from BER encoded byte array stored in a BufferedTransformation object
		explicit PolynomialOver(BufferedTransformation &bt);

		//! create a random PolynomialOver<T>
		PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring)
			{Randomize(rng, parameter, ring);}
	//@}

	//! \name ACCESSORS
	//@{
		//! the zero polynomial will return a degree of -1
		int Degree(const Ring &ring) const {return int(CoefficientCount(ring))-1;}
		//!
		unsigned int CoefficientCount(const Ring &ring) const;
		//! return coefficient for x^i
		CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const;
	//@}

	//! \name MANIPULATORS
	//@{
		//!
		PolynomialOver<Ring>&  operator=(const PolynomialOver<Ring>& t);

		//!
		void Randomize(RandomNumberGenerator &rng, const RandomizationParameter &parameter, const Ring &ring);

		//! set the coefficient for x^i to value
		void SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring);

		//!
		void Negate(const Ring &ring);

		//!
		void swap(PolynomialOver<Ring> &t);
	//@}


	//! \name BASIC ARITHMETIC ON POLYNOMIALS
	//@{
		bool Equals(const PolynomialOver<Ring> &t, const Ring &ring) const;
		bool IsZero(const Ring &ring) const {return CoefficientCount(ring)==0;}

		PolynomialOver<Ring> Plus(const PolynomialOver<Ring>& t, const Ring &ring) const;
		PolynomialOver<Ring> Minus(const PolynomialOver<Ring>& t, const Ring &ring) const;
		PolynomialOver<Ring> Inverse(const Ring &ring) const;

		PolynomialOver<Ring> Times(const PolynomialOver<Ring>& t, const Ring &ring) const;
		PolynomialOver<Ring> DividedBy(const PolynomialOver<Ring>& t, const Ring &ring) const;
		PolynomialOver<Ring> Modulo(const PolynomialOver<Ring>& t, const Ring &ring) const;
		PolynomialOver<Ring> MultiplicativeInverse(const Ring &ring) const;
		bool IsUnit(const Ring &ring) const;

		PolynomialOver<Ring>& Accumulate(const PolynomialOver<Ring>& t, const Ring &ring);
		PolynomialOver<Ring>& Reduce(const PolynomialOver<Ring>& t, const Ring &ring);

		//!
		PolynomialOver<Ring> Doubled(const Ring &ring) const {return Plus(*this, ring);}
		//!
		PolynomialOver<Ring> Squared(const Ring &ring) const {return Times(*this, ring);}

		CoefficientType EvaluateAt(const CoefficientType &x, const Ring &ring) const;

		PolynomialOver<Ring>& ShiftLeft(unsigned int n, const Ring &ring);
		PolynomialOver<Ring>& ShiftRight(unsigned int n, const Ring &ring);

		//! calculate r and q such that (a == d*q + r) && (0 <= degree of r < degree of d)
		static void Divide(PolynomialOver<Ring> &r, PolynomialOver<Ring> &q, const PolynomialOver<Ring> &a, const PolynomialOver<Ring> &d, const Ring &ring);
	//@}

	//! \name INPUT/OUTPUT
	//@{
		std::istream& Input(std::istream &in, const Ring &ring);
		std::ostream& Output(std::ostream &out, const Ring &ring) const;
	//@}

private:
	void FromStr(const char *str, const Ring &ring);

	std::vector<CoefficientType> m_coefficients;
};

//! Polynomials over a fixed ring
/*! Having a fixed ring allows overloaded operators */
template <class T, int instance> class PolynomialOverFixedRing : private PolynomialOver<T>
{
	typedef PolynomialOver<T> B;
	typedef PolynomialOverFixedRing<T, instance> ThisType;

public:
	typedef T Ring;
	typedef typename T::Element CoefficientType;
	typedef typename B::DivideByZero DivideByZero;
	typedef typename B::RandomizationParameter RandomizationParameter;

	//! \name CREATORS
	//@{
		//! creates the zero polynomial
		PolynomialOverFixedRing(unsigned int count = 0) : B(ms_fixedRing, count) {}

		//! copy constructor
		PolynomialOverFixedRing(const ThisType &t) : B(t) {}

		explicit PolynomialOverFixedRing(const B &t) : B(t) {}

		//! construct constant polynomial
		PolynomialOverFixedRing(const CoefficientType &element) : B(element) {}

		//! construct polynomial with specified coefficients, starting from coefficient of x^0
		template <typename Iterator> PolynomialOverFixedRing(Iterator first, Iterator last)
			: B(first, last) {}

		//! convert from string
		explicit PolynomialOverFixedRing(const char *str) : B(str, ms_fixedRing) {}

		//! convert from big-endian byte array
		PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount) : B(encodedPoly, byteCount) {}

		//! convert from Basic Encoding Rules encoded byte array
		explicit PolynomialOverFixedRing(const byte *BEREncodedPoly) : B(BEREncodedPoly) {}

		//! convert from BER encoded byte array stored in a BufferedTransformation object
		explicit PolynomialOverFixedRing(BufferedTransformation &bt) : B(bt) {}

		//! create a random PolynomialOverFixedRing
		PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter &parameter) : B(rng, parameter, ms_fixedRing) {}

		static const ThisType &Zero();
		static const ThisType &One();
	//@}

	//! \name ACCESSORS
	//@{
		//! the zero polynomial will return a degree of -1
		int Degree() const {return B::Degree(ms_fixedRing);}
		//! degree + 1
		unsigned int CoefficientCount() const {return B::CoefficientCount(ms_fixedRing);}
		//! return coefficient for x^i
		CoefficientType GetCoefficient(unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);}
		//! return coefficient for x^i
		CoefficientType operator[](unsigned int i) const {return B::GetCoefficient(i, ms_fixedRing);}
	//@}

	//! \name MANIPULATORS
	//@{
		//!
		ThisType&  operator=(const ThisType& t) {B::operator=(t); return *this;}
		//!
		ThisType&  operator+=(const ThisType& t) {Accumulate(t, ms_fixedRing); return *this;}
		//!
		ThisType&  operator-=(const ThisType& t) {Reduce(t, ms_fixedRing); return *this;}
		//!
		ThisType&  operator*=(const ThisType& t) {return *this = *this*t;}
		//!
		ThisType&  operator/=(const ThisType& t) {return *this = *this/t;}
		//!