bool _Format_b(Signal &sig, Formatter *pFormatter,
					const Formatter::Flags &flags, const mpz_class &num)
{
	char *str = nullptr;
	::gmp_asprintf(&str, Formatter::ComposeFlags(flags, "Zb").c_str(), num.get_mpz_t());
	bool rtn = pFormatter->PutString(sig, str);
	::free(str);
	return rtn;
}

int crypto_dh_keypair(
  unsigned char *pk,
  unsigned char *sk
)
{
  randombytes(sk, SECRETKEY_BYTES);
  mpz_class p;
  p = MODULUS;
  mpz_class a;
  static mpz_class base = 2;
  mpz_class result;
  mpz_import(a.get_mpz_t(),SECRETKEY_BYTES,-1,1,0,0,sk);
  mpz_powm(result.get_mpz_t(),base.get_mpz_t(),a.get_mpz_t(),p.get_mpz_t());
  if (mpz_sizeinbase(result.get_mpz_t(),256) > PUBLICKEY_BYTES) return -1;
  long long i;
  for (i = 0;i < PUBLICKEY_BYTES;++i) pk[i] = 0;
  mpz_export(pk,0,-1,1,0,0,result.get_mpz_t());
  return 0;
}

// Check Fermat probable primality test (2-PRP): 2 ** (n-1) = 1 (mod n)
// true: n is probable prime
// false: n is composite; set fractional length in the nLength output
static bool FermatProbablePrimalityTestFast(const mpz_class& n, unsigned int& nLength, CPrimalityTestParams& testParams, bool fFastDiv = false)
{
    // Faster GMP version
    mpz_t& mpzN = testParams.mpzN;
    mpz_t& mpzE = testParams.mpzE;
    mpz_t& mpzR = testParams.mpzR;
    const unsigned int nPrimorialSeq = testParams.nPrimorialSeq;

    mpz_set(mpzN, n.get_mpz_t());
    if (fFastDiv)
    {
        // Fast divisibility tests
        // Starting from the first prime not included in the round primorial
        const unsigned int nBeginSeq = nPrimorialSeq + 1;
        const unsigned int nEndSeq = nBeginSeq + nFastDivPrimes;
        for (unsigned int nPrimeSeq = nBeginSeq; nPrimeSeq < nEndSeq; nPrimeSeq++) {
            if (mpz_divisible_ui_p(mpzN, vPrimes[nPrimeSeq])) {
               return false;
            }
        }
    }

	++fermats;
    mpz_sub_ui(mpzE, mpzN, 1);
    mpz_powm(mpzR, mpzTwo.get_mpz_t(), mpzE, mpzN);
    if (mpz_cmp_ui(mpzR, 1) == 0)
    {
        return true;
    }
    // Failed Fermat test, calculate fractional length
    mpz_sub(mpzE, mpzN, mpzR);
    mpz_mul_2exp(mpzR, mpzE, nFractionalBits);
    mpz_tdiv_q(mpzE, mpzR, mpzN);
    unsigned int nFractionalLength = mpz_get_ui(mpzE);

    if (nFractionalLength >= (1 << nFractionalBits))
	{
		cout << "FermatProbablePrimalityTest() : fractional assert" << endl;
        return false;
	}
    nLength = (nLength & TARGET_LENGTH_MASK) | nFractionalLength;
    return false;
}

/* Pollard Brent factorization method. Pretty much the same as Pollard's rho
 * though uses brent cycle detection. */
