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