FAAST  0.2.1
FieldElement.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 FIELDELEMENT_H_
23 #define FIELDELEMENT_H_
24 
25 #include "Exceptions.hpp"
26 #include <string>
27 #include <vector>
28 
29 namespace FAAST {
30  template <class T> class Field;
31  template <class T> class FieldElement;
32  template <class T> class FieldPolynomial;
33 
34 /****************** Level embedding ******************/
35 /* Find docs for these functions in the friends section of FieldElement */
36  template <class T>
37  void pushDown(const FieldElement<T>& e, vector<FieldElement<T> >& v)
38  throw(NoSubFieldException);
39 
40  template <class T>
41  void liftUp(const vector<FieldElement<T> >& v, FieldElement<T>& e)
42  throw(NotInSameFieldException, NoOverFieldException);
43 
44 
45 /****************** Class FieldElement ******************/
86  template <class T> class FieldElement {
87 
88  friend class Field<T>;
89  friend class FieldPolynomial<T>;
127  friend void pushDown<T>(const FieldElement<T>& e, vector<FieldElement<T> >& v) throw(NoSubFieldException);
171  friend void liftUp<T>(const vector<FieldElement<T> >& v, FieldElement<T>& e) throw(NotInSameFieldException, NoOverFieldException);
172 
180  public:
181  typedef T Infrastructure;
182 
183  private:
184  typedef typename T::GFp GFp;
185  typedef typename T::MatGFp MatGFp;
186  typedef typename T::GFpX GFpX;
187  typedef typename T::GFpE GFpE;
188  typedef typename T::GFpEX GFpEX;
189  typedef typename T::BigInt BigInt;
190  typedef typename T::Context Context;
193  /****************** Members ******************/
196  GFp repBase;
198  GFpE repExt;
200  bool base;
202  const Field<T>* parent_field;
205  public:
206  /****************/
217  FieldElement() throw() : parent_field(NULL) {}
219  /****************/
233  const Field<T>& parent() const
234  throw(UndefinedFieldException) {
235  if (!parent_field)
236  throw UndefinedFieldException();
237  return *parent_field;
238  }
241  /****************/
245  FieldElement(const FieldElement<T>& e) throw();
246  FieldElement<T>& operator=(const FieldElement<T>& e) throw();
256  FieldElement<T>& operator=(const BigInt& i)
257  throw(UndefinedFieldException);
260  /****************** Arithmetics ******************/
268  FieldElement<T> operator+(const FieldElement<T>& e)
269  const throw(NotInSameFieldException) {
270  FieldElement<T> tmp = *this;
271  tmp += e;
272  return tmp;
273  }
274  FieldElement<T> operator-(const FieldElement<T>& e)
275  const throw(NotInSameFieldException) {
276  FieldElement<T> tmp = *this;
277  tmp -= e;
278  return tmp;
279  }
280  FieldElement<T> operator*(const FieldElement<T>& e)
281  const throw(NotInSameFieldException) {
282  FieldElement<T> tmp = *this;
283  tmp *= e;
284  return tmp;
285  }
286  FieldElement<T> operator/(const FieldElement<T>& e)
287  const throw(NotInSameFieldException, DivisionByZeroException) {
288  FieldElement<T> tmp = *this;
289  tmp /= e;
290  return tmp;
291  }
292 
293  /* Self-incrementing binary operators. */
294  void operator+=(const FieldElement<T>&)
295  throw(NotInSameFieldException);
296  void operator-=(const FieldElement<T>&)
297  throw(NotInSameFieldException);
298  void operator*=(const FieldElement<T>&)
299  throw(NotInSameFieldException);
300  void operator/=(const FieldElement<T>&)
301  throw(NotInSameFieldException, DivisionByZeroException);
302 
304  void sum(const FieldElement<T>& a, const FieldElement<T>& b)
305  throw(NotInSameFieldException)
306  { operator=(a); operator+=(b); }
308  void difference(const FieldElement<T>& a, const FieldElement<T>& b)
309  throw(NotInSameFieldException)
310  { operator=(a); operator-=(b); }
312  void product(const FieldElement<T>& a, const FieldElement<T>& b)
313  throw(NotInSameFieldException)
314  { operator=(a); operator*=(b); }
316  void division(const FieldElement<T>& a, const FieldElement<T>& b)
317  throw(NotInSameFieldException, DivisionByZeroException)
318  { operator=(a); operator/=(b); }
325  FieldElement<T> operator-() const throw() {
326  FieldElement<T> tmp = *this;
327  tmp.negate();
328  return tmp;
329  }
331  FieldElement<T> inv() const throw(DivisionByZeroException) {
332  FieldElement<T> tmp = *this;
333  tmp.self_inv();
334  return tmp;
335  }
337  FieldElement<T> operator^(const ZZ& i) const throw() {
338  FieldElement<T> tmp = *this;
339  tmp ^= i;
340  return tmp;
341  }
343  FieldElement<T> operator^(const long i) const throw() {
344  FieldElement<T> tmp = *this;
345  tmp ^= i;
346  return tmp;
347  }
348  /* Frobenius and iterated frobenius */
350  FieldElement<T> frobenius() const throw() {
351  FieldElement<T> tmp = *this;
352  tmp.self_frobenius();
353  return tmp;
354  }
359  FieldElement<T> frobenius(const long n) const throw() {
360  FieldElement<T> tmp = *this;
361  tmp.self_frobenius(n);
362  return tmp;
363  }
370  FieldElement<T> trace(const Field<T>& F)
371  const throw(NotASubFieldException) {
372  FieldElement<T> tmp = *this;
373  tmp.self_trace(F);
374  return tmp;
375  }
377  FieldElement<T> trace() const throw();
389  FieldElement<T> pseudotrace(unsigned long n) const throw() {
390  FieldElement<T> tmp = *this;
391  tmp.self_pseudotrace(n);
392  return tmp;
393  }
401  void negate() throw();
403  void self_inv() throw(DivisionByZeroException);
405  void operator^=(const ZZ&) throw();
407  void operator^=(const long) throw();
409  void self_frobenius() throw();
411  void self_frobenius(long) throw();
413  void self_trace(const Field<T>& F) throw(NotASubFieldException);
415  void self_trace() throw();
420  void self_pseudotrace(unsigned long) throw();
423  /****************/
426  FieldPolynomial<T> minimalPolynomial() const throw() {
427  parent_field->switchContext();
428  GFpX minpol;
429  MinPolyMod(minpol, rep(repExt), GFpE::modulus());
430  return parent_field->primeField().fromInfrastructure(minpol);
431  }
445  FieldPolynomial<T> minimalPolynomial(const Field<T>& F)
446  const throw(NotASubFieldException, NotSupportedException) {
447  vector<FieldPolynomial<T> > minpols;
448  minimalPolynomials(F, minpols);
449  return minpols[0];
450  }
471  void minimalPolynomials(const Field<T>& F, vector<FieldPolynomial<T> >& res)
472  const throw(NotASubFieldException, NotSupportedException);
473 
506  FieldPolynomial<T> affineMinimalPolynomial(
507  const Field<T>& F, const FieldElement<T>& a,
508  vector<FieldPolynomial<T> >& minpols)
509  const throw(NotASubFieldException, NoSuchPolynomialException,
510  NotSupportedException, BadParametersException);
511 
533  FieldPolynomial<T> affineMinimalPolynomial(
534  const Field<T>& F, const FieldElement<T>& a)
535  const throw(NotASubFieldException, NoSuchPolynomialException,
536  NotSupportedException) {
537  vector<FieldPolynomial<T> > minpols;
538  return affineMinimalPolynomial(F,a,minpols);
539  }
540 
570  FieldElement<T> evaluate(const FieldPolynomial<T>& P,
571  vector<FieldPolynomial<T> >& minpols)
572  const throw(IllegalCoercionException, BadParametersException);
573 
593  FieldElement<T> evaluate(const FieldPolynomial<T>& P)
594  const throw(IllegalCoercionException) {
595  vector<FieldPolynomial<T> > minpols;
596  return evaluate(P, minpols);
597  }
600  /****************/
620  FieldElement<T> toScalar() const throw(IllegalCoercionException);
629  FieldElement<T> operator>>(const Field<T>& F) const
630  throw(IllegalCoercionException) {
631  FieldElement<T> tmp = *this;
632  tmp >>= F;
633  return tmp;
634  }
642  void operator>>=(const Field<T>&) throw(IllegalCoercionException);
646  bool isCoercible(const Field<T>&) const throw();
649  /****************/
657  bool operator==(const FieldElement<T>&) const throw(NotInSameFieldException);
659  bool operator==(const BigInt&) const throw();
666  bool operator!=(const FieldElement<T>& e) const throw(NotInSameFieldException)
667  { return !(*this==e); }
669  bool operator!=(const BigInt& i) const throw() { return !(*this==i); }
671  bool isZero() const throw() {
672  return !parent_field ||
673  (base ? IsZero(repBase) : IsZero(repExt));
674  }
676  bool isOne() const throw() {
677  return parent_field &&
678  (base ? IsOne(repBase) : IsOne(repExt));
679  }
683  bool isScalar() const throw();
685  /****************/
703  void toInfrastructure(GFp& e) const throw(IllegalCoercionException);
714  void toInfrastructure(GFpE& e) const throw(IllegalCoercionException);
717  /****************/
720  ostream& print(ostream& o) const;
725  ostream& print(ostream& o, const string& var) const;
744  ostream& print(ostream& o, const vector<string>& vars) const;
746  /****************** Destructor ******************/
747  ~FieldElement() throw() {}
748 
749 
750  /*****************************************************/
751  /****************** Private section ******************/
752  /*****************************************************/
753 
754  private:
756  /****************/
762  void BigFrob(const long j);
768  void SmallFrob(const long n);
773  void BigPTrace(const long j);
779  void BigPTraceVector(vector<FieldElement<T> >& v, const long j) const;
785  void SmallPTrace(const long n);
788  /****************/
793  FieldElement(const Field<T>* p, const GFp& PBase, const GFpE& PExt, const bool b) throw() :
794  repBase(PBase), repExt(PExt), base(b), parent_field(p) {}
795  FieldElement(const Field<T>* p, const GFpE& P) throw() :
796  repExt(P), base(false), parent_field(p) {}
797  FieldElement(const Field<T>* p, const GFp& P) throw() :
798  repBase(P), base(true), parent_field(p) {}
800  /****************** Utility Routines ******************/
807  void sameLevel(const FieldElement<T>& e) const
808  throw(NotInSameFieldException) {
809  if (parent_field != e.parent_field)
810  throw NotInSameFieldException();
811  }
813  };
814 
815 /****************** Printing ******************/
819  template <class T> ostream&
820  operator<<(ostream& o, const FieldElement<T>& e) {
821  return e.print(o);
822  }
823 }
824 
825 #endif /*FIELDELEMENT_H_*/
Generated on Mon Jun 3 2013 20:49:49 for FAAST by   doxygen 1.8.1.2