FAAST  0.2.1
Field.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 FIELD_H_
23 #define FIELD_H_
24 
25 #include "Exceptions.hpp"
26 #include "FieldElement.hpp"
27 #include "FieldPolynomial.hpp"
28 #include <memory>
29 
30 namespace FAAST {
31 
32 #ifdef FAAST_TIMINGS
33 
41  typedef struct TIMINGS {
43  double CYCLOTOMIC;
45  double PSEUDOTRACES;
48  double LIFTUP;
51  double TRACEVEC;
53  double BUILDIRRED;
55  double IRREDTEST;
57  double PRIMETEST;
60  double ARTINMATRIX;
62  double BUILDSTEM;
63 
64  TIMINGS() : CYCLOTOMIC(0),
65  PSEUDOTRACES(0),
66  LIFTUP(0),
67  TRACEVEC(0),
68  BUILDIRRED(0),
69  IRREDTEST(0),
70  PRIMETEST(0),
71  ARTINMATRIX(0),
72  BUILDSTEM(0)
73  {}
74  } TIMINGS;
75 #endif
76 
77 
117  template <class T> class Field {
118 
119  friend class FieldElement<T>;
120  friend void pushDown<T>(const FieldElement<T>& e, vector<FieldElement<T> >& v) throw(NoSubFieldException);
121  friend void liftUp<T>(const vector<FieldElement<T> >& v, FieldElement<T>& e) throw(NotInSameFieldException, NoOverFieldException);
122 
123 #ifdef FAAST_TIMINGS
124  public:
128  static TIMINGS TIME;
129 #endif
130 
138  public:
140  typedef T Infrastructure;
141 
142  private:
143  typedef typename T::GFp GFp;
144  typedef typename T::MatGFp MatGFp;
145  typedef typename T::VecGFp VecGFp;
146  typedef typename T::GFpX GFpX;
147  typedef typename T::GFpE GFpE;
148  typedef typename T::GFpEX GFpEX;
149  typedef typename T::BigInt BigInt;
150  typedef typename T::Context Context;
151  typedef typename T::GFpXModulus GFpXModulus;
155  /****************/
158  mutable const Field<T>* subfield;
160  mutable const Field<T>* overfield;
164  Context context;
166  const auto_ptr<const FieldElement<T> > primitive;
168  mutable vector<FieldElement<T> > pseudotraces;
170  mutable auto_ptr<const FieldElement<T> > liftuphelper;
174  mutable MatGFp artin;
178  mutable long artinLine;
180  const bool plusone;
182  const bool twopminusone;
184  mutable auto_ptr<const Context> Phi;
187  /****************/
190  const Field<T>* stem;
193  /****************/
198  const Field<T>* vsubfield;
200  const auto_ptr<const FieldElement<T> > gen;
205  const auto_ptr<const FieldElement<T> > alpha;
209  public:
210  /****************/
213  const BigInt p;
215  const long d;
225  const long height;
229  public:
230  /****************/
259  static const Field<T>& createField(const bool test = true)
260  throw (NotPrimeException, NotIrreducibleException);
284  static const Field<T>& createField(const GFpX& P, const bool test = true)
285  throw (NotPrimeException, NotIrreducibleException);
309  static const Field<T>& createField
310  (const BigInt& p, const long d = 1, const bool test = true)
311  throw (NotPrimeException, BadParametersException);
314  /****************/
330  const Field<T>& ArtinSchreierExtension() const
331  throw (CharacteristicTooLargeException, NotSupportedException);
355  const Field<T>& ArtinSchreierExtension(const FieldElement<T>& alpha)
356  const throw (CharacteristicTooLargeException, NotIrreducibleException,
357  NotSupportedException, IllegalCoercionException);
369  FieldElement<T> Couveignes2000(const FieldElement<T>& alpha)
370  const throw(IllegalCoercionException, IsIrreducibleException);
373  /****************/
380  BigInt characteristic() const throw () { return p; }
386  long degree() const throw () { return d; }
388  ZZ cardinality() const throw ();
394  long ArtinSchreierHeight() const throw () { return height; }
405  FieldPolynomial<T> generatingPolynomial() const throw();
416  FieldPolynomial<T> primitivePolynomial() const throw();
419  /****************/
429  FieldElement<T> scalar(const BigInt& i) const throw ();
431  FieldElement<T> zero() const throw () { return scalar(0); }
433  FieldElement<T> one() const throw () { return scalar(1); }
439  FieldElement<T> generator() const throw () { return *gen; }
448  FieldElement<T> primitiveElement() const throw ()
449  { return *stem->primitive >> *this; }
451  FieldElement<T> random() const throw ();
454  /****************/
481  void switchContext() const throw();
492  FieldElement<T> fromInfrastructure(const GFp& e) const throw();
505  FieldElement<T> fromInfrastructure(const GFpE& e) const throw(IllegalCoercionException);
516  FieldPolynomial<T> fromInfrastructure(const GFpX& P) const throw();
529  FieldPolynomial<T> fromInfrastructure(const GFpEX& P) const throw(IllegalCoercionException);
532  /****************/
539  const Field<T>& primeField() const throw();
547  const Field<T>& baseField() const throw();
559  const Field<T>& subField() const throw(NoSubFieldException) {
560 #ifdef FAAST_DEBUG
561  if (!stem) throw FAASTException("No stem in stemField().");
562 #endif
563  if (!stem->subfield) throw NoSubFieldException();
564  return *(stem->subfield);
565  }
578  const Field<T>& overField() const throw(NoOverFieldException) {
579 #ifdef FAAST_DEBUG
580  if (!stem) throw FAASTException("No stem in stemField().");
581 #endif
582  if (!stem->overfield) throw NoOverFieldException();
583  return *(stem->overfield);
584  }
598  const Field<T>& stemField() const throw() {
599 #ifdef FAAST_DEBUG
600  if (!stem) throw FAASTException("No stem in stemField().");
601 #endif
602  return *stem;
603  }
607  /****************/
643  void toBivariate(const FieldElement<T>& e, vector<FieldElement<T> >& v) const
644  throw(IllegalCoercionException);
645 
682  void toUnivariate(const vector<FieldElement<T> >& v, FieldElement<T>& e) const
683  throw(NotInSameFieldException, IllegalCoercionException);
686  /****************/
692  bool operator==(const Field<T>& F) const throw () { return this==&F; }
697  bool operator!=(const Field<T>& F) const throw () { return !(*this==F); }
703  bool isIsomorphic(const Field<T>& F) const throw () { return stem==F.stem; }
709  bool isSubFieldOf(const Field<T>& F) const throw ();
715  bool isOverFieldOf(const Field<T>& F) const throw ()
716  { return isIsomorphic(F) || F.isSubFieldOf(*this); }
720  bool isPrimeField() const throw ()
721  { return stem->subfield == NULL; }
723  bool isBaseField() const throw ()
724  { return !stem->overfield || stem->overfield->height == 1; }
726  /****************/
729  ostream& print(ostream& o) const;
731  /****************** Destructor ******************/
732  ~Field() throw (FAASTException)
733  { throw FAASTException("Destroying fields is no good."); }
734 
735 
736  /*****************************************************/
737  /****************** Private section ******************/
738  /*****************************************************/
740  private:
741  /****************/
745  const FieldElement<T>& getPseudotrace(const long i) const;
746  const FieldElement<T>& getLiftup() const;
747  const MatGFp& getArtinMatrix() const;
748  const Context& getCyclotomic() const;
751  /****************** Copy prohibited ******************/
752  void operator=(const Field<T>&);
753  Field(const Field<T>&);
754 
755  /****************** Couveignes 2000 subroutines ******************/
763  void couveignes00(FieldElement<T>& res, const FieldElement<T>& alpha) const;
764 
765  /****************/
768  Field<T> (
769  const Field<T>* sub,
770  const Field<T>* over,
771  const Context& ctxt,
772  const FieldElement<T>* pri,
773  const vector<FieldElement<T> >& pseudo,
774  const FieldElement<T>* liftup,
775  const MatGFp& mat,
776  const long line,
777  const bool pluso,
778  const bool twopminuso,
779  const Context* Ph,
780  const Field<T>* st,
781  const Field<T>* vsub,
782  const FieldElement<T>* g,
783  const FieldElement<T>* a,
784  const BigInt& cha,
785  const long deg,
786  const long h
787  ) throw() :
788  subfield(sub), overfield(over),
789  context(ctxt),
790  primitive(pri),
791  pseudotraces(pseudo),
792  liftuphelper(liftup),
793  artin(mat), artinLine(line),
794  plusone(pluso), twopminusone(twopminuso),
795  Phi(Ph),
796  stem(st), vsubfield(vsub),
797  gen(g), alpha(a),
798  p(cha), d(deg), height(h)
799  {}
801  Field<T> (
802  const Field<T>* sub,
803  const Context& ctxt,
804  const GFpE& pri,
805  const BigInt& cha,
806  const long deg,
807  const GFpE& g
808  ) throw() :
809  subfield(sub), overfield(NULL),
810  context(ctxt),
811  primitive(new FieldElement<T>(this, pri)),
812  pseudotraces(),
813  liftuphelper(),
814  artin(), artinLine(-1),
815  plusone(false), twopminusone(false),
816  Phi(),
817  stem(this), vsubfield(NULL),
818  gen(new FieldElement<T>(this, g)),
819  alpha(),
820  p(cha), d(deg), height(0)
821  {}
823  Field<T> (
824  const Context& ctxt,
825  const GFp& pri,
826  const BigInt& cha
827  ) throw() :
828  subfield(NULL), overfield(NULL),
829  context(ctxt),
830  primitive(new FieldElement<T>(this, pri)),
831  pseudotraces(),
832  liftuphelper(),
833  artin(), artinLine(-1),
834  plusone(false), twopminusone(false),
835  Phi(),
836  stem(this), vsubfield(NULL),
837  gen(new FieldElement<T>(this, pri)),
838  alpha(),
839  p(cha), d(1), height(0)
840  {}
842  Field<T> (
843  const Field<T>* sub,
844  const Context& ctxt,
845  const GFpE& pri,
846  const bool po,
847  const bool tpmo,
848  const BigInt& cha,
849  const long deg,
850  const long h,
851  const FieldElement<T>* aleph,
852  const Field<T>* vsub = NULL
853  ) throw() :
854  subfield(sub), overfield(NULL),
855  context(ctxt),
856  primitive(new FieldElement<T>(this, pri)),
857  pseudotraces(),
858  liftuphelper(),
859  artin(), artinLine(-1),
860  plusone(po), twopminusone(tpmo),
861  Phi(),
862  stem(this), vsubfield(vsub),
863  gen(new FieldElement<T>(this, pri)),
864  alpha(aleph),
865  p(cha), d(deg), height(h)
866  {}
868  Field<T> (
869  const Field<T>* st,
870  const FieldElement<T>& gen,
871  const FieldElement<T>* aleph,
872  const Field<T>* vsub
873  ) throw() :
874  subfield(NULL), overfield(NULL),
875  context(),
876  primitive(NULL),
877  pseudotraces(),
878  liftuphelper(),
879  artin(), artinLine(-1),
880  plusone(), twopminusone(),
881  Phi(),
882  stem(st), vsubfield(vsub),
883  gen(new FieldElement<T>(this, gen.repBase, gen.repExt, gen.base)),
884  alpha(aleph),
885  p(st->p), d(st->d), height(st->height)
886  {}
889  };
890 
891  /****************** Printing ******************/
895  template <class T> ostream& operator<<(ostream& o, const Field<T>& F) {
896  return F.print(o);
897  }
898 }
899 
900 #endif /*FIELD_H_*/
Generated on Mon Jun 3 2013 20:49:49 for FAAST by   doxygen 1.8.1.2