2 #ifndef _GENERALIZED_FERMAT_PRIMT_FIELD_H_ 3 #define _GENERALIZED_FERMAT_PRIMT_FIELD_H_ 5 #include "BPASFiniteField.hpp" 8 typedef unsigned long long int usfixn64;
11 #define ULMAX 18446744073709551615ULL 12 #define SQRTR 3037000502 13 #define RC 9223372019674906624ULL 39 static mpz_class& prime;
45 static RingProperties properties;
90 static void setPrime (mpz_class p,usfixn64 R,
int K){
97 void setX (mpz_class a);
99 mpz_class Prime()
const;
101 mpz_class number()
const;
105 static mpz_class power(mpz_class xi, mpz_class yi) {
114 res = (res*xi) % prime;
120 xi = (xi*xi) % prime;
126 return GeneralizedFermatPrimeField::findPrimitiveRootofUnity(n);
129 static mpz_class findPrimitiveRootofUnity_plain(mpz_class n){
130 if ( ((prime - 1) % n != 0)){
131 cout <<
"ERROR: n does not divide prime - 1." << endl;
135 mpz_class q = (prime - 1) / n;
136 mpz_class p1 = prime - 1;
139 mpz_class test = q * n / 2;
148 if (power(c,test) == p1) {
156 cout <<
"No primitive root found!"<< endl;
165 throw std::invalid_argument(
"findPrimitiveRootofUnity error: N is less than 2k");
167 mpz_class g = findPrimitiveRootofUnity_plain(n);
168 mpz_class n2k = n / (2 * k);
169 mpz_class a = power(g, n2k);
171 std::stringstream str;
173 mpz_class r_mpz (str.str());
190 for (
int i = 0; i < k; i++) {
199 memset(x, 0x00, (k) *
sizeof(usfixn64));
203 for (
int i = k - 1;i > 0; i --){
216 for (
int i = k - 1;i > 0; i --){
223 inline bool isNegativeOne()
const {
224 for (
int i = 0; i < (k - 1);i ++){
235 inline void negativeOne() {
236 for (
int i = 0; i < (k - 1); i ++){
242 inline int isConstant()
const {
247 for (
int i = 0; i < k; i++) {
248 if (x[i] != c.x[i]) {
256 inline bool operator== (
const mpz_class& c)
const {
258 for (
int i = 0; i < k; i++) {
259 if (x[i] != b.x[i]) {
268 for (
int i = 0; i < k; i++) {
269 if (x[i] != c.x[i]) {
276 inline bool operator!= (
const mpz_class& c)
const {
278 for (
int i = 0; i < k; i++) {
279 if (x[i] != b.x[i]) {
363 void smallAdd2 (usfixn64 *xm, usfixn64* ym,
short & c);
365 void oneShiftRight (usfixn64 * xs);
368 void mulLong_2 (usfixn64 x, usfixn64 y, usfixn64 &s0,usfixn64 &s1, usfixn64 &s2);
371 void mulLong_3 (usfixn64
const &x, usfixn64
const &y, usfixn64 &s0,
372 usfixn64 &s1, usfixn64 &s2);
374 void multiplication (usfixn64* __restrict__ xs,
const usfixn64* __restrict__ ys,
375 usfixn64 permutationStride, usfixn64* lVector,
376 usfixn64 *hVector, usfixn64* cVector,
377 usfixn64* lVectorSub,
378 usfixn64 *hVectorSub, usfixn64* cVectorSub );
380 void multiplication_step2 (usfixn64* __restrict__ xs, usfixn64 permutationStride,
381 usfixn64* __restrict__ lVector,
382 usfixn64 * __restrict__ hVector,
383 usfixn64* __restrict__ cVector);
416 mpz_class xi = number();
417 mpz_class yi = c.number();
432 void egcd (
const mpz_class& x,
const mpz_class& y, mpz_class *ao, mpz_class *bo, mpz_class *vo, mpz_class P);
435 mpz_class a, n, b, v;
438 egcd (a, prime, &n, &b, &v, prime);
447 mpz_class b (std::to_string(c), 10);
514 std::cout <<
"BPAS: error, dividend is zero from GeneralizedFermatPrimeField."<< std::endl;
544 std::cerr <<
"GeneralizedFermatPrimeField::gcd NOT YET IMPLEMENTED" << std::endl;
553 std::vector<GeneralizedFermatPrimeField> ret;
554 ret.push_back(*
this);
562 return (*this).number();
GeneralizedFermatPrimeField & operator^=(long long int c)
Exponentiation assignment.
Definition: GeneralizedFermatPrimeField.hpp:481
GeneralizedFermatPrimeField remainder(const GeneralizedFermatPrimeField &b) const
Get the remainder of *this and b.
A univariate polynomial over an arbitrary BPASRing represented sparsely.
Definition: BigPrimeField.hpp:21
GeneralizedFermatPrimeField operator+(const GeneralizedFermatPrimeField &c) const
Addition.
Definition: GeneralizedFermatPrimeField.hpp:287
An arbitrary-precision complex rational number.
Definition: ComplexRationalNumber.hpp:23
ExpressionTree convertToExpressionTree() const
Convert this to an expression tree.
Definition: GeneralizedFermatPrimeField.hpp:491
GeneralizedFermatPrimeField operator-() const
Negation.
Definition: GeneralizedFermatPrimeField.hpp:357
An ExpressionTree encompasses various forms of data that can be expressed generically as a binary tre...
Definition: ExpressionTree.hpp:17
GeneralizedFermatPrimeField gcd(const GeneralizedFermatPrimeField &a) const
Get GCD of *this and other.
Definition: GeneralizedFermatPrimeField.hpp:543
void zero()
Make *this ring element zero.
Definition: GeneralizedFermatPrimeField.hpp:198
A finite field whose prime should be a generalized fermat number.
Definition: GeneralizedFermatPrimeField.hpp:36
GeneralizedFermatPrimeField quotient(const GeneralizedFermatPrimeField &b) const
Get the quotient of *this and b.
GeneralizedFermatPrimeField operator%(const GeneralizedFermatPrimeField &c) const
Get the remainder of *this and b;.
Definition: GeneralizedFermatPrimeField.hpp:534
GeneralizedFermatPrimeField & operator%=(const GeneralizedFermatPrimeField &c)
Assign *this to be the remainder of *this and b.
Definition: GeneralizedFermatPrimeField.hpp:538
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
GeneralizedFermatPrimeField operator^(long long int c) const
Exponentiation.
Definition: GeneralizedFermatPrimeField.hpp:445
bool operator!=(const GeneralizedFermatPrimeField &c) const
Inequality test,.
Definition: GeneralizedFermatPrimeField.hpp:267
bool isZero() const
Determine if *this ring element is zero, that is the additive identity.
Definition: GeneralizedFermatPrimeField.hpp:189
A univariate polynomial with RationalNumber coefficients represented densely.
Definition: urpolynomial.h:15
GeneralizedFermatPrimeField & operator=(const GeneralizedFermatPrimeField &c)
Copy assignment.
A prime field whose prime can be arbitrarily large.
Definition: BigPrimeField.hpp:27
A simple data structure for encapsulating a collection of Factor elements.
Definition: Factors.hpp:95
An arbitrary-precision Integer.
Definition: Integer.hpp:22
GeneralizedFermatPrimeField extendedEuclidean(const GeneralizedFermatPrimeField &b, GeneralizedFermatPrimeField *s=NULL, GeneralizedFermatPrimeField *t=NULL) const
Perform the extended euclidean division on *this and b.
bool operator==(const GeneralizedFermatPrimeField &c) const
Equality test,.
Definition: GeneralizedFermatPrimeField.hpp:246
GeneralizedFermatPrimeField inverse() const
Get the inverse of *this.
GeneralizedFermatPrimeField operator*(const GeneralizedFermatPrimeField &c) const
Multiplication.
Definition: GeneralizedFermatPrimeField.hpp:385
GeneralizedFermatPrimeField & operator/=(const GeneralizedFermatPrimeField &c)
Exact division assignment.
Definition: GeneralizedFermatPrimeField.hpp:512
GeneralizedFermatPrimeField unitCanonical(GeneralizedFermatPrimeField *u=NULL, GeneralizedFermatPrimeField *v=NULL) const
Obtain the unit normal (a.k.a canonical associate) of an element.
An arbitrary-precision rational number.
Definition: RationalNumber.hpp:24
virtual mpz_class characteristic()
The characteristic of this ring class.
Definition: BPASRing.hpp:87
Factors< GeneralizedFermatPrimeField > squareFree() const
Compute squarefree factorization of *this.
Definition: GeneralizedFermatPrimeField.hpp:552
bool isOne() const
Determine if *this ring element is one, that is the multiplication identity.
Definition: GeneralizedFermatPrimeField.hpp:202
GeneralizedFermatPrimeField euclideanSize() const
Get the euclidean size of *this.
Definition: GeneralizedFermatPrimeField.hpp:561
GeneralizedFermatPrimeField euclideanDivision(const GeneralizedFermatPrimeField &b, GeneralizedFermatPrimeField *q=NULL) const
Perform the eucldiean division 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
GeneralizedFermatPrimeField operator/(const GeneralizedFermatPrimeField &c) const
Exact division.
Definition: GeneralizedFermatPrimeField.hpp:495
void one()
Make *this ring element one.
Definition: GeneralizedFermatPrimeField.hpp:215