FAAST  0.2.1
FieldPolynomial.hpp
1 /*
2  This file is part of the FAAST library.
3 
4  Copyright (c) 2009 Luca De Feo and Éric Schost.
5 
6  The most recent version of FAAST is available at http://www.lix.polytechnique.fr/~defeo/FAAST
7 
8  This program is free software; you can redistribute it and/or
9  modify it under the terms of the GNU General Public License
10  as published by the Free Software Foundation; either version 2
11  of the License, or (at your option) any later version.
12 
13  This program is distributed in the hope that it will be useful,
14  but WITHOUT ANY WARRANTY; without even the implied warranty of
15  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16  GNU General Public License for more details.
17 
18  You should have received a copy of the GNU General Public License
19  along with this program; see file COPYING. If not, write to the Free Software
20  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
21 */
22 #ifndef FIELDPOLYNOMIAL_H_
23 #define FIELDPOLYNOMIAL_H_
24 
25 #include "Exceptions.hpp"
26 #include <string>
27 #include <vector>
28 
29 namespace FAAST {
30  template <class T> class Field;
31 
32 /****************** GCD ******************/
33 /* Find docs for these functions in the friends section of FieldElement */
34  template <class T> FieldPolynomial<T>
35  GCD(const FieldPolynomial<T>& P, const FieldPolynomial<T>& Q)
36  throw(NotInSameFieldException);
37 
38  template <class T> void
39  XGCD(const FieldPolynomial<T>& P, const FieldPolynomial<T>& Q,
40  FieldPolynomial<T>& U, FieldPolynomial<T>& V, FieldPolynomial<T>& G)
41  throw(NotInSameFieldException);
42 
43  template <class T> void
44  HalfGCD(FieldPolynomial<T>& U0, FieldPolynomial<T>& V0,
45  FieldPolynomial<T>& U1, FieldPolynomial<T>& V1,
46  const FieldPolynomial<T>& P, const FieldPolynomial<T>& Q,
47  const long d)
48  throw(NotInSameFieldException, BadParametersException);
49 /****************** Class FieldPolynomial ******************/
88  template <class T> class FieldPolynomial {
89 
90  friend class Field<T>;
91  friend class FieldElement<T>;
92 
93  /****************** GCD ******************/
100  friend FieldPolynomial<T> GCD<T>(const FieldPolynomial<T>& P, const FieldPolynomial<T>& Q)
101  throw(NotInSameFieldException);
117  friend void XGCD<T>(const FieldPolynomial<T>& P, const FieldPolynomial<T>& Q,
118  FieldPolynomial<T>& U, FieldPolynomial<T>& V, FieldPolynomial<T>& G)
119  throw(NotInSameFieldException);
120 
141  friend void
142  HalfGCD<T>(FieldPolynomial<T>& U0, FieldPolynomial<T>& V0,
143  FieldPolynomial<T>& U1, FieldPolynomial<T>& V1,
144  const FieldPolynomial<T>& P, const FieldPolynomial<T>& Q,
145  const long d)
146  throw(NotInSameFieldException, BadParametersException);
147 
155  public:
156  typedef T Infrastructure;
157 
158  private:
159  typedef typename T::GFp GFp;
160  typedef typename T::MatGFp MatGFp;
161  typedef typename T::GFpX GFpX;
162  typedef typename T::GFpE GFpE;
163  typedef typename T::GFpEX GFpEX;
164  typedef typename T::BigInt BigInt;
165  typedef typename T::Context Context;
169  /****************** Members ******************/
172  GFpX repBase;
174  GFpEX repExt;
176  bool base;
178  const Field<T>* parent_field;
182  public:
183  /****************/
195  FieldPolynomial() throw() : parent_field(NULL) {}
197  /****************/
211  const Field<T>& parent() const
212  throw(UndefinedFieldException) {
213  if (!parent_field)
214  throw UndefinedFieldException();
215  return *parent_field;
216  }
221  long degree() const throw();
224  /****************/
228  FieldPolynomial(const FieldPolynomial<T>&) throw();
229  FieldPolynomial<T>& operator=(const FieldPolynomial<T>&) throw();
230  /* \brief Degree 0 polynomial with constant coefficient \a e. */
231  FieldPolynomial(const FieldElement<T>& e) throw();
232  /* \brief Degree 0 polynomial with constant coefficient \a e. */
233  FieldPolynomial<T>& operator=(const FieldElement<T>& e) throw();
243  FieldPolynomial<T>& operator=(const BigInt& i)
244  throw(UndefinedFieldException);
247  /****************/
255  void getCoeff(const long i, FieldElement<T>& e)
256  const throw(BadParametersException);
271  void setCoeff(const long i, const FieldElement<T>& e)
272  throw(NotInSameFieldException, BadParametersException);
282  void setCoeff(const long i, const BigInt& c)
283  throw(UndefinedFieldException, BadParametersException);
291  void setCoeff(const long i)
292  throw(UndefinedFieldException, BadParametersException);
295  /****************** Arithmetics ******************/
303  FieldPolynomial<T> operator+(const FieldPolynomial<T>& e)
304  const throw(NotInSameFieldException) {
305  FieldPolynomial<T> tmp = *this;
306  tmp += e;
307  return tmp;
308  }
309  FieldPolynomial<T> operator-(const FieldPolynomial<T>& e)
310  const throw(NotInSameFieldException) {
311  FieldPolynomial<T> tmp = *this;
312  tmp -= e;
313  return tmp;
314  }
315  FieldPolynomial<T> operator*(const FieldPolynomial<T>& e)
316  const throw(NotInSameFieldException) {
317  FieldPolynomial<T> tmp = *this;
318  tmp *= e;
319  return tmp;
320  }
321  FieldPolynomial<T> operator/(const FieldPolynomial<T>& e)
322  const throw(NotInSameFieldException, DivisionByZeroException) {
323  FieldPolynomial<T> tmp = *this;
324  tmp /= e;
325  return tmp;
326  }
327  FieldPolynomial<T> operator%(const FieldPolynomial<T>& e)
328  const throw(NotInSameFieldException, DivisionByZeroException) {
329  FieldPolynomial<T> tmp = *this;
330  tmp %= e;
331  return tmp;
332  }
338  FieldPolynomial<T> operator<<(const long n) const {
339  FieldPolynomial<T> tmp;
340  tmp.LeftShift(*this, n);
341  return tmp;
342  }
348  FieldPolynomial<T> operator>>(const long n) const {
349  FieldPolynomial<T> tmp;
350  tmp.RightShift(*this, n);
351  return tmp;
352  }
353 
354  /* Self-incrementing binary operations. */
355  void operator+=(const FieldPolynomial<T>&)
356  throw(NotInSameFieldException);
357  void operator-=(const FieldPolynomial<T>&)
358  throw(NotInSameFieldException);
359  void operator*=(const FieldPolynomial<T>&)
360  throw(NotInSameFieldException);
361  void operator/=(const FieldPolynomial<T>&)
362  throw(NotInSameFieldException, DivisionByZeroException);
363  void operator%=(const FieldPolynomial<T>&)
364  throw(NotInSameFieldException, DivisionByZeroException);
368  void operator<<=(const long n)
369  { this->LeftShift(*this, n); }
373  void operator>>=(const long n)
374  { this->RightShift(*this, n); }
375 
377  void sum(const FieldPolynomial<T>& a, const FieldPolynomial<T>& b)
378  throw(NotInSameFieldException)
379  { operator=(a); operator+=(b); }
381  void difference(const FieldPolynomial<T>& a, const FieldPolynomial<T>& b)
382  throw(NotInSameFieldException)
383  { operator=(a); operator-=(b); }
385  void product(const FieldPolynomial<T>& a, const FieldPolynomial<T>& b)
386  throw(NotInSameFieldException)
387  { operator=(a); operator*=(b); }
389  void division(const FieldPolynomial<T>& a, const FieldPolynomial<T>& b)
390  throw(NotInSameFieldException, DivisionByZeroException)
391  { operator=(a); operator/=(b); }
393  void mod(const FieldPolynomial<T>& a, const FieldPolynomial<T>& b)
394  throw(NotInSameFieldException, DivisionByZeroException)
395  { operator=(a); operator%=(b); }
400  void LeftShift(const FieldPolynomial<T>& a, const long n);
405  void RightShift(const FieldPolynomial<T>& a, const long n);
406 
413  bool divides(const FieldPolynomial<T>& P) const throw();
414  FieldPolynomial<T> operator-() const throw() {
415  FieldPolynomial<T> tmp = *this;
416  tmp.negate();
417  return tmp;
418  }
420  FieldPolynomial<T> operator^(const long i) const throw() {
421  FieldPolynomial<T> tmp = *this;
422  tmp ^= i;
423  return tmp;
424  }
425  FieldPolynomial<T> derivative() const throw() {
426  FieldPolynomial<T> tmp = *this;
427  tmp.self_derivative();
428  return tmp;
429  }
432  FieldPolynomial<T> monic() const throw() {
433  FieldPolynomial<T> tmp = *this;
434  tmp.normalize();
435  return tmp;
436  }
442  FieldPolynomial<T> frobenius() const throw() {
443  FieldPolynomial<T> tmp = *this;
444  tmp.self_frobenius();
445  return tmp;
446  }
452  FieldPolynomial<T> frobenius(const long n) const throw() {
453  FieldPolynomial<T> tmp = *this;
454  tmp.self_frobenius(n);
455  return tmp;
456  }
464  void negate() throw();
466  void operator^=(const long) throw();
468  void self_derivative() throw();
472  void normalize() throw();
474  void self_frobenius() throw();
476  void self_frobenius(long) throw();
479  /****************/
499  FieldPolynomial<T> toScalarPolynomial() const throw(IllegalCoercionException);
509  FieldPolynomial<T> operator>>(const Field<T>&) const throw(IllegalCoercionException);
518  void operator>>=(const Field<T>& F) throw(IllegalCoercionException) {
519  FieldPolynomial<T> tmp = *this >> F;
520  *this = tmp;
521  }
525  bool isCoercible(const Field<T>&) const throw();
528  /****************/
534  FieldElement<T> evaluate(const FieldElement<T>& e,
535  vector<FieldPolynomial<T> >& minpols)
536  const throw(IllegalCoercionException, BadParametersException)
537  { return e.evaluate(*this, minpols); }
538 
543  FieldElement<T> evaluate(const FieldElement<T>& e)
544  const throw(IllegalCoercionException, BadParametersException)
545  { return e.evaluate(*this); }
547  /****************/
555  bool operator==(const FieldPolynomial<T>&) const throw(NotInSameFieldException);
557  bool operator==(const FieldElement<T>&) const throw(NotInSameFieldException);
559  bool operator==(const BigInt&) const throw();
560 
567  bool operator!=(const FieldPolynomial<T>& e)
568  const throw(NotInSameFieldException)
569  { return !(*this==e); }
571  bool operator!=(const FieldElement<T>& e)
572  const throw(NotInSameFieldException)
573  { return !(*this==e); }
575  bool operator!=(const BigInt& i) const throw()
576  { return !(*this==i); }
578  bool isZero() const throw() {
579  return !parent_field ||
580  (base ? IsZero(repBase) : IsZero(repExt));
581  }
583  bool isOne() const throw() {
584  return parent_field &&
585  (base ? IsOne(repBase) : IsOne(repExt));
586  }
590  bool isScalarPolynomial() const throw();
593  /****************/
611  void toInfrastructure(GFpX& P) const throw(IllegalCoercionException);
622  void toInfrastructure(GFpEX& P) const throw(IllegalCoercionException);
625  /****************/
628  ostream& print(ostream&) const;
643  ostream& print(ostream&, const string& varPoly, const string& varField) const;
659  ostream& print(ostream&, const string& varPoly, const vector<string>& varsField) const;
661  /****************** Destructor ******************/
662  ~FieldPolynomial() throw() {}
663 
664 
665  /*****************************************************/
666  /****************** Private section ******************/
667  /*****************************************************/
668 
669  private:
671  /****************/
676  FieldPolynomial(const Field<T>* p, const GFpX& PBase, const GFpEX& PExt, const bool b) throw() :
677  repBase(PBase), repExt(PExt), base(b), parent_field(p) {}
678  FieldPolynomial(const Field<T>* p, const GFpEX& P) throw() :
679  repExt(P), base(false), parent_field(p) {}
680  FieldPolynomial(const Field<T>* p, const GFpX& P) throw() :
681  repBase(P), base(true), parent_field(p) {}
683  /****************** Utility Routines ******************/
690  void sameLevel(const FieldElement<T>& e) const
691  throw(NotInSameFieldException) {
692  if (parent_field != e.parent_field)
693  throw NotInSameFieldException();
694  }
701  void sameLevel(const FieldPolynomial<T>& e) const
702  throw(NotInSameFieldException) {
703  if (parent_field != e.parent_field)
704  throw NotInSameFieldException();
705  }
707  };
708 /****************** Printing ******************/
712  template <class T> ostream&
713  operator<<(ostream& o, const FieldPolynomial<T>& P) {
714  return P.print(o);
715  }
716 }
717 
718 #endif /*FIELDPOLYNOMIAL_H_*/
Generated on Mon Jun 3 2013 20:49:49 for FAAST by   doxygen 1.8.1.2