Basic Polynomial Algebra Subprograms (BPAS)  v. 1.652
SmallPrimeField.hpp
1
2 #ifndef _SMALL_PRIME_FIELD_H
3 #define _SMALL_PRIME_FIELD_H
4
5 #include "BPASFiniteField.hpp"
6 #include <iostream>
7 #include <sstream>
8 #include <math.h>
9
10 using std::cout;
11 using std::endl;
12
13 //forward declarations
14 class Integer;
15 class RationalNumber;
17 class BigPrimeField;
21 template <class Ring>
23
24 //NOTE the below code is not properly formatted with the corresponding
25 //implementation file. Only the montegomery version is setup properly.
26 #if ( 0 )
27 // simple small prime field using long long int to represent the number
28 class SmallPrimeField : public BPASField{
29
30 private:
31
32  static long int prime;
33  long long int a;
34
35 public:
36
37  static mpz_class characteristic;
38  static bool isPrimeField;
39  static bool isSmallPrimeField;
40  static bool isComplexField;
41
42
43  SmallPrimeField () : a(0) {}
44  SmallPrimeField (long long int _a) {
45  while (_a < 0){
46  _a = _a + prime;
47  }
48  a = _a%prime;
49  }
50  SmallPrimeField (const SmallPrimeField& c) {
51  a = c.a;
52  }
53  //SmallPrimeField (Integer c);
57  //SmallPrimeField (DenseUnivariateIntegerPolynomial c);
58  //SmallPrimeField (DenseUnivariateRationalPolynomial c);
59  //SmallPrimeField (SparseUnivariatePolynomial<Integer> c);
60  //SmallPrimeField (SparseUnivariatePolynomial<RationalNumber> c);
61  //SmallPrimeField (SparseUnivariatePolynomial<ComplexRationalNumber> c);
62  //template <class Ring>
63  //SmallPrimeField (SparseUnivariatePolynomial<Ring> c);
64
65  SmallPrimeField* SPFpointer(SmallPrimeField* b) {
66  return b;
67  }
68  SmallPrimeField* SPFpointer(RationalNumber* a) {
69  std::cout << "BPAS error, try to cast pointer to Rational Number to pointer to SmallPrimeField" << std::endl;
70  exit(1);
71  }
72  SmallPrimeField* SPFpointer(BigPrimeField* a) {
73  std::cout << "BPAS error, try to cast pointer to BigPrimeField to pointer to SmallPrimeField" << std::endl;
74  exit(1);
75  }
77  std::cout << "BPAS error, try to cast pointer to GeneralizedFermatPrimeField to pointer to SmallPrimeField" << std::endl;
78  exit(1);
79  }
80
81  static void setPrime(long int p){
82
83  prime = p;
84  //using string for mpz_class assignment
85  std::ostringstream ss;
86  ss << p;
87  std::string sp = ss.str();
88
89  //mpz_t z;
90  //mpz_init(z
91
92  mpz_class w(sp);
93  // mpz_class w(p);
94  characteristic = w;
95  }
96
97  long int Prime(){
98  return prime;
99  }
100
101  void whichprimefield(){
102  cout << "SmallPrimeField" << endl;
103  }
104
105  long long int number(){
106  return a;
107  }
108
109 //fing the nth primitive root of unity
110  static SmallPrimeField findPrimitiveRootofUnity(long int n){
111  if ( ((prime - 1) % n != 0)){
112  cout << "ERROR: n does not divide prime - 1." << endl;
113  return -1;
114  }
115  bool flag = false;
116  long int q = (prime - 1) / n;
117  SmallPrimeField p1 (prime - 1);
118  SmallPrimeField c;
119  int i = 0;
120  long int test = q * n / 2;
121  srand (time(NULL));
122  while(i < 20){
123  c = rand();
124  if ((c^test) == p1) {
125  flag = true;
126  return (c^q);
127  }
128  i ++;
129  }
130  if (!flag ){
131  cout << "No primitive root found!"<< endl;
132  return 0;
133  }
134  // If no primitive root found
135  }
136
138  if (this != &c) {
139  a = c.a;
140  }
141  return *this;
142  }
143  SmallPrimeField& operator= (long long int k) {
144  while (k < 0){
145  k = k + prime;
146  }
147  a = k%prime;
148  return *this;
149  }
150
151  inline bool isZero() {
152  return (a == 0);
153  }
154  inline void zero() {
155  a = 0;
156  }
157  inline bool isOne() {
158  return (a == 1);
159  }
160  inline void one() {
161  a = 1;
162  }
163
164  inline bool isNegativeOne() {
165  return (a == (prime - 1));
166  }
167  inline void negativeOne() {
168  a = prime - 1;
169  }
170
171  inline int isConstant() {
172  if (a >= 0)
173  return 1;
174  else { return -1; }
175  }
176
177
178  inline SmallPrimeField gcd (SmallPrimeField c) {
179  SmallPrimeField q (0);
180  SmallPrimeField r (0);
181  SmallPrimeField b (*this);
182  if(b.a < c.a){
183  return c.gcd(b);
184  }
185  while (c.a > 0) {
186  q.a = b.a / c.a;
187  r.a = b.a % c.a;
188  b = c;
189  c = r;
190  }
191  return b;
192  }
193  inline SmallPrimeField gcd (long long int c){
194  SmallPrimeField b (c);
195  SmallPrimeField r (*this);
196  return r.gcd(b);
197  }
198
199  inline bool operator== (SmallPrimeField& c) {
200  if (a == c.a)
201  return 1;
202  else { return 0; }
203  }
204
205  inline bool operator== (long long int k){
206  SmallPrimeField r (*this);
207  SmallPrimeField b (k);
208  if (b == r){
209  return 1;
210  }
211  else {
212  return 0;
213  }
214  }
215  inline bool operator!= (SmallPrimeField& c) {
216  if (a == c.a)
217  return 0;
218  else { return 1; }
219  }
220
221  inline bool operator!= (long long int k){
222  SmallPrimeField r (*this);
223  SmallPrimeField b (k);
224  if (b == r){
225  return 0;
226  }
227  else {
228  return 1;
229  }
230  }
231
232
234  SmallPrimeField r (*this);
235  return (r += c);
236  }
237  inline SmallPrimeField operator+ (long long int& c) {
238  SmallPrimeField r (*this);
239  SmallPrimeField b (c);
240  return (r += b);
241  }
242  inline SmallPrimeField operator+ (int& c) {
243  SmallPrimeField r (*this);
244  SmallPrimeField b (c);
245  return (r += b);
246  }
247  inline SmallPrimeField operator+= (long long int& c) {
248  SmallPrimeField r (*this);
249  SmallPrimeField b (c);
250  return (r += b);
251  }
252  inline SmallPrimeField& operator+= (SmallPrimeField c) {
253  a = (a + c.a)%prime;
254  return *this;
255  }
256
258  SmallPrimeField r (*this);
259  return (r -= c);
260  }
261  inline SmallPrimeField operator- (long long int& c) {
262  SmallPrimeField r (*this);
263  SmallPrimeField b (c);
264  return (r -= b);
265  }
266  inline SmallPrimeField operator-= (long long int& c) {
267  SmallPrimeField r (*this);
268  SmallPrimeField b (c);
269  return (r -= b);
270  }
271  inline SmallPrimeField& operator-= (SmallPrimeField c) {
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  inline SmallPrimeField operator- () {
281  a = prime - a;
282  return *this;
283  }
285  SmallPrimeField r (*this);
286  return (r *= c);
287  }
288  inline SmallPrimeField operator* (long long int c) {
289  SmallPrimeField r (*this);
290  return (r *= c);
291  }
292
294  a = (a * c.a)%prime;
295  return *this;
296  }
297  inline SmallPrimeField operator*= (long long int& c) {
298  a = a * c;
299  SmallPrimeField r (a);
300  return r;
301  }
302  void egcd (long long int x, long long int y, long long int *ao, long long int *bo, long long int *vo, long long int P){
303  long long int t, A, B, C, D, u, v, q;
304
305  u = y;
306  v = x;
307  A = 1;
308  B = 0;
309  C = 0;
310  D = 1;
311
312  do
313  {
314  q = u / v;
315  t = u;
316  u = v;
317  v = t - q * v;
318  t = A;
319  A = B;
320  B = t - q * B;
321  t = C;
322  C = D;
323  D = t - q * D;
324  }
325  while (v != 0);
326
327  *ao = A;
328  *bo = C;
329  *vo = u;
330  }
331
332  inline SmallPrimeField inverse2(){
333  long long int n, b, v;
334  egcd (a, prime, &n, &b, &v, prime);
335  if (b < 0)
336  b += prime;
337  SmallPrimeField r (b);
338  return r;
339  }
340
341
342 //Binary inverse
343
345  long long int u = a;
346  long long int v = prime;
347  long long int x1 = 1;
348  long long int x2 = 0;
349  SmallPrimeField r(0);
350  while(u!=1 && v!=1){
351  while (u%2 == 0){
352  u = u >> 1;
353  if(x1%2==0)
354  x1 = x1 >> 1;
355  else
356  x1 = (x1 + prime) >> 1;
357  }
358  while (v%2 ==0){
359  v = v >> 1;
360  if(x2%2 == 0)
361  x2 = x2 >> 1;
362  else
363  x2 = (x2 + prime) >> 1;
364  }
365  if(u>=v){
366  u = u - v;
367  x1 = x1 - x2;
368  }
369  else{
370  v = v - u;
371  x2 = x2 - x1;
372  }
373  }
374  if(u == 1)
375  r = x1;
376  else
377  r = x2;
378  return r;
379  }
380
382  SmallPrimeField r (*this);
383  return (r /= c);
384  }
385  inline SmallPrimeField operator/ (long long int c) {
386  SmallPrimeField r (*this);
387  SmallPrimeField b (c);
388  return (r /= b);
389  }
390  inline SmallPrimeField operator/= (long long int c) {
391  SmallPrimeField r (*this);
392  SmallPrimeField b (c);
393  return (r /= b);
394  }
396  if (c.isZero()) {
397  std::cout << "BPAS: error, dividend is zero from SmallPrimeField."<< std::endl;
398  exit(1);
399  }
400  c=c.inverse();
401  SmallPrimeField r (*this);
402  r*=c;
403  a = r.a;
404  return *this;
405  }
406
407  inline SmallPrimeField operator^ (long long int e){
408  SmallPrimeField r;
409  if (isZero() || isOne() || e == 1)
410  r = *this;
411  else if (e == 2) {
412  r = *this * *this;
413  }
414  else if (e > 2) {
415  SmallPrimeField x (*this);
416  r.one();
417
418  while (e != 0) {
419  if (e % 2)
420  r *= x;
421  x = x * x;
422  e >>= 1;
423  }
424  }
425  else if (e == 0) {
426  r.one();
427  }
428  else {
429  r = *this ^ (-e);
430  r=r.inverse();
431  }
432  return r;
433  }
434
435
436  inline friend std::ostream& operator<< (std::ostream &out, SmallPrimeField c){
437  out << c.a;
438  return out;
439  }
440 };
441
442
443 #else
444
445 /**
446  * A prime field whose prime is 32 bits or less. Elements of this field
447  * are encoded using montgomery trick.
448  */
449 class SmallPrimeField : public BPASFiniteField<SmallPrimeField> {
450
451 private:
452
453  long long int a;
454  static long long int prime;
455  //static long long int R;
456  static unsigned long long int Pp;
457
458 //R = 2^Wt;
459 // static long long int Rp;
460
461 //Pp = -p^-1 mod R;
462 // static long long int N;
463
464 public:
465
466  static RingProperties properties;
467  static mpz_class characteristic;
468 // static bool isPrimeField;
469 // static bool isSmallPrimeField;
470 // static bool isComplexField;
471
472  SmallPrimeField ();
473
474 // using aR mod p to represent the number
475  SmallPrimeField (long long int _a);
476
477  SmallPrimeField (const SmallPrimeField& c);
478
479  explicit SmallPrimeField (const Integer& c);
480
481  explicit SmallPrimeField (const RationalNumber& c);
482
483  explicit SmallPrimeField (const ComplexRationalNumber& c);
484
485  explicit SmallPrimeField (const BigPrimeField& c);
486
487  explicit SmallPrimeField (const GeneralizedFermatPrimeField& c);
488
490
492
494
496
498
499  template <class Ring>
501
502  SmallPrimeField* SPFpointer(SmallPrimeField* b);
503
504  SmallPrimeField* SPFpointer(RationalNumber* a);
505
506  SmallPrimeField* SPFpointer(BigPrimeField* a);
507
509
510 // return the actual number
511  long long int number() const;
512
513  void whichprimefield();
514
515  static void setPrime(long long int p){
516
517  prime = p;
518 //using string for mpz_class assignment
519  std::ostringstream ss;
520  ss << p;
521  std::string sp = ss.str();
522
523 //mpz_t z;
524 //mpz_init(z
525
526  mpz_class w(sp);
527 // mpz_class w(p);
529
530  // long long int p1 = R - prime;
531
532  // for(int i = 0; i < R; i ++){
533  // if ((i * p1)%R == 1){
534  // Pp = i;
535  // break;
536  // }
537  // }
538 //cout << Pp << endl;
539  long long int t, A, B, C, D, u, v,q;
540  __asm__( //compute the first step of egcd where R = q*prime + v
541  // "movq %%rax,%%rsi\n\t"
542  "xor %%rax,%%rax\n\t"
543  "movq \$1,%%rdx\n\t"
544  "divq %2\n\t"
545  // "movq %%rsi,%%rax\n\t"
546  // "movq %%rdx,%0\n\t"
547  // "movq %%rax,%1\n\t"
548  : "=&d" (v),"=&a" (q)
549  : "b"(prime)
550  :"rsi","rdi");
551  A = 1;
552  B = 0;
553  C = 0;
554  D = 1;
555  // q = R/prime;
556  u = prime;
557  //v = R - R mod prime;
558  t = A;
559  A = B;
560  B = t - q * B;
561  t = C;
562  C = D;
563  D = t - q * D;
564
565  while (v != 0){
566  q = u / v;
567  t = u;
568  u = v;
569  v = t - q * v;
570  t = A;
571  A = B;
572  B = t - q * B;
573  t = C;
574  C = D;
575  D = t - q * D;
576  // printf("%llu,%llu\n",A,C);
577  }
578  //unsigned long long int res;
579  if(C < 0){
580  C = 0-C;
581  Pp = (unsigned long long int)C;
582  }
583  else{
584  __asm__( //compute -C mod R;
585  // "movq %%rax,%%rsi\n\t"
586  "xor %%rax,%%rax\n\t"
587  "movq \$1,%%rdx\n\t"
588  "sub %1,%%rax\n\t"
589  "sbb \$0,%%rdx\n\t"
590  // "movq %%rsi,%%rax\n\t"
591  // "movq %%rdx,%0\n\t"
592  "movq %%rax,%%rdx\n\t"
593  : "=&d" (Pp)
594  : "b"((unsigned long long int)C)
595  :"rsi","rdi");
596  }
597
598  }
599
600  long long int Prime();
601
603
604  SmallPrimeField& operator= (long long int k);
605
606  SmallPrimeField findPrimitiveRootOfUnity(long int n) const {
607  return SmallPrimeField::findPrimitiveRootofUnity(n);
608  }
609
610
611  static SmallPrimeField findPrimitiveRootofUnity(long long int n){
612  if ( ((prime - 1) % n != 0)){
613  cout << "ERROR: n does not divide prime - 1." << endl;
614  return -1;
615  }
616  bool flag = false;
617  long long int q = (prime - 1) / n;
618  SmallPrimeField p1 (prime - 1);
619  SmallPrimeField c;
620  int i = 0;
621  long long int test = q * n / 2;
622  srand (time(NULL));
623  while(i < 20){
624  c = rand();
625  if ((c^test) == p1) {
626  flag = true;
627  return (c^q);
628  }
629  i ++;
630  }
631  if (!flag ){
632  cout << "No primitive root found!"<< endl;
633  return 0;
634  }
635 // If no primitive root found
636  }
637
638  inline bool isZero() const {
639  return (a == 0);
640  }
641
642  inline void zero() {
643  a = 0;
644  }
645
646  inline bool isOne() const {
647  SmallPrimeField b(1);
648  return (a == b.a);
649  }
650
651  inline void one() {
652  SmallPrimeField b(1);
653  a = b.a;// R % prime;
654  }
655
656  inline bool isNegativeOne() {
657  SmallPrimeField b(-1);
658  return (a == b.a);
659  }
660  inline void negativeOne() {
661  SmallPrimeField b(-1);
662  a = b.a;
663  }
664
665  inline int isConstant() {
666  if (a >= 0)
667  return 1;
668  else { return -1; }
669  }
670
671  SmallPrimeField unitCanonical(SmallPrimeField* u = NULL, SmallPrimeField* v = NULL) const ;
672
673  inline SmallPrimeField operator+ (const SmallPrimeField& c) const {
674  SmallPrimeField r (*this);
675  return (r += c);
676  }
677
678  inline SmallPrimeField operator+ (const long long int& c) const {
679  SmallPrimeField r (*this);
680  SmallPrimeField b (c);
681  return (r += b);
682  }
683  inline SmallPrimeField operator+ (const int& c) const {
684  SmallPrimeField r (*this);
685  SmallPrimeField b (c);
686  return (r += b);
687  }
688  inline SmallPrimeField operator+= (const long long int& c) {
689  SmallPrimeField r (*this);
690  SmallPrimeField b (c);
691  return (r += b);
692  }
693
694  inline SmallPrimeField& operator+= (const SmallPrimeField& c) {
695  //a = (a + c.a)%prime;
696  //return *this;
697  a = a + c.a;
698  a -= prime;
699  a += (a >> 63) & prime;
700  return *this;
701  }
702
703  inline SmallPrimeField operator- (const SmallPrimeField& c) const {
704  SmallPrimeField r (*this);
705  return (r -= c);
706  }
707
708  inline SmallPrimeField operator- (const long long int& c) const {
709  SmallPrimeField r (*this);
710  SmallPrimeField b (c);
711  return (r -= b);
712  }
713  inline SmallPrimeField operator-= (const long long int& c) {
714  SmallPrimeField r (*this);
715  SmallPrimeField b (c);
716  return (r -= b);
717  }
718
719  inline SmallPrimeField& operator-= (const SmallPrimeField& c) {
720  // if ((a - c.a)<0){
721  // a = prime+(a - c.a);
722  // }
723  // else{
724  // a = a - c.a;
725  // }
726  // return *this;
727  a = a - c.a;
728  a += (a >> 63) & prime;
729  return *this;
730  }
731  inline SmallPrimeField operator- () const {
732  SmallPrimeField ret (*this);
733  ret.a = prime - a;
734  return ret;
735  }
736
737  inline SmallPrimeField operator* (const SmallPrimeField& c) const {
738  SmallPrimeField r (*this);
739
740  r*=c;
741 //cout << r << endl;
742  return r;
743  }
744
745  inline SmallPrimeField operator* (long long int c) const {
746  SmallPrimeField r (*this);
747  SmallPrimeField b(c);
748  return (r *= b);
749  }
750 // Mont(a,b) = ab/R mod p
751 // Mont(aR,bR) = abR mod p
753  // long long int x = (c.a * a);
754  // long long int w = x*Pp;
755  // long long int y = x + prime*(w&(R-1));
756  // long long int z = y>>32 ;
757  // if(z >= prime){
758  // z = z - prime;
759  // }
760  // a = z;
761  // return *this;
762  long long int _a = a;
763  __asm__(
764  "mulq %2\n\t"
765  "movq %%rax,%%rsi\n\t"
766  "movq %%rdx,%%rdi\n\t"
767  "imulq %3,%%rax\n\t"
768  "mulq %4\n\t"
771  "subq %4,%%rdx\n\t"
772  "mov %%rdx,%%rax\n\t"
773  "sar \$63,%%rax\n\t"
774  "andq %4,%%rax\n\t"
776  : "=&d" (_a)
777  : "a"(_a),"rm"(c.a),"b"((unsigned long long int)Pp),"c"(prime)
778  :"rsi","rdi");
779  a = _a;
780  return *this;
781  }
782
783 //partial Montgomery inversion
784  long long int* pinverse();
785 // long long int MontMul(long long int a, long long int b);
786
787 //return bc/R mod p;
788  static long long int Mont(long long int b, long long int c);
789  static long long int getRsquare();
790 //Montgomery inversion
791  inline SmallPrimeField inverse() const {
792  SmallPrimeField r(*this);
793  // SmallPrimeField rsquare(R);
794  long long int rsquare = getRsquare();
795  // long long int* result = r.pinverse();
796  // if(result[0] < 32){
797  // result[0] = Mont(result[0], rsquare.a);
798  // result[1] += 32;
799  // }
800  // result[0] = Mont(result[0], rsquare.a);
801  // result[0] = Mont(result[0], pow(2,64-result[1]));
802  // r.a = result[0];
803  // return r;
804
805  if (r.a == 0)
806  {
807  printf("Not invertible!\n");
808  return 0;
809  }
810  // long long int rsquare = getRsquare(prime);
811  long long int* result = r.pinverse();
812  if(result[1] < 64){
813  result[0] = Mont(result[0], rsquare);
814  result[1] += 64;
815  }
816  result[0] = Mont(result[0], rsquare);
817  long long int tmp;
818  if(result[1] != 64){
819  r.a = 1L << (128 - result[1]);
820  result[0] = Mont(result[0], r.a);
821  }
822  r.a = result[0];
823  free(result);
824  return r;
825  }
826
827 //Binary inverse
828  SmallPrimeField inverse2();
829
830  inline SmallPrimeField operator^ (long long int e) const {
831  SmallPrimeField r;
832  if (isZero() || isOne() || e == 1)
833  r = *this;
834  else if (e == 2) {
835  r = *this * *this;
836  }
837  else if (e > 2) {
838  SmallPrimeField x (*this);
839  r.one();
840
841  while (e != 0) {
842  if (e % 2)
843  r *= x;
844  x = x * x;
845  e >>= 1;
846  }
847  }
848  else if (e == 0) {
849  r.one();
850  }
851  else {
852  r = *this ^ (-e);
853  r=r.inverse();
854  }
855  return r;
856
857  }
858
859  inline SmallPrimeField& operator^= (long long int e) {
860  *this = *this ^ e;
861  return *this;
862  }
863
864  inline bool operator== (const SmallPrimeField& c) const {
865  if ((*this).number() == c.number())
866  return 1;
867  else { return 0; }
868  }
869
870  inline bool operator== (long long int k) const {
871  SmallPrimeField r (*this);
872  SmallPrimeField b (k);
873  if (b.number() == r.number()){
874  return 1;
875  }
876  else {
877  return 0;
878  }
879  }
880
881  inline bool operator!= (const SmallPrimeField& c) const {
882  if ((*this).number() == c.number())
883  return 0;
884  else { return 1; }
885  }
886
887
888  inline bool operator!= (long long int k) const {
889  SmallPrimeField r (*this);
890  SmallPrimeField b (k);
891  if (b.number() == r.number()){
892  return 0;
893  }
894  else {
895  return 1;
896  }
897  }
898
900  return ExpressionTree(new ExprTreeNode(this->number()));
901  }
902
903  inline SmallPrimeField operator/ (const SmallPrimeField& c) const {
904  SmallPrimeField r (*this);
905  r /= c;
906  return r;
907  }
908
909  inline SmallPrimeField operator/ (long long int c) const {
910  SmallPrimeField r (*this);
911  SmallPrimeField b(c);
912  return (r /= b);
913  }
914
916  if (c.isZero()) {
917  std::cout << "BPAS: error, dividend is zero from SmallPrimeField."<< std::endl;
918  exit(1);
919  }
920  //cout << "division" << endl;
921  SmallPrimeField inv = c.inverse();
922  SmallPrimeField r (*this);
923  r *= inv;
924  (*this).a = r.a;
925  return *this;
926  }
927
928  inline SmallPrimeField operator% (const SmallPrimeField& c) const {
929  return *this % c;
930  }
931
933  (*this).a = (*this).a % c.a;
934  return *this;
935  }
936
937  inline SmallPrimeField gcd (const SmallPrimeField& other) const {
938  SmallPrimeField q (0);
939  SmallPrimeField r (0);
940  SmallPrimeField b (*this);
941  SmallPrimeField c (other);
942  if(b.a < c.a){
943  return c.gcd(b);
944  }
945  while (c.a > 0) {
946  q.a = b.a / c.a;
947  r.a = b.a % c.a;
948  b = c;
949  c = r;
950  }
951  return b;
952  }
953
954  /**
955  * Compute squarefree factorization of *this
956  */
958  std::vector<SmallPrimeField> ret;
959  ret.push_back(*this);
960  return ret;
961  }
962
963  /**
964  * Get the euclidean size of *this.
965  */
967  return (*this).number();
968  }
969
970  /**
971  * Perform the eucldiean division of *this and b. Returns the
972  * remainder. If q is not NULL, then returns the quotient in q.
973  */
975
976  /**
977  * Perform the extended euclidean division on *this and b.
978  * Returns the GCD. If s and t are not NULL, returns the bezout coefficients in them.
979  */
981
982  /**
983  * Get the quotient of *this and b.
984  */
985  SmallPrimeField quotient(const SmallPrimeField& b) const;
986
987  /**
988  * Get the remainder of *this and b.
989  */
990  SmallPrimeField remainder(const SmallPrimeField& b) const;
991
992 };
993
994 #endif //montgomery switch
995
996 #endif //include guard
Factors< SmallPrimeField > squareFree() const
Compute squarefree factorization of *this.
Definition: SmallPrimeField.hpp:957
SmallPrimeField & operator=(const SmallPrimeField &c)
Copy assignment.
A univariate polynomial over an arbitrary BPASRing represented sparsely.
Definition: BigPrimeField.hpp:21
SmallPrimeField operator*(const SmallPrimeField &c) const
Multiplication.
Definition: SmallPrimeField.hpp:737
bool isOne() const
Determine if *this ring element is one, that is the multiplication identity.
Definition: SmallPrimeField.hpp:646
SmallPrimeField operator/(const SmallPrimeField &c) const
Exact division.
Definition: SmallPrimeField.hpp:903
SmallPrimeField inverse() const
Get the inverse of *this.
Definition: SmallPrimeField.hpp:791
SmallPrimeField & operator*=(const SmallPrimeField &c)
Multiplication assignment.
Definition: SmallPrimeField.hpp:752
void zero()
Make *this ring element zero.
Definition: SmallPrimeField.hpp:642
An arbitrary-precision complex rational number.
Definition: ComplexRationalNumber.hpp:23
SmallPrimeField operator^(long long int e) const
Exponentiation.
Definition: SmallPrimeField.hpp:830
SmallPrimeField euclideanDivision(const SmallPrimeField &b, SmallPrimeField *q=NULL) const
Perform the eucldiean division of *this and b.
SmallPrimeField operator-() const
Negation.
Definition: SmallPrimeField.hpp:731
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
A finite field whose prime should be a generalized fermat number.
Definition: GeneralizedFermatPrimeField.hpp:36
friend std::ostream & operator<<(std::ostream &ostream, const SmallPrimeField &d)
Output operator.
Definition: BPASRing.hpp:201
ExpressionTree convertToExpressionTree() const
Convert this to an expression tree.
Definition: SmallPrimeField.hpp:899
SmallPrimeField euclideanSize() const
Get the euclidean size of *this.
Definition: SmallPrimeField.hpp:966
void one()
Make *this ring element one.
Definition: SmallPrimeField.hpp:651
A prime field whose prime is 32 bits or less.
Definition: SmallPrimeField.hpp:449
A univariate polynomial with Integer coefficients using a dense representation.
Definition: uzpolynomial.h:13
SmallPrimeField gcd(const SmallPrimeField &other) const
Get GCD of *this and other.
Definition: SmallPrimeField.hpp:937
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
bool isZero() const
Determine if *this ring element is zero, that is the additive identity.
Definition: SmallPrimeField.hpp:638
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
bool operator!=(const SmallPrimeField &c) const
Inequality test,.
Definition: SmallPrimeField.hpp:881
SmallPrimeField operator%(const SmallPrimeField &c) const
Get the remainder of *this and b;.
Definition: SmallPrimeField.hpp:928
An arbitrary-precision Integer.
Definition: Integer.hpp:22
SmallPrimeField & operator^=(long long int e)
Exponentiation assignment.
Definition: SmallPrimeField.hpp:859
An arbitrary-precision rational number.
Definition: RationalNumber.hpp:24
virtual mpz_class characteristic()
The characteristic of this ring class.
Definition: BPASRing.hpp:87
SmallPrimeField unitCanonical(SmallPrimeField *u=NULL, SmallPrimeField *v=NULL) const
Obtain the unit normal (a.k.a canonical associate) of an element.
SmallPrimeField remainder(const SmallPrimeField &b) const
Get the remainder of *this and b.
An abstract class defining the interface of a field.
Definition: BPASField.hpp:11
SmallPrimeField & operator/=(const SmallPrimeField &c)
Exact division assignment.
Definition: SmallPrimeField.hpp:915
SmallPrimeField quotient(const SmallPrimeField &b) const
Get the quotient of *this and b.
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
SmallPrimeField operator+(const SmallPrimeField &c) const