00001
#ifndef CRYPTOPP_POLYNOMI_H
00002
#define CRYPTOPP_POLYNOMI_H
00003
00004
00005
00006
#include "cryptlib.h"
00007
#include "misc.h"
00008
#include "algebra.h"
00009
00010
#include <iosfwd>
00011
#include <vector>
00012
00013 NAMESPACE_BEGIN(CryptoPP)
00014
00015
00016
00017 template <class T> class
PolynomialOver
00018 {
00019
public:
00020
00021
00022
00023 class DivideByZero :
public Exception
00024 {
00025
public:
00026
DivideByZero() :
Exception(OTHER_ERROR,
"PolynomialOver<T>: division by zero") {}
00027 };
00028
00029
00030 class RandomizationParameter
00031 {
00032
public:
00033
RandomizationParameter(
unsigned int coefficientCount,
const typename T::RandomizationParameter &coefficientParameter )
00034 : m_coefficientCount(coefficientCount), m_coefficientParameter(coefficientParameter) {}
00035
00036
private:
00037
unsigned int m_coefficientCount;
00038
typename T::RandomizationParameter m_coefficientParameter;
00039
friend class PolynomialOver<T>;
00040 };
00041
00042
typedef T Ring;
00043
typedef typename T::Element CoefficientType;
00044
00045
00046
00047
00048
00049 PolynomialOver() {}
00050
00051
00052 PolynomialOver(
const Ring &ring,
unsigned int count)
00053 : m_coefficients((size_t)count, ring.Identity()) {}
00054
00055
00056 PolynomialOver(
const PolynomialOver<Ring> &t)
00057 : m_coefficients(t.m_coefficients.size()) {*
this = t;}
00058
00059
00060 PolynomialOver(
const CoefficientType &element)
00061 : m_coefficients(1, element) {}
00062
00063
00064 template <
typename Iterator> PolynomialOver(Iterator begin, Iterator end)
00065 : m_coefficients(begin, end) {}
00066
00067
00068 PolynomialOver(
const char *str,
const Ring &ring) {FromStr(str, ring);}
00069
00070
00071 PolynomialOver(
const byte *encodedPolynomialOver,
unsigned int byteCount);
00072
00073
00074
explicit PolynomialOver(
const byte *BEREncodedPolynomialOver);
00075
00076
00077
explicit PolynomialOver(
BufferedTransformation &bt);
00078
00079
00080 PolynomialOver(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter,
const Ring &ring)
00081 {Randomize(rng, parameter, ring);}
00082
00083
00084
00085
00086
00087 int Degree(
const Ring &ring)
const {
return int(CoefficientCount(ring))-1;}
00088
00089
unsigned int CoefficientCount(
const Ring &ring)
const;
00090
00091 CoefficientType GetCoefficient(
unsigned int i,
const Ring &ring)
const;
00092
00093
00094
00095
00096
00097
PolynomialOver<Ring>& operator=(
const PolynomialOver<Ring>& t);
00098
00099
00100
void Randomize(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter,
const Ring &ring);
00101
00102
00103
void SetCoefficient(
unsigned int i,
const CoefficientType &value,
const Ring &ring);
00104
00105
00106
void Negate(
const Ring &ring);
00107
00108
00109
void swap(
PolynomialOver<Ring> &t);
00110
00111
00112
00113
00114
00115
bool Equals(
const PolynomialOver<Ring> &t,
const Ring &ring)
const;
00116
bool IsZero(
const Ring &ring)
const {
return CoefficientCount(ring)==0;}
00117
00118
PolynomialOver<Ring> Plus(
const PolynomialOver<Ring>& t,
const Ring &ring)
const;
00119
PolynomialOver<Ring> Minus(
const PolynomialOver<Ring>& t,
const Ring &ring)
const;
00120
PolynomialOver<Ring> Inverse(
const Ring &ring)
const;
00121
00122
PolynomialOver<Ring> Times(
const PolynomialOver<Ring>& t,
const Ring &ring)
const;
00123
PolynomialOver<Ring> DividedBy(
const PolynomialOver<Ring>& t,
const Ring &ring)
const;
00124
PolynomialOver<Ring> Modulo(
const PolynomialOver<Ring>& t,
const Ring &ring)
const;
00125
PolynomialOver<Ring> MultiplicativeInverse(
const Ring &ring)
const;
00126
bool IsUnit(
const Ring &ring)
const;
00127
00128
PolynomialOver<Ring>& Accumulate(
const PolynomialOver<Ring>& t,
const Ring &ring);
00129
PolynomialOver<Ring>& Reduce(
const PolynomialOver<Ring>& t,
const Ring &ring);
00130
00131
00132
PolynomialOver<Ring> Doubled(
const Ring &ring)
const {
return Plus(*
this, ring);}
00133
00134
PolynomialOver<Ring> Squared(
const Ring &ring)
const {
return Times(*
this, ring);}
00135
00136 CoefficientType EvaluateAt(
const CoefficientType &x,
const Ring &ring)
const;
00137
00138
PolynomialOver<Ring>& ShiftLeft(
unsigned int n,
const Ring &ring);
00139
PolynomialOver<Ring>& ShiftRight(
unsigned int n,
const Ring &ring);
00140
00141
00142
static void Divide(
PolynomialOver<Ring> &r,
PolynomialOver<Ring> &q,
const PolynomialOver<Ring> &a,
const PolynomialOver<Ring> &d,
const Ring &ring);
00143
00144
00145
00146
00147 std::istream& Input(std::istream &in,
const Ring &ring);
00148 std::ostream& Output(std::ostream &out,
const Ring &ring)
const;
00149
00150
00151
private:
00152
void FromStr(
const char *str,
const Ring &ring);
00153
00154 std::vector<CoefficientType> m_coefficients;
00155 };
00156
00157
00158
00159 template <
class T,
int instance>
class PolynomialOverFixedRing :
private PolynomialOver<T>
00160 {
00161
typedef PolynomialOver<T> B;
00162
typedef PolynomialOverFixedRing<T, instance> ThisType;
00163
00164
public:
00165
typedef T Ring;
00166
typedef typename T::Element CoefficientType;
00167
typedef typename B::DivideByZero DivideByZero;
00168
typedef typename B::RandomizationParameter RandomizationParameter;
00169
00170
00171
00172
00173 PolynomialOverFixedRing(
unsigned int count = 0) :
B(ms_fixedRing, count) {}
00174
00175
00176 PolynomialOverFixedRing(
const ThisType &t) :
B(t) {}
00177
00178
explicit PolynomialOverFixedRing(
const B &t) : B(t) {}
00179
00180
00181 PolynomialOverFixedRing(
const CoefficientType &element) :
B(element) {}
00182
00183
00184 template <
typename Iterator>
PolynomialOverFixedRing(Iterator first, Iterator last)
00185 :
B(first, last) {}
00186
00187
00188 explicit PolynomialOverFixedRing(
const char *str) :
B(str, ms_fixedRing) {}
00189
00190
00191 PolynomialOverFixedRing(
const byte *encodedPoly,
unsigned int byteCount) :
B(encodedPoly, byteCount) {}
00192
00193
00194 explicit PolynomialOverFixedRing(
const byte *BEREncodedPoly) :
B(BEREncodedPoly) {}
00195
00196
00197 explicit PolynomialOverFixedRing(
BufferedTransformation &bt) :
B(bt) {}
00198
00199
00200 PolynomialOverFixedRing(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter) :
B(rng, parameter, ms_fixedRing) {}
00201
00202
static const ThisType &Zero();
00203
static const ThisType &One();
00204
00205
00206
00207
00208
00209 int Degree()
const {
return B::Degree(ms_fixedRing);}
00210
00211 unsigned int CoefficientCount()
const {
return B::CoefficientCount(ms_fixedRing);}
00212
00213 CoefficientType
GetCoefficient(
unsigned int i)
const {
return B::GetCoefficient(i, ms_fixedRing);}
00214
00215 CoefficientType
operator[](
unsigned int i)
const {
return B::GetCoefficient(i, ms_fixedRing);}
00216
00217
00218
00219
00220
00221 ThisType& operator=(
const ThisType& t) {B::operator=(t);
return *
this;}
00222
00223 ThisType& operator+=(
const ThisType& t) {Accumulate(t, ms_fixedRing);
return *
this;}
00224
00225 ThisType& operator-=(
const ThisType& t) {Reduce(t, ms_fixedRing);
return *
this;}
00226
00227 ThisType& operator*=(
const ThisType& t) {
return *
this = *
this*t;}
00228
00229 ThisType& operator/=(
const ThisType& t) {
return *
this = *
this/t;}
00230
00231 ThisType& operator%=(
const ThisType& t) {
return *
this = *
this%t;}
00232
00233
00234 ThisType& operator<<=(
unsigned int n) {ShiftLeft(n, ms_fixedRing);
return *
this;}
00235
00236 ThisType& operator>>=(
unsigned int n) {ShiftRight(n, ms_fixedRing);
return *
this;}
00237
00238
00239 void SetCoefficient(
unsigned int i,
const CoefficientType &value) {B::SetCoefficient(i, value, ms_fixedRing);}
00240
00241
00242
void Randomize(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter) {B::Randomize(rng, parameter, ms_fixedRing);}
00243
00244
00245
void Negate() {B::Negate(ms_fixedRing);}
00246
00247
void swap(ThisType &t) {B::swap(t);}
00248
00249
00250
00251
00252
00253
bool operator!()
const {
return CoefficientCount()==0;}
00254
00255 ThisType operator+()
const {
return *
this;}
00256
00257 ThisType operator-()
const {
return ThisType(Inverse(ms_fixedRing));}
00258
00259
00260
00261
00262
00263
friend ThisType operator>>(ThisType a,
unsigned int n) {
return ThisType(a>>=n);}
00264
00265
friend ThisType operator<<(ThisType a,
unsigned int n) {
return ThisType(a<<=n);}
00266
00267
00268
00269
00270
00271 ThisType MultiplicativeInverse()
const {
return ThisType(B::MultiplicativeInverse(ms_fixedRing));}
00272
00273
bool IsUnit()
const {
return B::IsUnit(ms_fixedRing);}
00274
00275
00276 ThisType Doubled()
const {
return ThisType(B::Doubled(ms_fixedRing));}
00277
00278 ThisType Squared()
const {
return ThisType(B::Squared(ms_fixedRing));}
00279
00280 CoefficientType EvaluateAt(
const CoefficientType &x)
const {
return B::EvaluateAt(x, ms_fixedRing);}
00281
00282
00283 static void Divide(
ThisType &r,
ThisType &q,
const ThisType &a,
const ThisType &d)
00284 {B::Divide(r, q, a, d, ms_fixedRing);}
00285
00286
00287
00288
00289
00290
friend std::istream& operator>>(std::istream& in, ThisType &a)
00291 {
return a.Input(in, ms_fixedRing);}
00292
00293
friend std::ostream& operator<<(std::ostream& out,
const ThisType &a)
00294 {
return a.Output(out, ms_fixedRing);}
00295
00296
00297
private:
00298
struct NewOnePolynomial
00299 {
00300 ThisType * operator()()
const
00301
{
00302
return new ThisType(ms_fixedRing.MultiplicativeIdentity());
00303 }
00304 };
00305
00306
static const Ring ms_fixedRing;
00307 };
00308
00309
00310 template <
class T>
class RingOfPolynomialsOver :
public AbstractEuclideanDomain<PolynomialOver<T> >
00311 {
00312
public:
00313
typedef T CoefficientRing;
00314
typedef PolynomialOver<T> Element;
00315
typedef typename Element::CoefficientType CoefficientType;
00316
typedef typename Element::RandomizationParameter RandomizationParameter;
00317
00318
RingOfPolynomialsOver(
const CoefficientRing &ring) : m_ring(ring) {}
00319
00320
Element RandomElement(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter)
00321 {
return Element(rng, parameter, m_ring);}
00322
00323
bool Equal(
const Element &a,
const Element &b)
const
00324
{
return a.Equals(b, m_ring);}
00325
00326
const Element& Identity()
const
00327
{
return this->result = m_ring.Identity();}
00328
00329
const Element& Add(
const Element &a,
const Element &b)
const
00330
{
return this->result = a.Plus(b, m_ring);}
00331
00332
Element& Accumulate(
Element &a,
const Element &b)
const
00333
{a.Accumulate(b, m_ring);
return a;}
00334
00335
const Element& Inverse(
const Element &a)
const
00336
{
return this->result = a.Inverse(m_ring);}
00337
00338
const Element& Subtract(
const Element &a,
const Element &b)
const
00339
{
return this->result = a.Minus(b, m_ring);}
00340
00341
Element& Reduce(
Element &a,
const Element &b)
const
00342
{
return a.Reduce(b, m_ring);}
00343
00344
const Element& Double(
const Element &a)
const
00345
{
return this->result = a.Doubled(m_ring);}
00346
00347
const Element& MultiplicativeIdentity()
const
00348
{
return this->result = m_ring.MultiplicativeIdentity();}
00349
00350
const Element& Multiply(
const Element &a,
const Element &b)
const
00351
{
return this->result = a.Times(b, m_ring);}
00352
00353
const Element&
Square(
const Element &a)
const
00354
{
return this->result = a.Squared(m_ring);}
00355
00356
bool IsUnit(
const Element &a)
const
00357
{
return a.IsUnit(m_ring);}
00358
00359
const Element& MultiplicativeInverse(
const Element &a)
const
00360
{
return this->result = a.MultiplicativeInverse(m_ring);}
00361
00362
const Element& Divide(
const Element &a,
const Element &b)
const
00363
{
return this->result = a.DividedBy(b, m_ring);}
00364
00365
const Element& Mod(
const Element &a,
const Element &b)
const
00366
{
return this->result = a.Modulo(b, m_ring);}
00367
00368
void DivisionAlgorithm(
Element &r,
Element &q,
const Element &a,
const Element &d)
const
00369
{Element::Divide(r, q, a, d, m_ring);}
00370
00371
class InterpolationFailed :
public Exception
00372 {
00373
public:
00374 InterpolationFailed() :
Exception(OTHER_ERROR,
"RingOfPolynomialsOver<T>: interpolation failed") {}
00375 };
00376
00377
Element Interpolate(
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
00378
00379
00380 CoefficientType InterpolateAt(
const CoefficientType &position,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
00381
00382
00383
00384
00385
00386
protected:
00387
void CalculateAlpha(std::vector<CoefficientType> &alpha,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
00388
00389 CoefficientRing m_ring;
00390 };
00391
00392
template <
class Ring,
class Element>
00393
void PrepareBulkPolynomialInterpolation(
const Ring &ring, Element *w,
const Element x[],
unsigned int n);
00394
template <
class Ring,
class Element>
00395
void PrepareBulkPolynomialInterpolationAt(
const Ring &ring, Element *v,
const Element &position,
const Element x[],
const Element w[],
unsigned int n);
00396
template <
class Ring,
class Element>
00397 Element BulkPolynomialInterpolateAt(
const Ring &ring,
const Element y[],
const Element v[],
unsigned int n);
00398
00399
00400
template <
class T,
int instance>
00401
inline bool operator==(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00402 {
return a.Equals(b, a.ms_fixedRing);}
00403
00404
template <
class T,
int instance>
00405
inline bool operator!=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00406 {
return !(a==b);}
00407
00408
00409
template <
class T,
int instance>
00410
inline bool operator> (
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00411 {
return a.Degree() > b.Degree();}
00412
00413
template <
class T,
int instance>
00414
inline bool operator>=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00415 {
return a.Degree() >= b.Degree();}
00416
00417
template <
class T,
int instance>
00418
inline bool operator< (const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00419 {
return a.Degree() < b.Degree();}
00420
00421
template <
class T,
int instance>
00422
inline bool operator<=(const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00423 {
return a.Degree() <= b.Degree();}
00424
00425
00426
template <
class T,
int instance>
00427
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00428 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, a.ms_fixedRing));}
00429
00430
template <
class T,
int instance>
00431
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00432 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, a.ms_fixedRing));}
00433
00434
template <
class T,
int instance>
00435
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator*(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00436 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Times(b, a.ms_fixedRing));}
00437
00438
template <
class T,
int instance>
00439
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator/(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00440 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.DividedBy(b, a.ms_fixedRing));}
00441
00442
template <
class T,
int instance>
00443
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator%(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00444 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Modulo(b, a.ms_fixedRing));}
00445
00446 NAMESPACE_END
00447
00448 NAMESPACE_BEGIN(std)
00449 template<class T> inline
void swap(CryptoPP::
PolynomialOver<T> &a, CryptoPP::
PolynomialOver<T> &b)
00450 {
00451 a.swap(b);
00452 }
00453
template<
class T,
int i>
inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
00454 {
00455 a.swap(b);
00456 }
00457 NAMESPACE_END
00458
00459
#endif