5#ifndef CRYPTOPP_IMPORTS
22const unsigned int maxPrimeTableSize = 3511;
23const word s_lastSmallPrime = 32719;
27 extern const word16 precomputedPrimeTable[maxPrimeTableSize];
28 size = maxPrimeTableSize;
29 return precomputedPrimeTable;
34 unsigned int primeTableSize;
37 if (p.
IsPositive() && p <= primeTable[primeTableSize-1])
38 return std::binary_search(primeTable, primeTable+primeTableSize, (
word16)p.
ConvertToLong());
45 unsigned int primeTableSize;
51 for (i = 0; primeTable[i]<bound; i++)
52 if ((p % primeTable[i]) == 0)
55 if (bound == primeTable[i])
56 return (p % bound == 0);
63 unsigned int primeTableSize;
74 return a_exp_b_mod_c(b, n-1, n)==1;
84 if ((n.
IsEven() && n!=2) ||
GCD(b, n) != 1)
96 Integer z = a_exp_b_mod_c(b, m, n);
97 if (z==1 || z==nminus1)
99 for (
unsigned j=1; j<a; j++)
118 for (
unsigned int i=0; i<rounds; i++)
120 b.Randomize(rng, 2, n-2);
141 while ((j=
Jacobi(b.Squared()-4, n)) == 1)
151 return Lucas(n+1, b, n)==2;
168 while ((j=
Jacobi(b.Squared()-4, n)) == 1)
192 z = (z.Squared()-2)%n;
201struct NewLastSmallPrimeSquared
211 if (p <= s_lastSmallPrime)
227unsigned int PrimeSearchInterval(
const Integer &max)
232static inline bool FastProbablePrimeTest(
const Integer &n)
239 if (productBitLength < 16)
244 if (productBitLength%2==0)
246 minP =
Integer(182) << (productBitLength/2-8);
252 maxP =
Integer(181) << ((productBitLength+1)/2-8);
263 bool NextCandidate(
Integer &c);
268 Integer m_first, m_last, m_step;
271 std::vector<bool> m_sieve;
274PrimeSieve::PrimeSieve(
const Integer &first,
const Integer &last,
const Integer &step,
signed int delta)
275 : m_first(first), m_last(last), m_step(step), m_delta(delta), m_next(0)
280bool PrimeSieve::NextCandidate(
Integer &c)
282 bool safe =
SafeConvert(std::find(m_sieve.begin()+m_next, m_sieve.end(),
false) - m_sieve.begin(), m_next);
284 if (m_next == m_sieve.size())
286 m_first += long(m_sieve.size())*m_step;
287 if (m_first > m_last)
293 return NextCandidate(c);
298 c = m_first + long(m_next)*m_step;
308 size_t sieveSize = sieve.size();
309 size_t j = (
word32(p-(first%p))*stepInv) % p;
311 if (first.
WordCount() <= 1 && first + step*long(j) == p)
313 for (; j < sieveSize; j += p)
318void PrimeSieve::DoSieve()
320 unsigned int primeTableSize;
323 const unsigned int maxSieveSize = 32768;
324 unsigned int sieveSize =
STDMIN(
Integer(maxSieveSize), (m_last-m_first)/m_step+1).ConvertToLong();
327 m_sieve.resize(sieveSize,
false);
331 for (
unsigned int i = 0; i < primeTableSize; ++i)
332 SieveSingle(m_sieve, primeTable[i], m_first, m_step, (
word16)m_step.InverseMod(primeTable[i]));
337 Integer qFirst = (m_first-m_delta) >> 1;
338 Integer halfStep = m_step >> 1;
339 for (
unsigned int i = 0; i < primeTableSize; ++i)
343 SieveSingle(m_sieve, p, m_first, m_step, stepInv);
345 word16 halfStepInv = 2*stepInv < p ? 2*stepInv : 2*stepInv-p;
346 SieveSingle(m_sieve, p, qFirst, halfStep, halfStepInv);
359 if (p <= gcd && gcd <= max &&
IsPrime(gcd) && (!pSelector || pSelector->IsAcceptable(gcd)))
368 unsigned int primeTableSize;
371 if (p <= primeTable[primeTableSize-1])
377 pItr = std::upper_bound(primeTable, primeTable+primeTableSize, (
word)p.
ConvertToLong());
381 while (pItr < primeTable+primeTableSize && !(*pItr%mod == equiv && (!pSelector || pSelector->IsAcceptable(*pItr))))
384 if (pItr < primeTable+primeTableSize)
390 p = primeTable[primeTableSize-1]+1;
396 return FirstPrime(p, max,
CRT(equiv, mod, 1, 2, 1), mod<<1, pSelector);
403 PrimeSieve sieve(p, max, mod);
405 while (sieve.NextCandidate(p))
407 if ((!pSelector || pSelector->IsAcceptable(p)) && FastProbablePrimeTest(p) &&
IsPrime(p))
426 if (((r%q).Squared()-4*(r/q)).IsSquare())
429 unsigned int primeTableSize;
433 for (
int i=0; i<50; i++)
435 Integer b = a_exp_b_mod_c(primeTable[i], r, p);
437 return a_exp_b_mod_c(b, q, p) == 1;
448 if (maxP <=
Integer(s_lastSmallPrime).Squared())
455 unsigned int qbits = (pbits+2)/3 + 1 + rng.
GenerateWord32(0, pbits/36);
469 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*q2, maxP), q2);
471 while (sieve.NextCandidate(p))
473 if (FastProbablePrimeTest(p) && ProvePrime(p, q))
484 const unsigned smallPrimeBound = 29, c_opt=10;
487 unsigned int primeTableSize;
490 if (bits < smallPrimeBound)
498 const unsigned margin = bits > 50 ? 20 : (bits-10)/2;
501 relativeSize = std::pow(2.0,
double(rng.
GenerateWord32())/0xffffffff - 1);
502 while (bits * relativeSize >= bits - margin);
508 unsigned int trialDivisorBound = (
unsigned int)
STDMIN((
unsigned long)primeTable[primeTableSize-1], (
unsigned long)bits*bits/c_opt);
509 bool success =
false;
513 p *= q; p <<= 1; ++p;
517 b = a_exp_b_mod_c(a, (p-1)/q, p);
518 success = (
GCD(b-1, p) == 1) && (a_exp_b_mod_c(b, q, p) == 1);
528 return p * (u * (xq-xp) % q) + xp;
547 return a_exp_b_mod_c(a, (p+1)/4, p);
558 while (
Jacobi(n, p) != -1)
561 Integer y = a_exp_b_mod_c(n, q, p);
562 Integer x = a_exp_b_mod_c(a, (q-1)/2, p);
563 Integer b = (x.Squared()%p)*a%p;
581 for (
unsigned i=0; i<r-m-1; i++)
595 Integer D = (b.Squared() - 4*a*c) % p;
604 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
609 Integer t = (a+a).InverseMod(p);
637 return CRT(p2, p, q2, q, u);
774 while (a.GetBit(i)==0)
778 if (i%2==1 && (b%8==3 || b%8==5))
781 if (a%4==3 && b%4==3)
788 return (b==1) ? result : 0;
799 Integer v=p, v1=m.Subtract(m.Square(p), two);
807 v = m.Subtract(m.Multiply(v,v1), p);
809 v1 = m.Subtract(m.Square(v1), two);
814 v1 = m.Subtract(m.Multiply(v,v1), p);
816 v = m.Subtract(m.Square(v), two);
819 return m.ConvertOut(v);
1006 return CRT(p2, p, q2, q, u);
1014 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1021 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1032 if (qbits+1 == pbits)
1036 bool success =
false;
1041 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*12, maxP), 12, delta);
1043 while (sieve.NextCandidate(p))
1048 if (FastProbablePrimeTest(q) && FastProbablePrimeTest(p) &&
IsPrime(q) &&
IsPrime(p))
1060 for (g=2;
Jacobi(g, p) != 1; ++g) {}
1062 CRYPTOPP_ASSERT((p%8==1 || p%8==7) ? g==2 : (p%12==1 || p%12==11) ? g==3 : g==4);
1092 g = a_exp_b_mod_c(h, (p-1)/q, p);
1104 g =
Lucas((p+1)/q, h, p);
Classes for working with NameValuePairs.
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
An object that implements NameValuePairs.
Multiple precision integer with arithmetic operations.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
bool IsPositive() const
Determines if the Integer is positive.
signed long ConvertToLong() const
Convert the Integer to Long.
bool IsSquare() const
Determine whether this integer is a perfect square.
static const Integer & Zero()
Integer representing 0.
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Integer Squared() const
Multiply this integer by itself.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
@ ANY
a number with no special properties
@ PRIME
a number which is probabilistically prime
static const Integer & Two()
Integer representing 2.
bool IsNegative() const
Determines if the Integer is negative.
bool IsOdd() const
Determines if the Integer is odd parity.
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
static const Integer & One()
Integer representing 1.
bool IsEven() const
Determines if the Integer is even parity.
An invalid argument was detected.
Performs modular arithmetic in Montgomery representation for increased speed.
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
Application callback to signal suitability of a cabdidate prime.
Interface for random number generators.
virtual word32 GenerateWord32(word32 min=0, word32 max=0xffffffffUL)
Generate a random 32 bit word in the range min to max, inclusive.
Restricts the instantiation of a class to one static object without locks.
word64 word
Full word used for multiprecision integer arithmetic.
unsigned int word32
32-bit unsigned datatype
unsigned short word16
16-bit unsigned datatype
Multiple precision integer with arithmetic operations.
Utility functions for the Crypto++ library.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
bool SafeConvert(T1 from, T2 &to)
Perform a conversion from from to to.
Class file for performing modular arithmetic.
Crypto++ library namespace.
Classes and functions for number theoretic operations.
CRYPTOPP_DLL int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
CRYPTOPP_DLL bool IsPrime(const Integer &p)
Verifies a number is probably prime.
CRYPTOPP_DLL const word16 * GetPrimeTable(unsigned int &size)
The Small Prime table.
CRYPTOPP_DLL Integer MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
CRYPTOPP_DLL bool IsStrongLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
CRYPTOPP_DLL unsigned int DiscreteLogWorkFactor(unsigned int bitlength)
Estimate work factor.
Integer ModularExponentiation(const Integer &x, const Integer &e, const Integer &m)
Modular exponentiation.
CRYPTOPP_DLL Integer ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
CRYPTOPP_DLL bool IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
CRYPTOPP_DLL bool SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
Solve a Modular Quadratic Equation.
CRYPTOPP_DLL bool RabinMillerTest(RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
Determine if a number is probably prime.
CRYPTOPP_DLL Integer MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
CRYPTOPP_DLL Integer Lucas(const Integer &e, const Integer &p, const Integer &n)
Calculate the Lucas value.
CRYPTOPP_DLL Integer InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
Calculate the inverse Lucas value.
CRYPTOPP_DLL bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
CRYPTOPP_DLL Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Extract a modular root.
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Calculate multiplicative inverse.
CRYPTOPP_DLL bool SmallDivisorsTest(const Integer &p)
Tests whether a number is divisible by a small prime.
CRYPTOPP_DLL bool IsLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
CRYPTOPP_DLL bool TrialDivision(const Integer &p, unsigned bound)
Tests whether a number is divisible by a small prime.
CRYPTOPP_DLL unsigned int FactoringWorkFactor(unsigned int bitlength)
Estimate work factor.
CRYPTOPP_DLL bool IsFermatProbablePrime(const Integer &n, const Integer &b)
Determine if a number is probably prime.
CRYPTOPP_DLL Integer CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
Chinese Remainder Theorem.
CRYPTOPP_DLL bool IsStrongProbablePrime(const Integer &n, const Integer &b)
Determine if a number is probably prime.
CRYPTOPP_DLL bool FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
Finds a random prime of special form.
Classes for automatic resource management.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.