5#ifndef CRYPTOPP_IMPORTS
19NAMESPACE_BEGIN(CryptoPP)
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);
76 CRYPTOPP_ASSERT(primeTable[primeTableSize-1] >= bound);
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]);
101 CRYPTOPP_ASSERT(n>3 && b>1 && b<n-1);
102 return a_exp_b_mod_c(b, n-1, n)==1;
110 CRYPTOPP_ASSERT(n>3 && b>1 && b<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++)
143 CRYPTOPP_ASSERT(n>3);
146 for (
unsigned int i=0; i<rounds; i++)
148 b.Randomize(rng, 2, n-2);
149 if (!IsStrongProbablePrime(n, b))
163 CRYPTOPP_ASSERT(n>2);
169 while ((j=Jacobi(b.Squared()-4, n)) == 1)
179 return Lucas(n+1, b, n)==2;
182bool IsStrongLucasProbablePrime(
const Integer &n)
190 CRYPTOPP_ASSERT(n>2);
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);
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);
311 CRYPTOPP_UNUSED(safe); CRYPTOPP_ASSERT(safe);
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;
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]));
364 CRYPTOPP_ASSERT(m_step%2==0);
365 Integer qFirst = (m_first-m_delta) >> 1;
366 Integer halfStep = m_step >> 1;
367 for (
unsigned int i = 0; i < primeTableSize; ++i)
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);
381 CRYPTOPP_ASSERT(!equiv.
IsNegative() && equiv < mod);
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;
421 CRYPTOPP_ASSERT(p > primeTable[primeTableSize-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))
445 CRYPTOPP_ASSERT(p < q*q*q);
446 CRYPTOPP_ASSERT(p % q == 1);
454 if (((r%q).Squared()-4*(r/q)).IsSquare())
457 unsigned int primeTableSize;
458 const word16 * primeTable = GetPrimeTable(primeTableSize);
460 CRYPTOPP_ASSERT(primeTableSize >= 50);
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;
575 return a_exp_b_mod_c(a, (p+1)/4, p);
586 while (Jacobi(n, p) != -1)
589 Integer y = a_exp_b_mod_c(n, q, p);
590 Integer x = a_exp_b_mod_c(a, (q-1)/2, p);
591 Integer b = (x.Squared()%p)*a%p;
609 for (
unsigned i=0; i<r-m-1; i++)
617 CRYPTOPP_ASSERT(x.Squared()%p == a);
623 Integer D = (b.Squared() - 4*a*c) % p;
624 switch (Jacobi(D, p))
627 CRYPTOPP_ASSERT(
false);
632 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
633 CRYPTOPP_ASSERT(((r1.Squared()*a + r1*b + c) % p).IsZero());
636 Integer s = ModularSquareRoot(D, p);
637 Integer t = (a+a).InverseMod(p);
640 CRYPTOPP_ASSERT(((r1.Squared()*a + r1*b + c) % p).IsZero());
641 CRYPTOPP_ASSERT(((r2.Squared()*a + r2*b + c) % p).IsZero());
665 return CRT(p2, p, q2, q, u);
674 CRYPTOPP_ASSERT(!!dp && !!dq && !!u);
675 return ModularRoot(a, dp, dq, p, q, u);
794 CRYPTOPP_ASSERT(bIn.
IsOdd());
802 while (a.GetBit(i)==0)
806 if (i%2==1 && (b%8==3 || b%8==5))
809 if (a%4==3 && b%4==3)
816 return (b==1) ? result : 0;
821 unsigned i = e.BitCount();
1011 #pragma omp parallel
1012 #pragma omp sections
1027 const Integer t1 = p-Jacobi(d,p);
1030 const Integer t2 = q-Jacobi(d,q);
1034 return CRT(p2, p, q2, q, u);
1037unsigned int FactoringWorkFactor(
unsigned int n)
1042 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1045unsigned int DiscreteLogWorkFactor(
unsigned int n)
1049 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1057 CRYPTOPP_ASSERT(qbits > 4);
1058 CRYPTOPP_ASSERT(pbits > qbits);
1060 if (qbits+1 == pbits)
1064 bool success =
false;
1069 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*12, maxP), 12, delta);
1071 while (sieve.NextCandidate(p))
1076 if (FastProbablePrimeTest(q) && FastProbablePrimeTest(p) &&
IsPrime(q) &&
IsPrime(p))
1088 for (g=2;
Jacobi(g, p) != 1; ++g) {}
1090 CRYPTOPP_ASSERT((p%8==1 || p%8==7) ? g==2 : (p%12==1 || p%12==11) ? g==3 : g==4);
1094 CRYPTOPP_ASSERT(delta == -1);
1120 g = a_exp_b_mod_c(h, (p-1)/q, p);
1122 CRYPTOPP_ASSERT(a_exp_b_mod_c(g, q, p)==1);
1126 CRYPTOPP_ASSERT(delta==-1);
1132 g =
Lucas((p+1)/q, h, p);
1134 CRYPTOPP_ASSERT(
Lucas(q, g, p) == 2);
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 &CRYPTOPP_API 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 &CRYPTOPP_API 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 CRYPTOPP_API Power2(size_t e)
Exponentiates to a power of 2.
bool IsOdd() const
Determines if the Integer is odd parity.
static const Integer &CRYPTOPP_API 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 ->
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)
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 negative and incorrectly promoted.
Class file for performing modular arithmetic.
Classes and functions for number theoretic operations.
Integer ModularExponentiation(const Integer &x, const Integer &e, const Integer &m)
Modular exponentiation.
CRYPTOPP_DLL Integer CRYPTOPP_API Lucas(const Integer &e, const Integer &p, const Integer &n)
Calculate the Lucas value.
CRYPTOPP_DLL bool CRYPTOPP_API IsPrime(const Integer &p)
Verifies a number is probably prime.
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Calculate multiplicative inverse.
CRYPTOPP_DLL bool CRYPTOPP_API IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest(const Integer &p)
Tests whether a number is divisible by a small prime.
Classes for automatic resource management.