1 #ifndef CRYPTOPP_POLYNOMI_H
2 #define CRYPTOPP_POLYNOMI_H
13 NAMESPACE_BEGIN(CryptoPP)
33 RandomizationParameter(
unsigned int coefficientCount,
const typename T::RandomizationParameter &coefficientParameter )
34 : m_coefficientCount(coefficientCount), m_coefficientParameter(coefficientParameter) {}
37 unsigned int m_coefficientCount;
38 typename T::RandomizationParameter m_coefficientParameter;
39 friend class PolynomialOver<T>;
43 typedef typename T::Element CoefficientType;
53 : m_coefficients((size_t)count, ring.Identity()) {}
57 : m_coefficients(t.m_coefficients.size()) {*
this = t;}
61 : m_coefficients(1, element) {}
65 : m_coefficients(begin, end) {}
71 PolynomialOver(
const byte *encodedPolynomialOver,
unsigned int byteCount);
81 {Randomize(rng, parameter, ring);}
87 int Degree(
const Ring &ring)
const {
return int(CoefficientCount(ring))-1;}
89 unsigned int CoefficientCount(
const Ring &ring)
const;
91 CoefficientType
GetCoefficient(
unsigned int i,
const Ring &ring)
const;
100 void Randomize(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter,
const Ring &ring);
103 void SetCoefficient(
unsigned int i,
const CoefficientType &value,
const Ring &ring);
106 void Negate(
const Ring &ring);
116 bool IsZero(
const Ring &ring)
const {
return CoefficientCount(ring)==0;}
126 bool IsUnit(
const Ring &ring)
const;
136 CoefficientType EvaluateAt(
const CoefficientType &x,
const Ring &ring)
const;
147 std::istream& Input(std::istream &in,
const Ring &ring);
148 std::ostream& Output(std::ostream &out,
const Ring &ring)
const;
152 void FromStr(
const char *str,
const Ring &ring);
154 std::vector<CoefficientType> m_coefficients;
166 typedef typename T::Element CoefficientType;
202 static const ThisType &Zero();
203 static const ThisType &One();
221 ThisType& operator=(
const ThisType& t) {B::operator=(t);
return *
this;}
223 ThisType& operator+=(
const ThisType& t) {Accumulate(t, ms_fixedRing);
return *
this;}
225 ThisType& operator-=(
const ThisType& t) {Reduce(t, ms_fixedRing);
return *
this;}
227 ThisType& operator*=(
const ThisType& t) {
return *
this = *
this*t;}
229 ThisType& operator/=(
const ThisType& t) {
return *
this = *
this/t;}
231 ThisType& operator%=(
const ThisType& t) {
return *
this = *
this%t;}
234 ThisType& operator<<=(
unsigned int n) {ShiftLeft(n, ms_fixedRing);
return *
this;}
236 ThisType& operator>>=(
unsigned int n) {ShiftRight(n, ms_fixedRing);
return *
this;}
242 void Randomize(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter) {B::Randomize(rng, parameter, ms_fixedRing);}
245 void Negate() {B::Negate(ms_fixedRing);}
247 void swap(ThisType &t) {B::swap(t);}
255 ThisType operator+()
const {
return *
this;}
257 ThisType operator-()
const {
return ThisType(Inverse(ms_fixedRing));}
263 friend ThisType operator>>(ThisType a,
unsigned int n) {
return ThisType(a>>=n);}
265 friend ThisType operator<<(ThisType a,
unsigned int n) {
return ThisType(a<<=n);}
271 ThisType MultiplicativeInverse()
const {
return ThisType(B::MultiplicativeInverse(ms_fixedRing));}
273 bool IsUnit()
const {
return B::IsUnit(ms_fixedRing);}
276 ThisType Doubled()
const {
return ThisType(B::Doubled(ms_fixedRing));}
278 ThisType Squared()
const {
return ThisType(B::Squared(ms_fixedRing));}
280 CoefficientType EvaluateAt(
const CoefficientType &x)
const {
return B::EvaluateAt(x, ms_fixedRing);}
290 friend std::istream& operator>>(std::istream& in, ThisType &a)
291 {
return a.Input(in, ms_fixedRing);}
293 friend std::ostream& operator<<(std::ostream& out,
const ThisType &a)
294 {
return a.Output(out, ms_fixedRing);}
298 struct NewOnePolynomial
300 ThisType * operator()()
const
302 return new ThisType(ms_fixedRing.MultiplicativeIdentity());
306 static const Ring ms_fixedRing;
313 typedef T CoefficientRing;
315 typedef typename Element::CoefficientType CoefficientType;
321 {
return Element(rng, parameter, m_ring);}
324 {
return a.Equals(b, m_ring);}
326 const Element& Identity()
const
327 {
return this->result = m_ring.Identity();}
330 {
return this->result = a.Plus(b, m_ring);}
333 {a.Accumulate(b, m_ring);
return a;}
336 {
return this->result = a.Inverse(m_ring);}
339 {
return this->result = a.Minus(b, m_ring);}
342 {
return a.Reduce(b, m_ring);}
345 {
return this->result = a.Doubled(m_ring);}
347 const Element& MultiplicativeIdentity()
const
348 {
return this->result = m_ring.MultiplicativeIdentity();}
351 {
return this->result = a.Times(b, m_ring);}
354 {
return this->result = a.Squared(m_ring);}
356 bool IsUnit(
const Element &a)
const
357 {
return a.IsUnit(m_ring);}
360 {
return this->result = a.MultiplicativeInverse(m_ring);}
363 {
return this->result = a.DividedBy(b, m_ring);}
366 {
return this->result = a.Modulo(b, m_ring);}
377 Element Interpolate(
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
380 CoefficientType InterpolateAt(
const CoefficientType &position,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
387 void CalculateAlpha(std::vector<CoefficientType> &alpha,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
389 CoefficientRing m_ring;
392 template <
class Ring,
class Element>
393 void PrepareBulkPolynomialInterpolation(
const Ring &ring, Element *w,
const Element x[],
unsigned int n);
394 template <
class Ring,
class Element>
395 void PrepareBulkPolynomialInterpolationAt(
const Ring &ring, Element *v,
const Element &position,
const Element x[],
const Element w[],
unsigned int n);
396 template <
class Ring,
class Element>
397 Element BulkPolynomialInterpolateAt(
const Ring &ring,
const Element y[],
const Element v[],
unsigned int n);
400 template <
class T,
int instance>
401 inline bool operator==(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
402 {
return a.Equals(b, a.ms_fixedRing);}
404 template <
class T,
int instance>
405 inline bool operator!=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
409 template <
class T,
int instance>
410 inline bool operator> (
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
411 {
return a.Degree() > b.Degree();}
413 template <
class T,
int instance>
414 inline bool operator>=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
415 {
return a.Degree() >= b.Degree();}
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();}
426 template <
class T,
int instance>
427 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
428 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, a.ms_fixedRing));}
430 template <
class T,
int instance>
431 inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
432 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, a.ms_fixedRing));}
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.Times(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.DividedBy(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.Modulo(b, a.ms_fixedRing));}
453 template<
class T,
int i>
inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)