8 #ifndef CRYPTOPP_POLYNOMI_H 9 #define CRYPTOPP_POLYNOMI_H 41 RandomizationParameter(
unsigned int coefficientCount,
const typename T::RandomizationParameter &coefficientParameter )
42 : m_coefficientCount(coefficientCount), m_coefficientParameter(coefficientParameter) {}
45 unsigned int m_coefficientCount;
46 typename T::RandomizationParameter m_coefficientParameter;
47 friend class PolynomialOver<T>;
51 typedef typename T::Element CoefficientType;
61 : m_coefficients((
size_t)count, ring.Identity()) {}
65 : m_coefficients(t.m_coefficients.size()) {*
this = t;}
69 : m_coefficients(1, element) {}
73 : m_coefficients(begin, end) {}
79 PolynomialOver(
const byte *encodedPolynomialOver,
unsigned int byteCount);
89 {Randomize(rng, parameter, ring);}
95 int Degree(
const Ring &ring)
const {
return int(CoefficientCount(ring))-1;}
97 unsigned int CoefficientCount(
const Ring &ring)
const;
99 CoefficientType
GetCoefficient(
unsigned int i,
const Ring &ring)
const;
111 void SetCoefficient(
unsigned int i,
const CoefficientType &value,
const Ring &ring);
114 void Negate(
const Ring &ring);
124 bool IsZero(
const Ring &ring)
const {
return CoefficientCount(ring)==0;}
134 bool IsUnit(
const Ring &ring)
const;
144 CoefficientType EvaluateAt(
const CoefficientType &x,
const Ring &ring)
const;
155 std::istream& Input(std::istream &in,
const Ring &ring);
156 std::ostream& Output(std::ostream &out,
const Ring &ring)
const;
160 void FromStr(
const char *str,
const Ring &ring);
162 std::vector<CoefficientType> m_coefficients;
174 typedef typename T::Element CoefficientType;
210 static const ThisType &Zero();
211 static const ThisType &One();
217 int Degree()
const {
return B::Degree(ms_fixedRing);}
221 CoefficientType
GetCoefficient(
unsigned int i)
const {
return B::GetCoefficient(i, ms_fixedRing);}
223 CoefficientType
operator[](
unsigned int i)
const {
return B::GetCoefficient(i, ms_fixedRing);}
229 ThisType& operator=(
const ThisType& t) {B::operator=(t);
return *
this;}
231 ThisType& operator+=(
const ThisType& t) {Accumulate(t, ms_fixedRing);
return *
this;}
233 ThisType& operator-=(
const ThisType& t) {Reduce(t, ms_fixedRing);
return *
this;}
235 ThisType& operator*=(
const ThisType& t) {
return *
this = *
this*t;}
237 ThisType& operator/=(
const ThisType& t) {
return *
this = *
this/t;}
239 ThisType& operator%=(
const ThisType& t) {
return *
this = *
this%t;}
242 ThisType& operator<<=(
unsigned int n) {ShiftLeft(n, ms_fixedRing);
return *
this;}
244 ThisType& operator>>=(
unsigned int n) {ShiftRight(n, ms_fixedRing);
return *
this;}
247 void SetCoefficient(
unsigned int i,
const CoefficientType &value) {B::SetCoefficient(i, value, ms_fixedRing);}
250 void Randomize(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter) {B::Randomize(rng, parameter, ms_fixedRing);}
253 void Negate() {B::Negate(ms_fixedRing);}
255 void swap(ThisType &t) {B::swap(t);}
261 bool operator!()
const {
return CoefficientCount()==0;}
263 ThisType operator+()
const {
return *
this;}
265 ThisType operator-()
const {
return ThisType(Inverse(ms_fixedRing));}
271 friend ThisType operator>>(ThisType a,
unsigned int n) {
return ThisType(a>>=n);}
273 friend ThisType operator<<(ThisType a,
unsigned int n) {
return ThisType(a<<=n);}
279 ThisType MultiplicativeInverse()
const {
return ThisType(B::MultiplicativeInverse(ms_fixedRing));}
281 bool IsUnit()
const {
return B::IsUnit(ms_fixedRing);}
284 ThisType Doubled()
const {
return ThisType(B::Doubled(ms_fixedRing));}
286 ThisType Squared()
const {
return ThisType(B::Squared(ms_fixedRing));}
288 CoefficientType EvaluateAt(
const CoefficientType &x)
const {
return B::EvaluateAt(x, ms_fixedRing);}
291 static void Divide(ThisType &r, ThisType &q,
const ThisType &a,
const ThisType &d)
292 {B::Divide(r, q, a, d, ms_fixedRing);}
298 friend std::istream& operator>>(std::istream& in, ThisType &a)
299 {
return a.Input(in, ms_fixedRing);}
301 friend std::ostream& operator<<(std::ostream& out,
const ThisType &a)
302 {
return a.Output(out, ms_fixedRing);}
306 struct NewOnePolynomial
308 ThisType * operator()()
const 310 return new ThisType(ms_fixedRing.MultiplicativeIdentity());
314 static const Ring ms_fixedRing;
321 typedef T CoefficientRing;
323 typedef typename Element::CoefficientType CoefficientType;
329 {
return Element(rng, parameter, m_ring);}
331 bool Equal(
const Element &a,
const Element &b)
const 332 {
return a.Equals(b, m_ring);}
334 const Element& Identity()
const 335 {
return this->result = m_ring.Identity();}
337 const Element& Add(
const Element &a,
const Element &b)
const 338 {
return this->result = a.Plus(b, m_ring);}
340 Element& Accumulate(Element &a,
const Element &b)
const 341 {a.Accumulate(b, m_ring);
return a;}
343 const Element& Inverse(
const Element &a)
const 344 {
return this->result = a.Inverse(m_ring);}
346 const Element& Subtract(
const Element &a,
const Element &b)
const 347 {
return this->result = a.Minus(b, m_ring);}
349 Element& Reduce(Element &a,
const Element &b)
const 350 {
return a.Reduce(b, m_ring);}
352 const Element& Double(
const Element &a)
const 353 {
return this->result = a.Doubled(m_ring);}
355 const Element& MultiplicativeIdentity()
const 356 {
return this->result = m_ring.MultiplicativeIdentity();}
358 const Element& Multiply(
const Element &a,
const Element &b)
const 359 {
return this->result = a.Times(b, m_ring);}
361 const Element&
Square(
const Element &a)
const 362 {
return this->result = a.Squared(m_ring);}
364 bool IsUnit(
const Element &a)
const 365 {
return a.IsUnit(m_ring);}
367 const Element& MultiplicativeInverse(
const Element &a)
const 368 {
return this->result = a.MultiplicativeInverse(m_ring);}
370 const Element& Divide(
const Element &a,
const Element &b)
const 371 {
return this->result = a.DividedBy(b, m_ring);}
373 const Element& Mod(
const Element &a,
const Element &b)
const 374 {
return this->result = a.Modulo(b, m_ring);}
376 void DivisionAlgorithm(Element &r, Element &q,
const Element &a,
const Element &d)
const 377 {Element::Divide(r, q, a, d, m_ring);}
385 Element Interpolate(
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
388 CoefficientType InterpolateAt(
const CoefficientType &position,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
395 void CalculateAlpha(std::vector<CoefficientType> &alpha,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
397 CoefficientRing m_ring;
400 template <
class Ring,
class Element>
401 void PrepareBulkPolynomialInterpolation(
const Ring &ring,
Element *w,
const Element x[],
unsigned int n);
402 template <
class Ring,
class Element>
403 void PrepareBulkPolynomialInterpolationAt(
const Ring &ring,
Element *v,
const Element &position,
const Element x[],
const Element w[],
unsigned int n);
404 template <
class Ring,
class Element>
405 Element BulkPolynomialInterpolateAt(
const Ring &ring,
const Element y[],
const Element v[],
unsigned int n);
408 template <
class T,
int instance>
409 inline bool operator==(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
410 {
return a.Equals(b, a.ms_fixedRing);}
412 template <
class T,
int instance>
413 inline bool operator!=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
417 template <
class T,
int instance>
418 inline bool operator> (
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
419 {
return a.Degree() > b.Degree();}
421 template <
class T,
int instance>
422 inline bool operator>=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
423 {
return a.Degree() >= b.Degree();}
425 template <
class T,
int instance>
426 inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
427 {
return a.Degree() < b.Degree();}
429 template <
class T,
int instance>
430 inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
431 {
return a.Degree() <= b.Degree();}
434 template <
class T,
int instance>
435 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
436 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, a.ms_fixedRing));}
438 template <
class T,
int instance>
439 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
440 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, a.ms_fixedRing));}
442 template <
class T,
int instance>
443 inline CryptoPP::PolynomialOverFixedRing<T, instance>
operator*(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
444 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Times(b, a.ms_fixedRing));}
446 template <
class T,
int instance>
447 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
448 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, a.ms_fixedRing));}
450 template <
class T,
int instance>
451 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
452 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, a.ms_fixedRing));}
457 template<
class T>
inline void swap(CryptoPP::PolynomialOver<T> &a, CryptoPP::PolynomialOver<T> &b)
461 template<
class T,
int i>
inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
Base class for all exceptions thrown by Crypto++.
bool operator>=(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
bool operator>(const ::PolynomialMod2 &a, const ::PolynomialMod2 &b)
compares degree
PolynomialOverFixedRing(Iterator first, Iterator last)
construct polynomial with specified coefficients, starting from coefficient of x^0 ...
inline::Integer operator*(const ::Integer &a, const ::Integer &b)
specify the distribution for randomization functions
CoefficientType operator[](unsigned int i) const
return coefficient for x^i
void SetCoefficient(unsigned int i, const CoefficientType &value, const Ring &ring)
set the coefficient for x^i to value
PolynomialOver(Iterator begin, Iterator end)
construct polynomial with specified coefficients, starting from coefficient of x^0 ...
Utility functions for the Crypto++ library.
PolynomialOver(const PolynomialOver< Ring > &t)
copy constructor
PolynomialOverFixedRing(const byte *encodedPoly, unsigned int byteCount)
convert from big-endian byte array
PolynomialOverFixedRing(unsigned int count=0)
creates the zero polynomial
PolynomialOverFixedRing(const char *str)
convert from string
unsigned int CoefficientCount() const
degree + 1
Abstract base classes that provide a uniform interface to this library.
PolynomialOverFixedRing(const ThisType &t)
copy constructor
CoefficientType GetCoefficient(unsigned int i, const Ring &ring) const
return coefficient for x^i
Abstract Euclidean Domain.
PolynomialOverFixedRing(const byte *BEREncodedPoly)
convert from Basic Encoding Rules encoded byte array
Interface for random number generators.
PolynomialOverFixedRing(const CoefficientType &element)
construct constant polynomial
Classes for performing mathematics over different fields.
represents single-variable polynomials over arbitrary rings
PolynomialOver(const char *str, const Ring &ring)
convert from string
Ring of polynomials over another ring.
Classes and functions for secure memory allocations.
int Degree() const
the zero polynomial will return a degree of -1
Polynomials over a fixed ring.
CoefficientType GetCoefficient(unsigned int i) const
return coefficient for x^i
PolynomialOver()
creates the zero polynomial
void SetCoefficient(unsigned int i, const CoefficientType &value)
set the coefficient for x^i to value
PolynomialOver(RandomNumberGenerator &rng, const RandomizationParameter ¶meter, const Ring &ring)
create a random PolynomialOver<T>
PolynomialOver(const CoefficientType &element)
construct constant polynomial
static void Divide(PolynomialOver< Ring > &r, PolynomialOver< Ring > &q, const PolynomialOver< Ring > &a, const PolynomialOver< Ring > &d, const Ring &ring)
calculate r and q such that (a == d*q + r) && (0 <= degree of r < degree of d)
static void Divide(ThisType &r, ThisType &q, const ThisType &a, const ThisType &d)
calculate r and q such that (a == d*q + r) && (0 <= r < abs(d))
PolynomialOverFixedRing(BufferedTransformation &bt)
convert from BER encoded byte array stored in a BufferedTransformation object
Crypto++ library namespace.
division by zero exception
int Degree(const Ring &ring) const
the zero polynomial will return a degree of -1
PolynomialOverFixedRing(RandomNumberGenerator &rng, const RandomizationParameter ¶meter)
create a random PolynomialOverFixedRing