5#ifndef CRYPTOPP_IMPORTS
21const word s_lastSmallPrime = 32719;
25 std::vector<word16> * operator()()
const
27 const unsigned int maxPrimeTableSize = 3511;
30 std::vector<word16> &primeTable = *pPrimeTable;
31 primeTable.reserve(maxPrimeTableSize);
33 primeTable.push_back(2);
34 unsigned int testEntriesEnd = 1;
36 for (
unsigned int p=3; p<=s_lastSmallPrime; p+=2)
39 for (j=1; j<testEntriesEnd; j++)
40 if (p%primeTable[j] == 0)
42 if (j == testEntriesEnd)
44 primeTable.push_back(word16(p));
45 testEntriesEnd =
UnsignedMin(54U, primeTable.size());
49 return pPrimeTable.release();
53const word16 * GetPrimeTable(
unsigned int &size)
56 size = (
unsigned int)primeTable.size();
57 return &primeTable[0];
62 unsigned int primeTableSize;
63 const word16 * primeTable = GetPrimeTable(primeTableSize);
65 if (p.
IsPositive() && p <= primeTable[primeTableSize-1])
66 return std::binary_search(primeTable, primeTable+primeTableSize, (word16)p.
ConvertToLong());
71bool TrialDivision(
const Integer &p,
unsigned bound)
73 unsigned int primeTableSize;
74 const word16 * primeTable = GetPrimeTable(primeTableSize);
79 for (i = 0; primeTable[i]<bound; i++)
80 if ((p % primeTable[i]) == 0)
83 if (bound == primeTable[i])
84 return (p % bound == 0);
91 unsigned int primeTableSize;
92 const word16 * primeTable = GetPrimeTable(primeTableSize);
93 return !TrialDivision(p, primeTable[primeTableSize-1]);
102 return a_exp_b_mod_c(b, n-1, n)==1;
112 if ((n.
IsEven() && n!=2) ||
GCD(b, n) != 1)
124 Integer z = a_exp_b_mod_c(b, m, n);
125 if (z==1 || z==nminus1)
127 for (
unsigned j=1; j<a; j++)
146 for (
unsigned int i=0; i<rounds; i++)
148 b.Randomize(rng, 2, n-2);
149 if (!IsStrongProbablePrime(n, b))
169 while ((j=Jacobi(b.Squared()-4, n)) == 1)
179 return Lucas(n+1, b, n)==2;
182bool IsStrongLucasProbablePrime(
const Integer &n)
196 while ((j=Jacobi(b.Squared()-4, n)) == 1)
220 z = (z.Squared()-2)%n;
239 if (p <= s_lastSmallPrime)
240 return IsSmallPrime(p);
242 return SmallDivisorsTest(p);
244 return SmallDivisorsTest(p) && IsStrongProbablePrime(p, 3) && IsStrongLucasProbablePrime(p);
249 bool pass = IsPrime(p) && RabinMillerTest(rng, p, 1);
251 pass = pass && RabinMillerTest(rng, p, 10);
255unsigned int PrimeSearchInterval(
const Integer &max)
260static inline bool FastProbablePrimeTest(
const Integer &n)
262 return IsStrongProbablePrime(n,2);
267 if (productBitLength < 16)
272 if (productBitLength%2==0)
274 minP =
Integer(182) << (productBitLength/2-8);
280 maxP =
Integer(181) << ((productBitLength+1)/2-8);
291 bool NextCandidate(
Integer &c);
294 static void SieveSingle(std::vector<bool> &sieve, word16 p,
const Integer &first,
const Integer &step, word16 stepInv);
296 Integer m_first, m_last, m_step;
299 std::vector<bool> m_sieve;
302PrimeSieve::PrimeSieve(
const Integer &first,
const Integer &last,
const Integer &step,
signed int delta)
303 : m_first(first), m_last(last), m_step(step), m_delta(delta), m_next(0)
308bool PrimeSieve::NextCandidate(
Integer &c)
310 bool safe =
SafeConvert(std::find(m_sieve.begin()+m_next, m_sieve.end(),
false) - m_sieve.begin(), m_next);
312 if (m_next == m_sieve.size())
314 m_first += long(m_sieve.size())*m_step;
315 if (m_first > m_last)
321 return NextCandidate(c);
326 c = m_first + long(m_next)*m_step;
332void PrimeSieve::SieveSingle(std::vector<bool> &sieve, word16 p,
const Integer &first,
const Integer &step, word16 stepInv)
336 size_t sieveSize = sieve.size();
337 size_t j = (word32(p-(first%p))*stepInv) % p;
339 if (first.
WordCount() <= 1 && first + step*long(j) == p)
341 for (; j < sieveSize; j += p)
346void PrimeSieve::DoSieve()
348 unsigned int primeTableSize;
349 const word16 * primeTable = GetPrimeTable(primeTableSize);
351 const unsigned int maxSieveSize = 32768;
352 unsigned int sieveSize =
STDMIN(
Integer(maxSieveSize), (m_last-m_first)/m_step+1).ConvertToLong();
355 m_sieve.resize(sieveSize,
false);
359 for (
unsigned int i = 0; i < primeTableSize; ++i)
360 SieveSingle(m_sieve, primeTable[i], m_first, m_step, (word16)m_step.
InverseMod(primeTable[i]));
365 Integer qFirst = (m_first-m_delta) >> 1;
366 Integer halfStep = m_step >> 1;
367 for (
unsigned int i = 0; i < primeTableSize; ++i)
369 word16 p = primeTable[i];
370 word16 stepInv = (word16)m_step.
InverseMod(p);
371 SieveSingle(m_sieve, p, m_first, m_step, stepInv);
373 word16 halfStepInv = 2*stepInv < p ? 2*stepInv : 2*stepInv-p;
374 SieveSingle(m_sieve, p, qFirst, halfStep, halfStepInv);
387 if (p <= gcd && gcd <= max && IsPrime(gcd) && (!pSelector || pSelector->IsAcceptable(gcd)))
396 unsigned int primeTableSize;
397 const word16 * primeTable = GetPrimeTable(primeTableSize);
399 if (p <= primeTable[primeTableSize-1])
405 pItr = std::upper_bound(primeTable, primeTable+primeTableSize, (word)p.
ConvertToLong());
409 while (pItr < primeTable+primeTableSize && !(*pItr%mod == equiv && (!pSelector || pSelector->IsAcceptable(*pItr))))
412 if (pItr < primeTable+primeTableSize)
418 p = primeTable[primeTableSize-1]+1;
424 return FirstPrime(p, max, CRT(equiv, mod, 1, 2, 1), mod<<1, pSelector);
433 while (sieve.NextCandidate(p))
435 if ((!pSelector || pSelector->IsAcceptable(p)) && FastProbablePrimeTest(p) && IsPrime(p))
454 if (((r%q).Squared()-4*(r/q)).IsSquare())
457 unsigned int primeTableSize;
458 const word16 * primeTable = GetPrimeTable(primeTableSize);
461 for (
int i=0; i<50; i++)
463 Integer b = a_exp_b_mod_c(primeTable[i], r, p);
465 return a_exp_b_mod_c(b, q, p) == 1;
476 if (maxP <=
Integer(s_lastSmallPrime).Squared())
483 unsigned int qbits = (pbits+2)/3 + 1 + rng.
GenerateWord32(0, pbits/36);
484 Integer q = MihailescuProvablePrime(rng, qbits);
499 while (sieve.NextCandidate(p))
501 if (FastProbablePrimeTest(p) && ProvePrime(p, q))
512 const unsigned smallPrimeBound = 29, c_opt=10;
515 unsigned int primeTableSize;
516 const word16 * primeTable = GetPrimeTable(primeTableSize);
518 if (bits < smallPrimeBound)
522 while (TrialDivision(p, 1 << ((bits+1)/2)));
526 const unsigned margin = bits > 50 ? 20 : (bits-10)/2;
529 relativeSize = std::pow(2.0,
double(rng.
GenerateWord32())/0xffffffff - 1);
530 while (bits * relativeSize >= bits - margin);
533 Integer q = MaurerProvablePrime(rng,
unsigned(bits*relativeSize));
536 unsigned int trialDivisorBound = (
unsigned int)
STDMIN((
unsigned long)primeTable[primeTableSize-1], (
unsigned long)bits*bits/c_opt);
537 bool success =
false;
541 p *= q; p <<= 1; ++p;
542 if (!TrialDivision(p, trialDivisorBound))
545 b = a_exp_b_mod_c(a, (p-1)/q, p);
546 success = (
GCD(b-1, p) == 1) && (a_exp_b_mod_c(b, q, p) == 1);
556 return p * (u * (xq-xp) % q) + xp;
578 return a_exp_b_mod_c(a, (p+1)/4, p);
589 while (Jacobi(n, p) != -1)
592 Integer y = a_exp_b_mod_c(n, q, p);
593 Integer x = a_exp_b_mod_c(a, (q-1)/2, p);
594 Integer b = (x.Squared()%p)*a%p;
612 for (
unsigned i=0; i<r-m-1; i++)
626 Integer D = (b.Squared() - 4*a*c) % p;
627 switch (Jacobi(D, p))
635 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
639 Integer s = ModularSquareRoot(D, p);
640 Integer t = (a+a).InverseMod(p);
661 return CRT(p2, p, q2, q, u);
671 return ModularRoot(a, dp, dq, p, q, u);
798 while (a.GetBit(i)==0)
802 if (i%2==1 && (b%8==3 || b%8==5))
805 if (a%4==3 && b%4==3)
812 return (b==1) ? result : 0;
817 unsigned i = e.BitCount();
1005 #pragma omp parallel
1006 #pragma omp sections
1019 return CRT(p2, p, q2, q, u);
1022unsigned int FactoringWorkFactor(
unsigned int n)
1027 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1030unsigned int DiscreteLogWorkFactor(
unsigned int n)
1034 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1045 if (qbits+1 == pbits)
1049 bool success =
false;
1054 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*12, maxP), 12, delta);
1056 while (sieve.NextCandidate(p))
1061 if (FastProbablePrimeTest(q) && FastProbablePrimeTest(p) &&
IsPrime(q) &&
IsPrime(p))
1073 for (g=2;
Jacobi(g, p) != 1; ++g) {}
1075 CRYPTOPP_ASSERT((p%8==1 || p%8==7) ? g==2 : (p%12==1 || p%12==11) ? g==3 : g==4);
1105 g = a_exp_b_mod_c(h, (p-1)/q, p);
1117 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.
static const Integer & Zero()
Integer representing 0.
signed long ConvertToLong() const
Convert the Integer to Long.
bool IsSquare() const
Determine whether this integer is a perfect square.
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
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.
static const Integer & One()
Integer representing 1.
@ ANY
a number with no special properties
@ PRIME
a number which is probabilistically prime
bool IsNegative() const
Determines if the Integer is negative.
static Integer Power2(size_t e)
Exponentiates to a power of 2.
bool IsOdd() const
Determines if the Integer is odd parity.
static const Integer & Two()
Integer representing 2.
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
bool IsEven() const
Determines if the Integer is even parity.
An invalid argument was detected.
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Performs modular arithmetic in Montgomery representation for increased speed.
Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
const Integer & Square(const Integer &a) const
Square an element in the ring.
Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
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.
Pointer that overloads operator ->
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)
Tests whether a conversion from -> to is safe to perform.
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Class file for performing modular arithmetic.
Crypto++ library namespace.
Classes and functions for number theoretic operations.
Integer ModularExponentiation(const Integer &x, const Integer &e, const Integer &m)
Modular exponentiation.
Integer Lucas(const Integer &e, const Integer &p, const Integer &n)
Calculate the Lucas value.
bool IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
bool SmallDivisorsTest(const Integer &p)
Tests whether a number is divisible by a small prime.
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Calculate multiplicative inverse.
int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
bool IsPrime(const Integer &p)
Verifies a number is probably prime.
Classes for automatic resource management.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.