5#ifndef CRYPTOPP_IMPORTS
23const unsigned int maxPrimeTableSize = 3511;
24const word s_lastSmallPrime = 32719;
28 extern const word16 precomputedPrimeTable[maxPrimeTableSize];
29 size = maxPrimeTableSize;
30 return precomputedPrimeTable;
35 unsigned int primeTableSize;
38 if (p.
IsPositive() && p <= primeTable[primeTableSize-1])
39 return std::binary_search(primeTable, primeTable+primeTableSize, (
word16)p.
ConvertToLong());
46 unsigned int primeTableSize;
52 for (i = 0; primeTable[i]<bound; i++)
53 if ((p % primeTable[i]) == 0)
56 if (bound == primeTable[i])
57 return (p % bound == 0);
64 unsigned int primeTableSize;
75 return a_exp_b_mod_c(b, n-1, n)==1;
85 if ((n.
IsEven() && n!=2) ||
GCD(b, n) != 1)
97 Integer z = a_exp_b_mod_c(b, m, n);
98 if (z==1 || z==nminus1)
100 for (
unsigned j=1; j<a; j++)
119 for (
unsigned int i=0; i<rounds; i++)
142 while ((j=
Jacobi(b.Squared()-4, n)) == 1)
152 return Lucas(n+1, b, n)==2;
169 while ((j=
Jacobi(b.Squared()-4, n)) == 1)
193 z = (z.Squared()-2)%n;
202struct NewLastSmallPrimeSquared
212 if (p <= s_lastSmallPrime)
228unsigned int PrimeSearchInterval(
const Integer &max)
233static inline bool FastProbablePrimeTest(
const Integer &n)
240 if (productBitLength < 16)
245 if (productBitLength%2==0)
247 minP =
Integer(182) << (productBitLength/2-8);
253 maxP =
Integer(181) << ((productBitLength+1)/2-8);
264 bool NextCandidate(
Integer &c);
269 Integer m_first, m_last, m_step;
272 std::vector<bool> m_sieve;
275PrimeSieve::PrimeSieve(
const Integer &first,
const Integer &last,
const Integer &step,
signed int delta)
276 : m_first(first), m_last(last), m_step(step), m_delta(delta), m_next(0)
281bool PrimeSieve::NextCandidate(
Integer &c)
283 bool safe =
SafeConvert(std::find(m_sieve.begin()+m_next, m_sieve.end(),
false) - m_sieve.begin(), m_next);
285 if (m_next == m_sieve.size())
287 m_first += long(m_sieve.size())*m_step;
288 if (m_first > m_last)
294 return NextCandidate(c);
299 c = m_first + long(m_next)*m_step;
309 size_t sieveSize = sieve.size();
310 size_t j = (
word32(p-(first%p))*stepInv) % p;
312 if (first.
WordCount() <= 1 && first + step*long(j) == p)
314 for (; j < sieveSize; j += p)
319void PrimeSieve::DoSieve()
321 unsigned int primeTableSize;
324 const unsigned int maxSieveSize = 32768;
325 unsigned int sieveSize =
STDMIN(
Integer(maxSieveSize), (m_last-m_first)/m_step+1).ConvertToLong();
328 m_sieve.resize(sieveSize,
false);
332 for (
unsigned int i = 0; i < primeTableSize; ++i)
333 SieveSingle(m_sieve, primeTable[i], m_first, m_step, (
word16)m_step.InverseMod(primeTable[i]));
338 Integer qFirst = (m_first-m_delta) >> 1;
339 Integer halfStep = m_step >> 1;
340 for (
unsigned int i = 0; i < primeTableSize; ++i)
344 SieveSingle(m_sieve, p, m_first, m_step, stepInv);
346 word16 halfStepInv = 2*stepInv < p ? 2*stepInv : 2*stepInv-p;
347 SieveSingle(m_sieve, p, qFirst, halfStep, halfStepInv);
360 if (p <= gcd && gcd <= max &&
IsPrime(gcd) && (!pSelector || pSelector->IsAcceptable(gcd)))
369 unsigned int primeTableSize;
372 if (p <= primeTable[primeTableSize-1])
378 pItr = std::upper_bound(primeTable, primeTable+primeTableSize, (
word)p.
ConvertToLong());
382 while (pItr < primeTable+primeTableSize && !(*pItr%mod == equiv && (!pSelector || pSelector->IsAcceptable(*pItr))))
385 if (pItr < primeTable+primeTableSize)
391 p = primeTable[primeTableSize-1]+1;
397 return FirstPrime(p, max,
CRT(equiv, mod, 1, 2, 1), mod<<1, pSelector);
404 PrimeSieve sieve(p, max, mod);
406 while (sieve.NextCandidate(p))
408 if ((!pSelector || pSelector->IsAcceptable(p)) && FastProbablePrimeTest(p) &&
IsPrime(p))
427 if (((r%q).Squared()-4*(r/q)).IsSquare())
430 unsigned int primeTableSize;
434 for (
int i=0; i<50; i++)
436 Integer b = a_exp_b_mod_c(primeTable[i], r, p);
438 return a_exp_b_mod_c(b, q, p) == 1;
449 if (maxP <=
Integer(s_lastSmallPrime).Squared())
456 unsigned int qbits = (pbits+2)/3 + 1 + rng.
GenerateWord32(0, pbits/36);
470 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*q2, maxP), q2);
472 while (sieve.NextCandidate(p))
474 if (FastProbablePrimeTest(p) && ProvePrime(p, q))
485 const unsigned smallPrimeBound = 29, c_opt=10;
488 unsigned int primeTableSize;
491 if (bits < smallPrimeBound)
499 const unsigned margin = bits > 50 ? 20 : (bits-10)/2;
502 relativeSize = std::pow(2.0,
double(rng.
GenerateWord32())/0xffffffff - 1);
503 while (bits * relativeSize >= bits - margin);
509 unsigned int trialDivisorBound = (
unsigned int)
STDMIN((
unsigned long)primeTable[primeTableSize-1], (
unsigned long)bits*bits/c_opt);
510 bool success =
false;
514 p *= q; p <<= 1; ++p;
518 b = a_exp_b_mod_c(a, (p-1)/q, p);
519 success = (
GCD(b-1, p) == 1) && (a_exp_b_mod_c(b, q, p) == 1);
529 return p * (u * (xq-xp) % q) + xp;
551 return a_exp_b_mod_c(a, (p+1)/4, p);
562 while (
Jacobi(n, p) != -1)
565 Integer y = a_exp_b_mod_c(n, q, p);
566 Integer x = a_exp_b_mod_c(a, (q-1)/2, p);
567 Integer b = (x.Squared()%p)*a%p;
585 for (
unsigned i=0; i<r-m-1; i++)
602 Integer D = (b.Squared() - 4*a*c) % p;
611 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
616 Integer t = (a+a).InverseMod(p);
647 return CRT(p2, p, q2, q, u);
787 while (a.GetBit(i)==0)
791 if (i%2==1 && (b%8==3 || b%8==5))
794 if (a%4==3 && b%4==3)
801 return (b==1) ? result : 0;
812 Integer v=p, v1=m.Subtract(m.Square(p), two);
820 v = m.Subtract(m.Multiply(v,v1), p);
822 v1 = m.Subtract(m.Square(v1), two);
827 v1 = m.Subtract(m.Multiply(v,v1), p);
829 v = m.Subtract(m.Square(v), two);
832 return m.ConvertOut(v);
1021 return CRT(p2, p, q2, q, u);
1029 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1036 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1047 if (qbits+1 == pbits)
1051 bool success =
false;
1056 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*12, maxP), 12, delta);
1058 while (sieve.NextCandidate(p))
1063 if (FastProbablePrimeTest(q) && FastProbablePrimeTest(p) &&
IsPrime(q) &&
IsPrime(p))
1075 for (g=2;
Jacobi(g, p) != 1; ++g) {}
1077 CRYPTOPP_ASSERT((p%8==1 || p%8==7) ? g==2 : (p%12==1 || p%12==11) ? g==3 : g==4);
1107 g = a_exp_b_mod_c(h, (p-1)/q, p);
1119 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 candidate 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.
Debugging and diagnostic assertions.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.