Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
BigPrimeField.hpp
1
2 #ifndef _BIG_PRIME_FIELD_H_
3 #define _BIG_PRIME_FIELD_H_
4
5 #include "BPASFiniteField.hpp"
6 #include <iostream>
7 #include <string>
8
9 using std::endl;
10 using std::cout;
11
12 //forward declarations
13 class Integer;
14 class RationalNumber;
16 class SmallPrimeField;
20 template <class Ring>
22
23 // prime field with big number, using GMP functions
24 /**
25  * A prime field whose prime can be arbitrarily large.
26  */
27 class BigPrimeField : public BPASFiniteField<BigPrimeField> {
28
29 private:
30
31  static mpz_class prime;
32  mpz_class a;
33
34 public:
35
36  static mpz_class characteristic;
37  static RingProperties properties;
38  // static bool isPrimeField;
39  // static bool isSmallPrimeField;
40  // static bool isComplexField;
41
42  BigPrimeField ();
43
44  BigPrimeField (mpz_class _a);
45
46  BigPrimeField (long int _a);
47
48  BigPrimeField (const BigPrimeField& c);
49
50  explicit BigPrimeField (const Integer& c);
51
52  explicit BigPrimeField (const RationalNumber& c);
53
54  explicit BigPrimeField (const ComplexRationalNumber& c);
55
56  explicit BigPrimeField (const SmallPrimeField& c); //? NOT SURE
57
58  explicit BigPrimeField (const GeneralizedFermatPrimeField& c);
59
61
63
65
67
69
70  template <class Ring>
72
73  BigPrimeField* BPFpointer(BigPrimeField* b);
74
75  BigPrimeField* BPFpointer(RationalNumber* a);
76
77  BigPrimeField* BPFpointer(SmallPrimeField* a);
78
80
81  static void setPrime(mpz_class p){
82  prime = p;
83  // characteristic = p;
84  }
85
86  mpz_class Prime() const;
87
88  mpz_class number() const;
89
90  void whichprimefield();
91
92  BigPrimeField findPrimitiveRootOfUnity(long int n) const {
93  return BigPrimeField::findPrimitiveRootofUnity(mpz_class(n));
94  }
95
96
97  static BigPrimeField findPrimitiveRootofUnity(mpz_class n){
98  if ( ((prime - 1) % n != 0)){
99  cout << "ERROR: n does not divide prime - 1." << endl;
100  return -1;
101  }
102  bool flag = false;
103  mpz_class q = (prime - 1) / n;
104  BigPrimeField p1 (prime - 1);
105  BigPrimeField c;
106  int i = 0;
107  mpz_class test = q * n / 2;
108  srand (time(NULL));
109  while(i < 20){
110  c = rand();
111  if ((c^test) == p1) {
112  flag = true;
113  return (c^q);
114  }
115  i++;
116  }
117  if (!flag ){
118  cout << "No primitive root found!"<< endl;
119  return 0;
120  }
121  // If no primitive root found
122  }
123
124  BigPrimeField unitCanonical(BigPrimeField* u = NULL, BigPrimeField* v = NULL) const;
125
127
128  BigPrimeField& operator= (long int k);
129
130  BigPrimeField& operator= (const mpz_class& k);
131
132  inline bool isZero() const {
133  return (a == 0);
134  }
135
136  inline void zero() {
137  a = 0;
138  }
139
140  inline bool isOne() const {
141  return (a == 1);
142  }
143
144  inline void one() {
145  a = 1;
146  }
147
148  inline bool isNegativeOne() const {
149  return (a == (prime - 1));
150  }
151
152  inline void negativeOne() {
153  a = prime - 1;
154  }
155
156  inline int isConstant() const {
157  if (a >= 0)
158  return 1;
159  else { return -1; }
160  }
161
162  inline bool operator== (const BigPrimeField& c) const {
163  if (a == c.a)
164  return 1;
165  else { return 0; }
166  }
167
168  inline bool operator== (const mpz_class& k) const {
169  BigPrimeField r (*this);
170  BigPrimeField b (k);
171  if (b == r){
172  return 1;
173  }
174  else {
175  return 0;
176  }
177  }
178
179  inline bool operator== (long int k) const {
180  BigPrimeField r (*this);
181  BigPrimeField b (k);
182  if (b == r){
183  return 1;
184  }
185  else {
186  return 0;
187  }
188  }
189
190  inline bool operator!= (const BigPrimeField& c) const {
191  if (a == c.a)
192  return 0;
193  else { return 1; }
194  }
195
196  inline bool operator!= (const mpz_class& k) const {
197  BigPrimeField r (*this);
198  BigPrimeField b (k);
199  if (b == r){
200  return 0;
201  }
202  else {
203  return 1;
204  }
205  }
206
207  inline bool operator!= (long int k) const {
208  BigPrimeField r (*this);
209  BigPrimeField b (k);
210  if (b == r){
211  return 0;
212  }
213  else {
214  return 1;
215  }
216  }
217
218  inline BigPrimeField operator+ (const BigPrimeField& c) const {
219  BigPrimeField r (*this);
220  return (r += c);
221  }
222
223  inline BigPrimeField operator+ (long int c) const {
224  BigPrimeField r (*this);
225  BigPrimeField b (c);
226  return (r += b);
227  }
228
229  inline BigPrimeField operator+ (const mpz_class& c) const {
230  BigPrimeField r (*this);
231  BigPrimeField b(c);
232  return (r += b);
233  }
234
236  a = (a + c.a);
237  if(a>prime)
238  a -= prime;
239  return *this;
240  }
241
242  inline BigPrimeField operator+= (long int c) {
243  BigPrimeField r (*this);
244  BigPrimeField b (c);
245  return (r += b);
246  }
247
248  inline BigPrimeField operator+= (const mpz_class& c) {
249  BigPrimeField r (*this);
250  BigPrimeField b(c);
251  return (r += b);
252  }
253
254  inline BigPrimeField operator- (const BigPrimeField& c) const {
255  BigPrimeField r (*this);
256  return (r -= c);
257  }
258
259  inline BigPrimeField operator- (long int c) const {
260  BigPrimeField r (*this);
261  BigPrimeField b (c);
262  return (r += b);
263  }
264
265  inline BigPrimeField operator- (const mpz_class& c) const {
266  BigPrimeField r (*this);
267  BigPrimeField b(c);
268  return (r += b);
269  }
270
272  if ((a - c.a)<0){
273  a = prime+(a - c.a);
274  }
275  else{
276  a = a - c.a;
277  }
278  return *this;
279  }
280
281  inline BigPrimeField operator-= (long int c) {
282  BigPrimeField r (*this);
283  BigPrimeField b (c);
284  return (r += b);
285  }
286
287  inline BigPrimeField operator-= (const mpz_class& c) {
288  BigPrimeField r (*this);
289  BigPrimeField b(c);
290  return (r += b);
291  }
292
293  inline BigPrimeField operator- () const {
294  BigPrimeField ret = *this;
295  ret.a = prime - a;
296  return ret;
297  }
298
299  inline BigPrimeField operator* (const BigPrimeField& c) const {
300  BigPrimeField r (*this);
301  return (r *= c);
302  }
303
304  inline BigPrimeField operator* (const mpz_class& c) const {
305  BigPrimeField r (*this);
306  return (r *= c);
307  }
308
309  inline BigPrimeField operator* (long int c) const {
310  BigPrimeField r (*this);
311  return (r *= c);
312  }
313
315  a = (a * c.a)%prime;
316  return *this;
317  }
318
319  inline BigPrimeField& operator*= (const mpz_class& m) {
320  mpz_class c(m);
321  while(c<0){
322  c=c+prime;
323  }
324  a = (a * c)%prime;
325  return *this;
326  }
327
328  inline BigPrimeField& operator*= (long int c) {
329  mpz_class b = c;
330  while(b<0){
331  b=b+prime;
332  }
333  a = (a * b)%prime;
334  return *this;
335  }
336
337  inline BigPrimeField operator^ (long long int c) const {
338  BigPrimeField r (*this);
339  mpz_class b(std::to_string(c), 10);
340  return (r ^ b);
341  }
342
343  inline BigPrimeField operator^ (const mpz_class& exp) const {
344  BigPrimeField r;
345  mpz_class e = exp;
346  if (isZero() || isOne() || e == 1)
347  r = *this;
348  else if (e == 2) {
349  r = *this * *this;
350  }
351  else if (e > 2) {
352  BigPrimeField x (*this);
353  r.one();
354
355  while (e != 0) {
356  if ((e % 2) == 1)
357  r *= x;
358  x = x * x;
359  e >>= 1;
360  }
361  }
362  else if (e == 0) {
363  r.one();
364  }
365  else {
366  r = *this ^ (-e);
367  r=r.inverse();
368  }
369  return r;
370  }
371
372  inline BigPrimeField& operator^= (long long int c) {
373  *this = *this ^ c;
374  return *this;
375  }
376
377  inline BigPrimeField& operator^= (const mpz_class& e) {
378  *this = *this ^ e;
379  return *this;
380  }
381
383  return ExpressionTree(new ExprTreeNode(a));
384  }
385
386  inline BigPrimeField operator/ (const BigPrimeField& c) const {
387  BigPrimeField r (*this);
388  return (r /= c);
389  }
390
391  inline BigPrimeField operator/ (long int c) const {
392  BigPrimeField r (*this);
393  BigPrimeField b (c);
394  return (r /= b);
395  }
396
397  inline BigPrimeField operator/ (const mpz_class& c) const {
398  BigPrimeField r (*this);
399  BigPrimeField b (c);
400  return (r /= b);
401  }
402
404  if (c.isZero()) {
405  std::cout << "BPAS: error, dividend is zero from SmallPrimeField."<< std::endl;
406  exit(1);
407  }
408  BigPrimeField inv = c.inverse();
409  *this *= inv;
410  return *this;
411  }
412
413  inline BigPrimeField& operator/= (long int c) {
414  BigPrimeField b (c);
415  return (*this /= b);
416  }
417
418  inline BigPrimeField& operator/= (const mpz_class& c) {
419  BigPrimeField b (c);
420  return (*this /= b);
421  }
422
423  inline BigPrimeField operator% (const BigPrimeField& c) const {
424  return 0;
425  }
426
428  *this = 0;
429  return *this;
430  }
431
432  inline BigPrimeField gcd (const BigPrimeField& other) const {
433  BigPrimeField q (0);
434  BigPrimeField r (0);
435  BigPrimeField c (other);
436  BigPrimeField b (*this);
437  if(b.a < c.a){
438  return c.gcd(b);
439  }
440  while (c.a > 0) {
441  q.a = b.a / c.a;
442  r.a = b.a % c.a;
443  b = c;
444  c = r;
445  }
446  return b;
447  }
448
449  inline BigPrimeField gcd (long int c){
450  BigPrimeField r (*this);
451  BigPrimeField b (c);
452  return r.gcd(b);
453  }
454
455  inline BigPrimeField gcd (const mpz_class& c) const {
456  BigPrimeField r (*this);
457  BigPrimeField b (c);
458  return r.gcd(b);
459  }
460
461  /**
462  * Compute squarefree factorization of *this
463  */
465  std::vector<BigPrimeField> ret;
466  ret.push_back(*this);
467  return ret;
468  }
469
470  /**
471  * Get the euclidean size of *this.
472  */
473  inline BigPrimeField euclideanSize() const {
474  return (*this).number();
475  }
476
477  /**
478  * Perform the eucldiean division of *this and b. Returns the
479  * remainder. If q is not NULL, then returns the quotient in q.
480  */
481  BigPrimeField euclideanDivision(const BigPrimeField& b, BigPrimeField* q = NULL) const;
482
483  /**
484  * Perform the extended euclidean division on *this and b.
485  * Returns the GCD. If s and t are not NULL, returns the bezout coefficients in them.
486  */
487  BigPrimeField extendedEuclidean(const BigPrimeField& b, BigPrimeField* s = NULL, BigPrimeField* t = NULL) const;
488
489  /**
490  * Get the quotient of *this and b.
491  */
492  BigPrimeField quotient(const BigPrimeField& b) const;
493
494  /**
495  * Get the remainder of *this and b.
496  */
497  BigPrimeField remainder(const BigPrimeField& b) const;
498
499  inline BigPrimeField inverse() const {
500  BigPrimeField r(0);
501  mpz_t temp;
502  mpz_init(temp);
503  if (!mpz_invert(temp, a.get_mpz_t(), prime.get_mpz_t()))
504  mpz_set_si(temp, 0);
505  mpz_class temp_class(temp);
506  mpz_clear(temp);
507  r = temp_class;
508  return r;
509  }
510
511 };
512
513 #endif
ExpressionTree convertToExpressionTree() const
Convert this to an expression tree.
Definition: BigPrimeField.hpp:382
BigPrimeField quotient(const BigPrimeField &b) const
Get the quotient of *this and b.
BigPrimeField remainder(const BigPrimeField &b) const
Get the remainder of *this and b.
BigPrimeField euclideanSize() const
Get the euclidean size of *this.
Definition: BigPrimeField.hpp:473
BigPrimeField & operator^=(long long int c)
Exponentiation assignment.
Definition: BigPrimeField.hpp:372
A univariate polynomial over an arbitrary BPASRing represented sparsely.
Definition: BigPrimeField.hpp:21
bool isZero() const
Determine if *this ring element is zero, that is the additive identity.
Definition: BigPrimeField.hpp:132
An arbitrary-precision complex rational number.
Definition: ComplexRationalNumber.hpp:23
void one()
Make *this ring element one.
Definition: BigPrimeField.hpp:144
BigPrimeField operator*(const BigPrimeField &c) const
Multiplication.
Definition: BigPrimeField.hpp:299
BigPrimeField & operator+=(const BigPrimeField &c)
Definition: BigPrimeField.hpp:235
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
BigPrimeField gcd(const BigPrimeField &other) const
Get GCD of *this and other.
Definition: BigPrimeField.hpp:432
A finite field whose prime should be a generalized fermat number.
Definition: GeneralizedFermatPrimeField.hpp:36
BigPrimeField & operator/=(const BigPrimeField &c)
Exact division assignment.
Definition: BigPrimeField.hpp:403
BigPrimeField unitCanonical(BigPrimeField *u=NULL, BigPrimeField *v=NULL) const
Obtain the unit normal (a.k.a canonical associate) of an element.
A prime field whose prime is 32 bits or less.
Definition: SmallPrimeField.hpp:449
BigPrimeField extendedEuclidean(const BigPrimeField &b, BigPrimeField *s=NULL, BigPrimeField *t=NULL) const
Perform the extended euclidean division on *this and b.
A univariate polynomial with Integer coefficients using a dense representation.
Definition: uzpolynomial.h:13
bool operator!=(const BigPrimeField &c) const
Inequality test,.
Definition: BigPrimeField.hpp:190
BigPrimeField operator^(long long int c) const
Exponentiation.
Definition: BigPrimeField.hpp:337
BigPrimeField & operator*=(const BigPrimeField &c)
Multiplication assignment.
Definition: BigPrimeField.hpp:314
bool operator==(const BigPrimeField &c) const
Equality test,.
Definition: BigPrimeField.hpp:162
A univariate polynomial with RationalNumber coefficients represented densely.
Definition: urpolynomial.h:15
A prime field whose prime can be arbitrarily large.
Definition: BigPrimeField.hpp:27
BigPrimeField operator%(const BigPrimeField &c) const
Get the remainder of *this and b;.
Definition: BigPrimeField.hpp:423
BigPrimeField operator-() const
Negation.
Definition: BigPrimeField.hpp:293
BigPrimeField & operator-=(const BigPrimeField &c)
Subtraction assignment.
Definition: BigPrimeField.hpp:271
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
BigPrimeField & operator%=(const BigPrimeField &c)
Assign *this to be the remainder of *this and b.
Definition: BigPrimeField.hpp:427
An arbitrary-precision Integer.
Definition: Integer.hpp:22
bool isOne() const
Determine if *this ring element is one, that is the multiplication identity.
Definition: BigPrimeField.hpp:140
void zero()
Make *this ring element zero.
Definition: BigPrimeField.hpp:136
BigPrimeField operator/(const BigPrimeField &c) const
Exact division.
Definition: BigPrimeField.hpp:386
An arbitrary-precision rational number.
Definition: RationalNumber.hpp:24
BigPrimeField operator+(const BigPrimeField &c) const
Definition: BigPrimeField.hpp:218
virtual mpz_class characteristic()
The characteristic of this ring class.
Definition: BPASRing.hpp:87
Factors< BigPrimeField > squareFree() const
Compute squarefree factorization of *this.
Definition: BigPrimeField.hpp:464
BigPrimeField euclideanDivision(const BigPrimeField &b, BigPrimeField *q=NULL) const
Perform the eucldiean division of *this and b.
BigPrimeField & operator=(const BigPrimeField &c)
Copy assignment.
BigPrimeField inverse() const
Get the inverse of *this.
Definition: BigPrimeField.hpp:499
ExprTreeNode is a single node in the bianry tree of an ExpressionTree.
Definition: ExprTreeNode.hpp:76
An abstract class defining the interface of a prime field.
Definition: BPASFiniteField.hpp:12