2 #ifndef _SMALL_PRIME_FIELD_H 3 #define _SMALL_PRIME_FIELD_H 5 #include "BPASFiniteField.hpp" 32 static long int prime;
38 static bool isPrimeField;
39 static bool isSmallPrimeField;
40 static bool isComplexField;
69 std::cout <<
"BPAS error, try to cast pointer to Rational Number to pointer to SmallPrimeField" << std::endl;
73 std::cout <<
"BPAS error, try to cast pointer to BigPrimeField to pointer to SmallPrimeField" << std::endl;
77 std::cout <<
"BPAS error, try to cast pointer to GeneralizedFermatPrimeField to pointer to SmallPrimeField" << std::endl;
81 static void setPrime(
long int p){
85 std::ostringstream ss;
87 std::string sp = ss.str();
101 void whichprimefield(){
102 cout <<
"SmallPrimeField" << endl;
105 long long int number(){
111 if ( ((prime - 1) % n != 0)){
112 cout <<
"ERROR: n does not divide prime - 1." << endl;
116 long int q = (prime - 1) / n;
120 long int test = q * n / 2;
124 if ((c^test) == p1) {
131 cout <<
"No primitive root found!"<< endl;
157 inline bool isOne() {
164 inline bool isNegativeOne() {
165 return (a == (prime - 1));
167 inline void negativeOne() {
171 inline int isConstant() {
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;
333 long long int n, b, v;
334 egcd (a, prime, &n, &b, &v, prime);
346 long long int v = prime;
347 long long int x1 = 1;
348 long long int x2 = 0;
356 x1 = (x1 + prime) >> 1;
363 x2 = (x2 + prime) >> 1;
397 std::cout <<
"BPAS: error, dividend is zero from SmallPrimeField."<< std::endl;
454 static long long int prime;
456 static unsigned long long int Pp;
466 static RingProperties properties;
499 template <
class Ring>
511 long long int number()
const;
513 void whichprimefield();
515 static void setPrime(
long long int p){
519 std::ostringstream ss;
521 std::string sp = ss.str();
539 long long int t, A, B, C, D, u, v,q;
542 "xor %%rax,%%rax\n\t" 548 :
"=&d" (v),
"=&a" (q)
581 Pp = (
unsigned long long int)C;
586 "xor %%rax,%%rax\n\t" 592 "movq %%rax,%%rdx\n\t" 594 :
"b"((
unsigned long long int)C)
600 long long int Prime();
607 return SmallPrimeField::findPrimitiveRootofUnity(n);
612 if ( ((prime - 1) % n != 0)){
613 cout <<
"ERROR: n does not divide prime - 1." << endl;
617 long long int q = (prime - 1) / n;
621 long long int test = q * n / 2;
625 if ((c^test) == p1) {
632 cout <<
"No primitive root found!"<< endl;
656 inline bool isNegativeOne() {
660 inline void negativeOne() {
665 inline int isConstant() {
699 a += (a >> 63) & prime;
728 a += (a >> 63) & prime;
762 long long int _a = a;
765 "movq %%rax,%%rsi\n\t" 766 "movq %%rdx,%%rdi\n\t" 769 "add %%rsi,%%rax\n\t" 770 "adc %%rdi,%%rdx\n\t" 772 "mov %%rdx,%%rax\n\t" 775 "addq %%rax,%%rdx\n\t" 777 :
"a"(_a),
"rm"(c.a),
"b"((
unsigned long long int)Pp),
"c"(prime)
784 long long int* pinverse();
788 static long long int Mont(
long long int b,
long long int c);
789 static long long int getRsquare();
794 long long int rsquare = getRsquare();
807 printf(
"Not invertible!\n");
811 long long int* result = r.pinverse();
813 result[0] = Mont(result[0], rsquare);
816 result[0] = Mont(result[0], rsquare);
819 r.a = 1L << (128 - result[1]);
820 result[0] = Mont(result[0], r.a);
865 if ((*this).number() == c.number())
870 inline bool operator== (
long long int k)
const {
873 if (b.number() == r.number()){
882 if ((*this).number() == c.number())
888 inline bool operator!= (
long long int k)
const {
891 if (b.number() == r.number()){
917 std::cout <<
"BPAS: error, dividend is zero from SmallPrimeField."<< std::endl;
933 (*this).a = (*this).a % c.a;
958 std::vector<SmallPrimeField> ret;
959 ret.push_back(*
this);
967 return (*this).number();
994 #endif //montgomery switch 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
Addition.
Definition: SmallPrimeField.hpp:673
bool operator==(const SmallPrimeField &c) const
Equality test,.
Definition: SmallPrimeField.hpp:864
SmallPrimeField extendedEuclidean(const SmallPrimeField &b, SmallPrimeField *s=NULL, SmallPrimeField *t=NULL) const
Perform the extended euclidean division on *this and b.
SmallPrimeField & operator%=(const SmallPrimeField &c)
Assign *this to be the remainder of *this and b.
Definition: SmallPrimeField.hpp:932