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(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, 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, fixedRing) {}
00201
00202
static const ThisType &Zero();
00203
static const ThisType &One();
00204
00205
00206
00207
00208
00209 int Degree()
const {
return B::Degree(fixedRing);}
00210
00211 unsigned int CoefficientCount()
const {
return B::CoefficientCount(fixedRing);}
00212
00213 CoefficientType
GetCoefficient(
unsigned int i)
const {
return B::GetCoefficient(i, fixedRing);}
00214
00215 CoefficientType
operator[](
unsigned int i)
const {
return B::GetCoefficient(i, 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, fixedRing);
return *
this;}
00224
00225 ThisType& operator-=(
const ThisType& t) {Reduce(t, 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, fixedRing);
return *
this;}
00235
00236 ThisType& operator>>=(
unsigned int n) {ShiftRight(n, fixedRing);
return *
this;}
00237
00238
00239 void SetCoefficient(
unsigned int i,
const CoefficientType &value) {B::SetCoefficient(i, value, fixedRing);}
00240
00241
00242
void Randomize(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter) {B::Randomize(rng, parameter, fixedRing);}
00243
00244
00245
void Negate() {B::Negate(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(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(fixedRing));}
00272
00273
bool IsUnit()
const {
return B::IsUnit(fixedRing);}
00274
00275
00276 ThisType Doubled()
const {
return ThisType(B::Doubled(fixedRing));}
00277
00278 ThisType Squared()
const {
return ThisType(B::Squared(fixedRing));}
00279
00280 CoefficientType EvaluateAt(
const CoefficientType &x)
const {
return B::EvaluateAt(x, fixedRing);}
00281
00282
00283 static void Divide(
ThisType &r,
ThisType &q,
const ThisType &a,
const ThisType &d)
00284 {B::Divide(r, q, a, d, fixedRing);}
00285
00286
00287
00288
00289
00290
friend std::istream& operator>>(std::istream& in, ThisType &a)
00291 {
return a.Input(in, fixedRing);}
00292
00293
friend std::ostream& operator<<(std::ostream& out,
const ThisType &a)
00294 {
return a.Output(out, fixedRing);}
00295
00296
00297
private:
00298
static const Ring fixedRing;
00299 };
00300
00301
00302 template <
class T>
class RingOfPolynomialsOver :
public AbstractEuclideanDomain<PolynomialOver<T> >
00303 {
00304
public:
00305
typedef T CoefficientRing;
00306
typedef PolynomialOver<T> Element;
00307
typedef typename Element::CoefficientType CoefficientType;
00308
typedef typename Element::RandomizationParameter RandomizationParameter;
00309
00310
RingOfPolynomialsOver(
const CoefficientRing &ring) : m_ring(ring) {}
00311
00312
Element RandomElement(
RandomNumberGenerator &rng,
const RandomizationParameter ¶meter)
00313 {
return Element(rng, parameter, m_ring);}
00314
00315
bool Equal(
const Element &a,
const Element &b)
const
00316
{
return a.Equals(b, m_ring);}
00317
00318
const Element& Identity()
const
00319
{
return result = m_ring.Identity();}
00320
00321
const Element& Add(
const Element &a,
const Element &b)
const
00322
{
return result = a.Plus(b, m_ring);}
00323
00324
Element& Accumulate(
Element &a,
const Element &b)
const
00325
{a.Accumulate(b, m_ring);
return a;}
00326
00327
const Element& Inverse(
const Element &a)
const
00328
{
return result = a.Inverse(m_ring);}
00329
00330
const Element& Subtract(
const Element &a,
const Element &b)
const
00331
{
return result = a.Minus(b, m_ring);}
00332
00333
Element& Reduce(
Element &a,
const Element &b)
const
00334
{
return a.Reduce(b, m_ring);}
00335
00336
const Element& Double(
const Element &a)
const
00337
{
return result = a.Doubled(m_ring);}
00338
00339
const Element& MultiplicativeIdentity()
const
00340
{
return result = m_ring.MultiplicativeIdentity();}
00341
00342
const Element& Multiply(
const Element &a,
const Element &b)
const
00343
{
return result = a.Times(b, m_ring);}
00344
00345
const Element&
Square(
const Element &a)
const
00346
{
return result = a.Squared(m_ring);}
00347
00348
bool IsUnit(
const Element &a)
const
00349
{
return a.IsUnit(m_ring);}
00350
00351
const Element& MultiplicativeInverse(
const Element &a)
const
00352
{
return result = a.MultiplicativeInverse(m_ring);}
00353
00354
const Element& Divide(
const Element &a,
const Element &b)
const
00355
{
return result = a.DividedBy(b, m_ring);}
00356
00357
const Element& Mod(
const Element &a,
const Element &b)
const
00358
{
return result = a.Modulo(b, m_ring);}
00359
00360
void DivisionAlgorithm(
Element &r,
Element &q,
const Element &a,
const Element &d)
const
00361
{Element::Divide(r, q, a, d, m_ring);}
00362
00363
class InterpolationFailed :
public Exception
00364 {
00365
public:
00366 InterpolationFailed() :
Exception(OTHER_ERROR,
"RingOfPolynomialsOver<T>: interpolation failed") {}
00367 };
00368
00369
Element Interpolate(
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
00370
00371
00372 CoefficientType InterpolateAt(
const CoefficientType &position,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
00373
00374
00375
00376
00377
00378
protected:
00379
void CalculateAlpha(std::vector<CoefficientType> &alpha,
const CoefficientType x[],
const CoefficientType y[],
unsigned int n)
const;
00380
00381 CoefficientRing m_ring;
00382 };
00383
00384
template <
class Ring,
class Element>
00385
void PrepareBulkPolynomialInterpolation(
const Ring &ring, Element *w,
const Element x[],
unsigned int n);
00386
template <
class Ring,
class Element>
00387
void PrepareBulkPolynomialInterpolationAt(
const Ring &ring, Element *v,
const Element &position,
const Element x[],
const Element w[],
unsigned int n);
00388
template <
class Ring,
class Element>
00389 Element BulkPolynomialInterpolateAt(
const Ring &ring,
const Element y[],
const Element v[],
unsigned int n);
00390
00391
00392
template <
class T,
int instance>
00393
inline bool operator==(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00394 {
return a.Equals(b, fixedRing);}
00395
00396
template <
class T,
int instance>
00397
inline bool operator!=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00398 {
return !(a==b);}
00399
00400
00401
template <
class T,
int instance>
00402
inline bool operator> (
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00403 {
return a.Degree() > b.Degree();}
00404
00405
template <
class T,
int instance>
00406
inline bool operator>=(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00407 {
return a.Degree() >= b.Degree();}
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
00418
template <
class T,
int instance>
00419
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator+(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00420 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Plus(b, fixedRing));}
00421
00422
template <
class T,
int instance>
00423
inline CryptoPP::PolynomialOverFixedRing<T, instance> operator-(
const CryptoPP::PolynomialOverFixedRing<T, instance> &a,
const CryptoPP::PolynomialOverFixedRing<T, instance> &b)
00424 {
return CryptoPP::PolynomialOverFixedRing<T, instance>(a.Minus(b, fixedRing));}
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.Times(b, 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.DividedBy(b, 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.Modulo(b, fixedRing));}
00437
00438 NAMESPACE_END
00439
00440 NAMESPACE_BEGIN(std)
00441 template<class T> inline
void swap(CryptoPP::
PolynomialOver<T> &a, CryptoPP::
PolynomialOver<T> &b)
00442 {
00443 a.swap(b);
00444 }
00445
template<
class T,
int i>
inline void swap(CryptoPP::PolynomialOverFixedRing<T,i> &a, CryptoPP::PolynomialOverFixedRing<T,i> &b)
00446 {
00447 a.swap(b);
00448 }
00449 NAMESPACE_END
00450
00451
#endif