mpz_class primes::pollard_brent(mpz_class &n) {
  mpz_class y; // random
  random(y, n);

  unsigned int m = mpz_sizeinbase(n.get_mpz_t(), 2);

  unsigned int brentLimit = m_numBrents;
  if (m > 99) {
    brentLimit = brentLimit >> 3;
  } else if (m > 98) {

mpz_class UnivariatePolynomial::eval(const mpz_class &x) const {
    //TODO: Use Horner's Scheme
    mpz_class ans = 0;
    for (const auto &p : dict_) {
        mpz_class temp;
        mpz_pow_ui(temp.get_mpz_t(), x.get_mpz_t(), p.first);
        ans += p.second * temp;
    }
    return ans;
}

mpz_class sumOfDigits(const mpz_class number, const unsigned radix) {
  assert(radix <= 10);
  assert(number >= 0);
  auto digits = number.get_str(static_cast<int>(radix));

  mpz_class sum(0);
  for (const auto i : digits)
    sum += i - '0';

  return sum;
}

int digit_sum(const mpz_class& bignum) {
    /**Find sum of digits in a bignum
     * Return the sum of the digits in the number
     */
    int sum = 0;
    string bigstr(bignum.get_str());
    for (int i = 0; i < (int)bigstr.size(); ++i)
        // implicit conversion from char to int
        sum += bigstr[i] - '0';
    return sum;
}

bool FermatProbablePrimalityTestFast(const mpz_class &n,
                                     unsigned int& nLength, 
                                     CPrimalityTestParams &testParams,
                                     bool fFastFail)
{
  static const mpz_class mpzTwo = 2;
  mpz_t& mpzE = testParams.mpzE;
  mpz_t& mpzR = testParams.mpzR;
  
  mpz_sub_ui(mpzE, n.get_mpz_t(), 1);
  mpz_powm(mpzR, mpzTwo.get_mpz_t(), mpzE, n.get_mpz_t());
  if (mpz_cmp_ui(mpzR, 1) == 0)
    return true;
  if (fFastFail)
    return false;
  
  // Fermat test failed, calculate chain length (integer and fractional part)
  mpz_sub(mpzE, n.get_mpz_t(), mpzR);
  mpz_mul_2exp(mpzR, mpzE, DifficultyFractionalBits);
  mpz_tdiv_q(mpzE, mpzR, n.get_mpz_t());
  unsigned int fractionalLength = mpz_get_ui(mpzE);
  
  nLength = (nLength & DifficultyChainLengthMask) | fractionalLength;
  return false;
}

void generate_random(mpz_class &z, const mpz_class &n)
{
	if (n == 0)
	{
		z = 0;
		return;
	}
	size_t nbchar = mpz_sizeinbase(n.get_mpz_t(), 2) / (sizeof(unsigned char) * CHAR_BIT) + 1;
	unsigned char *rnd = new unsigned char[nbchar];
	mpz_class mask(2);
	mask <<= mpz_sizeinbase(n.get_mpz_t(), 2);
	mask -= 1;
	do
	{
		_Pragma(STRINGIFY(omp critical))
		{
			fastrandombytes(rnd, nbchar);
		}
		mpz_import (z.get_mpz_t(), nbchar, 1, sizeof(unsigned char), 0, 0, rnd);
		z &= mask;
	}
	while (z >= n);
	delete[] rnd;
}

static bool is_mersenne_prime(mpz_class p)
{
        if( 2 == p )
                return true;
        else
        {
                mpz_class s(4);
                mpz_class div( (mpz_class(1) << p.get_ui()) - 1 );
                for( mpz_class i(3);  i <= p;  ++i )
                {
                        s =  (s * s - mpz_class(2)) % div ;
                }

                return ( s == mpz_class(0) );
        }
}

/**
  * Helper function to convert an mpz_class object into
  * its internal QString representation. Mainly used for
  * debugging.
  */
static QString mpzToString(const mpz_class & val)
{
  char *p = 0;
  // use the gmp provided conversion routine
  gmp_asprintf(&p, "%Zd", val.get_mpz_t());

  // convert it into a QString
  QString result(QString::fromLatin1(p));

  // and free up the resources allocated by gmp_asprintf
  __gmp_freefunc_t freefunc;
  mp_get_memory_functions(NULL, NULL, &freefunc);
  (*freefunc)(p, std::strlen(p) + 1);

  // done
  return result;
}

/* Pollard P-1 fatorization method. Used as a second (fast as limited to primes
 * < 200000) method incase brent fails to gain a factor. */
mpz_class primes::pollard_p1(mpz_class &n) {
  mpz_class c(2);
  for (size_t i = 0; i < m_primes.size(); ++i) {
    mpz_class pp = m_primes[i];
    while (pp < 200000) {
      mpz_powm(c.get_mpz_t(), c.get_mpz_t(), m_primes[i].get_mpz_t(),
               n.get_mpz_t());
      pp *= m_primes[i];
    }
  }
  mpz_class g;
  c--;
  gcd(g, c, n);
  if (g > 1 && g <= n) {
    return g;
  }
  return 1;
}

// Check Fermat probable primality test (2-PRP): 2 ** (n-1) = 1 (mod n)
// true: n is probable prime
// false: n is composite; set fractional length in the nLength output
static bool FermatProbablePrimalityTest(const mpz_class& n, unsigned int& nLength) {
   // Faster GMP version
   mpz_t mpzN;mpz_t mpzE;mpz_t mpzR;
   mpz_init_set(mpzN, n.get_mpz_t());
   mpz_init(mpzE);
   mpz_sub_ui(mpzE, mpzN, 1);
   mpz_init(mpzR);
   mpz_powm(mpzR, mpzTwo.get_mpz_t(), mpzE, mpzN);
   if (mpz_cmp_ui(mpzR, 1) == 0) { mpz_clear(mpzN);mpz_clear(mpzE);mpz_clear(mpzR);return true; }
   // Failed Fermat test, calculate fractional length
   mpz_sub(mpzE, mpzN, mpzR);
   mpz_mul_2exp(mpzR, mpzE, nFractionalBits);
   mpz_tdiv_q(mpzE, mpzR, mpzN);
   unsigned int nFractionalLength = mpz_get_ui(mpzE);
   mpz_clear(mpzN);mpz_clear(mpzE);mpz_clear(mpzR);
   if (nFractionalLength >= (1 << nFractionalBits)) { return error("FermatProbablePrimalityTest() : fractional assert"); }
   nLength = (nLength & TARGET_LENGTH_MASK) | nFractionalLength;
   return false;
}

std::vector<int> Ellipticcurve::getNAF(mpz_class k) {
    //implementation folows pg. 98
    std::vector<int> naf(mpz_sizeinbase(k.get_mpz_t(), 2) + 1);
    int i = 0;
    while (k >= 1){
        if (k % 2 == 1){
            mpz_class temp = (k % 4);
            naf[i] = 2 - (int)temp.get_ui();
            k -= naf[i];

        }
        else{
            naf[i] = 0;
        }
        k /= 2;
        i++;
    }
    return naf;
}

bool trialDivisionChainTest(const PrimeSource &primeSource,
                            mpz_class &N,
                            bool fSophieGermain,
                            unsigned chainLength,
                            unsigned depth)
{
  N += (fSophieGermain ? -1 : 1);
  for (unsigned i = 0; i < chainLength; i++) {
    for (unsigned divIdx = 0; divIdx < depth; divIdx++) { 
      if (mpz_tdiv_ui(N.get_mpz_t(), primeSource[divIdx]) == 0) {
        fprintf(stderr, " * divisor: [%u]%u\n", divIdx, primeSource[divIdx]);
        return false;
      }
    }
    
    N <<= 1;
    N += (fSophieGermain ? 1 : -1);
  }
  
  return true;
}

inline vector<mpz_class> sieve_of_eratosthenes_factorization(const mpz_class& n)
{
  mpz_class remaining = n;
  vector<mpz_class> factors;

  unsigned int limit = pow(2, 26);
  mpz_class tmp;
  mpz_sqrt(tmp.get_mpz_t(), n.get_mpz_t());
  tmp++;
  if (tmp.fits_uint_p() && tmp < limit)
  {
    limit = tmp.get_ui();
  }

  vector<bool> is_prime (limit, true);
  
  is_prime[0] = false;
  is_prime[1] = false;
  for (int i = 2; i < limit; i++)
  {
    if (is_prime[i])
    {
      while (remaining % i == 0)
      {
        remaining /= i;
        factors.push_back(i);
      }

      for (int j = i*i; j < limit; j += i)
      {
        is_prime[j] = false;
      }
    }
  }

  // Don't forget the last factor if one exists.
  if (remaining > 1) factors.push_back(remaining);

  return factors;
}

/**
 * Funkce, pro testovani prvociselnosti (pouzita metoda Solovay--Strassen).
 * @param n Cislo, ktere se ma zkontrolovat na prvocislo.
 * @param iter Pocet iteraci.
 * @return True -- Je pravdepodobne prvocislo, False -- urcite neni.
 */
bool SolovayStrassen(mpz_class n, int iter)
{
   mpz_class n3 = n - 3;
   mpz_class res, exp;
   mpz_class jacobi = 0;

   for(int i = 0; i < iter; i++)
   {
      mpz_class a = rndClass.get_z_range(n3) + 2;
      jacobi = JacobiSymbol(a, n);
      if(jacobi == 0)
         return false;
      exp = (n - 1) / 2;
      mpz_powm(res.get_mpz_t(), a.get_mpz_t(), exp.get_mpz_t(), n.get_mpz_t());
      if(jacobi == -1)
         jacobi += n;
      if(res != jacobi)
         return false;
   }

   return true;
}

list<int> dfa_randomgenerator::randomElementOfK(int m, mpz_class t, mpz_class p)
{{{
	list<int> ret;

	if(m < 2)
		return ret;

	if(p*(m-1) < t)
		return ret;

	mpz_class C, De;

	C = elementOfC(m,t,p);

	if(t == 1) {
		mpz_class Dei, x;

		random_mpz_class(Dei, C);
		Dei += 1;
		De = Dei;
		x = 1;
		while(De > x) {
			De -= x;
			x++;
		};
		ret.push_back(x.get_si());
		return ret;
	} else {
		random_mpz_class(De, C);
		De += 1;
		if((De <= elementOfC(m,t,p-1)) && p > 1) {
			return randomElementOfK(m,t,p-1);
		} else {
			ret = randomElementOfK(m,t-1,p);
			ret.push_back(p.get_si());
			return ret;
		}
	}
}}}

void MathUtils::GetSmoothnessBase(mpz_class& ret_base, mpz_class& N)
{
	mpfr_t f_N, log_N, log_log_N;
	mpz_t base_mpz;
	mpz_init(base_mpz);

	mpfr_init(f_N); mpfr_init(log_N); mpfr_init(log_log_N);

	mpfr_set_z(f_N, N.get_mpz_t(), MPFR_RNDU);		//f_N = N
	mpfr_log(log_N, f_N, MPFR_RNDU); 				//log_N = log(N)
	mpfr_log(log_log_N, log_N, MPFR_RNDU); 			//log_log_N = log(log(N))

	mpfr_mul(f_N, log_N, log_log_N, MPFR_RNDU); 	//f_N = log(N) * log(log(N))
	mpfr_sqrt(f_N, f_N, MPFR_RNDU); 				//f_N = sqrt(f_N)

	mpfr_div_ui(f_N, f_N, 2, MPFR_RNDU);  			//f_N = f_N/2
	mpfr_exp(f_N, f_N, MPFR_RNDU);					//f_N = e^f_N

	mpfr_get_z(base_mpz, f_N, MPFR_RNDU);
	ret_base = mpz_class(base_mpz);

	mpfr_clears(f_N, log_N, log_log_N, NULL);
}

	std::string Signal::valueToVHDL(mpz_class v, bool quot){
		std::string r;

		/* Get base 2 representation */
		r = v.get_str(2);

		/* Some checks */
		if ((int) r.size() > width())	{
			std::ostringstream o;
			o << "Error in " <<  __FILE__ << "@" << __LINE__ << ": value (" << r << ") is larger than signal " << getName();
			throw o.str();
		}

		/* Do padding */
		while ((int)r.size() < width())
			r = "0" + r;

		/* Put apostrophe / quot */
		if (!quot) return r;
		if ((width() > 1) || ( isBus() ))
			return "\"" + r + "\"";
		else
			return "'" + r + "'";
	}