5 #ifndef CRYPTOPP_IMPORTS
21 NAMESPACE_BEGIN(CryptoPP)
23 const word s_lastSmallPrime = 32719;
27 std::vector<word16> * operator()()
const
29 const unsigned int maxPrimeTableSize = 3511;
32 std::vector<word16> &primeTable = *pPrimeTable;
33 primeTable.reserve(maxPrimeTableSize);
35 primeTable.push_back(2);
36 unsigned int testEntriesEnd = 1;
38 for (
unsigned int p=3; p<=s_lastSmallPrime; p+=2)
41 for (j=1; j<testEntriesEnd; j++)
42 if (p%primeTable[j] == 0)
44 if (j == testEntriesEnd)
46 primeTable.push_back(word16(p));
47 testEntriesEnd =
UnsignedMin(54U, primeTable.size());
51 return pPrimeTable.release();
55 const word16 * GetPrimeTable(
unsigned int &size)
58 size = (
unsigned int)primeTable.size();
59 return &primeTable[0];
64 unsigned int primeTableSize;
65 const word16 * primeTable = GetPrimeTable(primeTableSize);
67 if (p.
IsPositive() && p <= primeTable[primeTableSize-1])
68 return std::binary_search(primeTable, primeTable+primeTableSize, (word16)p.
ConvertToLong());
75 unsigned int primeTableSize;
76 const word16 * primeTable = GetPrimeTable(primeTableSize);
81 for (i = 0; primeTable[i]<bound; i++)
82 if ((p % primeTable[i]) == 0)
85 if (bound == primeTable[i])
86 return (p % bound == 0);
91 bool SmallDivisorsTest(
const Integer &p)
93 unsigned int primeTableSize;
94 const word16 * primeTable = GetPrimeTable(primeTableSize);
104 return a_exp_b_mod_c(b, n-1, n)==1;
114 if ((n.
IsEven() && n!=2) || GCD(b, n) != 1)
126 Integer z = a_exp_b_mod_c(b, m, n);
127 if (z==1 || z==nminus1)
129 for (
unsigned j=1; j<a; j++)
148 for (
unsigned int i=0; i<rounds; i++)
151 if (!IsStrongProbablePrime(n, b))
157 bool IsLucasProbablePrime(
const Integer &n)
171 while ((j=Jacobi(b.
Squared()-4, n)) == 1)
181 return Lucas(n+1, b, n)==2;
184 bool IsStrongLucasProbablePrime(
const Integer &n)
198 while ((j=Jacobi(b.
Squared()-4, n)) == 1)
241 if (p <= s_lastSmallPrime)
244 return SmallDivisorsTest(p);
246 return SmallDivisorsTest(p) && IsStrongProbablePrime(p, 3) && IsStrongLucasProbablePrime(p);
251 bool pass =
IsPrime(p) && RabinMillerTest(rng, p, 1);
253 pass = pass && RabinMillerTest(rng, p, 10);
257 unsigned int PrimeSearchInterval(
const Integer &max)
262 static inline bool FastProbablePrimeTest(
const Integer &n)
264 return IsStrongProbablePrime(n,2);
269 if (productBitLength < 16)
274 if (productBitLength%2==0)
276 minP =
Integer(182) << (productBitLength/2-8);
282 maxP =
Integer(181) << ((productBitLength+1)/2-8);
293 bool NextCandidate(
Integer &c);
296 static void SieveSingle(std::vector<bool> &sieve, word16 p,
const Integer &first,
const Integer &step, word16 stepInv);
298 Integer m_first, m_last, m_step;
301 std::vector<bool> m_sieve;
304 PrimeSieve::PrimeSieve(
const Integer &first,
const Integer &last,
const Integer &step,
signed int delta)
305 : m_first(first), m_last(last), m_step(step), m_delta(delta), m_next(0)
310 bool PrimeSieve::NextCandidate(
Integer &c)
312 bool safe =
SafeConvert(std::find(m_sieve.begin()+m_next, m_sieve.end(),
false) - m_sieve.begin(), m_next);
314 if (m_next == m_sieve.size())
316 m_first += long(m_sieve.size())*m_step;
317 if (m_first > m_last)
323 return NextCandidate(c);
328 c = m_first + long(m_next)*m_step;
334 void PrimeSieve::SieveSingle(std::vector<bool> &sieve, word16 p,
const Integer &first,
const Integer &step, word16 stepInv)
338 size_t sieveSize = sieve.size();
339 size_t j = (word32(p-(first%p))*stepInv) % p;
341 if (first.
WordCount() <= 1 && first + step*long(j) == p)
343 for (; j < sieveSize; j += p)
348 void PrimeSieve::DoSieve()
350 unsigned int primeTableSize;
351 const word16 * primeTable = GetPrimeTable(primeTableSize);
353 const unsigned int maxSieveSize = 32768;
354 unsigned int sieveSize =
STDMIN(
Integer(maxSieveSize), (m_last-m_first)/m_step+1).ConvertToLong();
357 m_sieve.resize(sieveSize,
false);
361 for (
unsigned int i = 0; i < primeTableSize; ++i)
362 SieveSingle(m_sieve, primeTable[i], m_first, m_step, (word16)m_step.
InverseMod(primeTable[i]));
367 Integer qFirst = (m_first-m_delta) >> 1;
368 Integer halfStep = m_step >> 1;
369 for (
unsigned int i = 0; i < primeTableSize; ++i)
371 word16 p = primeTable[i];
372 word16 stepInv = (word16)m_step.
InverseMod(p);
373 SieveSingle(m_sieve, p, m_first, m_step, stepInv);
375 word16 halfStepInv = 2*stepInv < p ? 2*stepInv : 2*stepInv-p;
376 SieveSingle(m_sieve, p, qFirst, halfStep, halfStepInv);
389 if (p <= gcd && gcd <= max &&
IsPrime(gcd) && (!pSelector || pSelector->IsAcceptable(gcd)))
398 unsigned int primeTableSize;
399 const word16 * primeTable = GetPrimeTable(primeTableSize);
401 if (p <= primeTable[primeTableSize-1])
407 pItr = std::upper_bound(primeTable, primeTable+primeTableSize, (word)p.
ConvertToLong());
411 while (pItr < primeTable+primeTableSize && !(*pItr%mod == equiv && (!pSelector || pSelector->IsAcceptable(*pItr))))
414 if (pItr < primeTable+primeTableSize)
420 p = primeTable[primeTableSize-1]+1;
426 return FirstPrime(p, max, CRT(equiv, mod, 1, 2, 1), mod<<1, pSelector);
435 while (sieve.NextCandidate(p))
437 if ((!pSelector || pSelector->IsAcceptable(p)) && FastProbablePrimeTest(p) &&
IsPrime(p))
456 if (((r%q).Squared()-4*(r/q)).IsSquare())
459 unsigned int primeTableSize;
460 const word16 * primeTable = GetPrimeTable(primeTableSize);
463 for (
int i=0; i<50; i++)
465 Integer b = a_exp_b_mod_c(primeTable[i], r, p);
467 return a_exp_b_mod_c(b, q, p) == 1;
478 if (maxP <=
Integer(s_lastSmallPrime).Squared())
485 unsigned int qbits = (pbits+2)/3 + 1 + rng.
GenerateWord32(0, pbits/36);
501 while (sieve.NextCandidate(p))
503 if (FastProbablePrimeTest(p) && ProvePrime(p, q))
514 const unsigned smallPrimeBound = 29, c_opt=10;
517 unsigned int primeTableSize;
518 const word16 * primeTable = GetPrimeTable(primeTableSize);
520 if (bits < smallPrimeBound)
528 const unsigned margin = bits > 50 ? 20 : (bits-10)/2;
531 relativeSize = pow(2.0,
double(rng.
GenerateWord32())/0xffffffff - 1);
532 while (bits * relativeSize >= bits - margin);
538 unsigned int trialDivisorBound = (
unsigned int)
STDMIN((
unsigned long)primeTable[primeTableSize-1], (
unsigned long)bits*bits/c_opt);
539 bool success =
false;
543 p *= q; p <<= 1; ++p;
547 b = a_exp_b_mod_c(a, (p-1)/q, p);
548 success = (GCD(b-1, p) == 1) && (a_exp_b_mod_c(b, q, p) == 1);
558 return p * (u * (xq-xp) % q) + xp;
577 return a_exp_b_mod_c(a, (p+1)/4, p);
588 while (Jacobi(n, p) != -1)
591 Integer y = a_exp_b_mod_c(n, q, p);
592 Integer x = a_exp_b_mod_c(a, (q-1)/2, p);
611 for (
unsigned i=0; i<r-m-1; i++)
626 switch (Jacobi(D, p))
634 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
638 Integer s = ModularSquareRoot(D, p);
639 Integer t = (a+a).InverseMod(p);
656 p2 = ModularExponentiation((a % p), dp, p);
658 q2 = ModularExponentiation((a % q), dq, q);
660 return CRT(p2, p, q2, q, u);
666 Integer dp = EuclideanMultiplicativeInverse(e, p-1);
667 Integer dq = EuclideanMultiplicativeInverse(e, q-1);
668 Integer u = EuclideanMultiplicativeInverse(p, q);
670 return ModularRoot(a, dp, dq, p, q, u);
797 while (a.GetBit(i)==0)
801 if (i%2==1 && (b%8==3 || b%8==5))
804 if (a%4==3 && b%4==3)
811 return (b==1) ? result : 0;
822 Integer v=p, v1=m.Subtract(m.Square(p), two);
830 v = m.Subtract(m.Multiply(v,v1), p);
832 v1 = m.Subtract(m.Square(v1), two);
837 v1 = m.Subtract(m.Multiply(v,v1), p);
839 v = m.Subtract(m.Square(v), two);
842 return m.ConvertOut(v);
1004 #pragma omp parallel
1005 #pragma omp sections
1010 p2 = Lucas(EuclideanMultiplicativeInverse(e,p2), m, p);
1015 q2 = Lucas(EuclideanMultiplicativeInverse(e,q2), m, q);
1018 return CRT(p2, p, q2, q, u);
1021 unsigned int FactoringWorkFactor(
unsigned int n)
1026 else return (
unsigned int)(2.4 * pow((
double)n, 1.0/3.0) * pow(log(
double(n)), 2.0/3.0) - 5);
1029 unsigned int DiscreteLogWorkFactor(
unsigned int n)
1033 else return (
unsigned int)(2.4 * pow((
double)n, 1.0/3.0) * pow(log(
double(n)), 2.0/3.0) - 5);
1038 void PrimeAndGenerator::Generate(
signed int delta,
RandomNumberGenerator &rng,
unsigned int pbits,
unsigned int qbits)
1044 if (qbits+1 == pbits)
1048 bool success =
false;
1053 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*12, maxP), 12, delta);
1055 while (sieve.NextCandidate(p))
1060 if (FastProbablePrimeTest(q) && FastProbablePrimeTest(p) &&
IsPrime(q) &&
IsPrime(p))
1072 for (g=2; Jacobi(g, p) != 1; ++g) {}
1074 CRYPTOPP_ASSERT((p%8==1 || p%8==7) ? g==2 : (p%12==1 || p%12==11) ? g==3 : g==4);
1082 if (Jacobi(g*g-4, p)==-1 && Lucas(q, g, p)==2)
1104 g = a_exp_b_mod_c(h, (p-1)/q, p);
1114 if (Jacobi(h*h-4, p)==1)
1116 g = Lucas((p+1)/q, h, p);
An invalid argument was detected.
Classes for working with NameValuePairs.
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
a number which is probabilistically prime
Utility functions for the Crypto++ library.
Restricts the instantiation of a class to one static object without locks.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
bool IsOdd() const
Determines if the Integer is odd parity.
bool FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
Finds a random prime of special form.
virtual word32 GenerateWord32(word32 min=0, word32 max=0xffffffffUL)
Generate a random 32 bit word in the range min to max, inclusive.
bool IsEven() const
Determines if the Integer is even parity.
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
Integer MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
Classes for automatic resource management.
bool IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
Interface for random number generators.
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
static const Integer & One()
Integer representing 1.
Pointer that overloads operator ->
bool IsSquare() const
return whether this integer is a perfect square
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Integer MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
bool IsPositive() const
Determines if the Integer is positive.
a number with no special properties
bool IsNegative() const
Determines if the Integer is negative.
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
signed long ConvertToLong() const
Convert the Integer to Long.
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a prime number.
Application callback to signal suitability of a cabdidate prime.
static Integer Power2(size_t e)
Exponentiates to a power of 2.
Multiple precision integer with arithmetic operations.
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
bool IsPrime(const Integer &p)
Verifies a prime number.
static const Integer & Two()
Integer representing 2.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
bool TrialDivision(const Integer &p, unsigned bound)
Classes and functions for number theoretic operations.
Performs modular arithmetic in Montgomery representation for increased speed.
An object that implements NameValuePairs.
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
Multiple precision integer with arithmetic operations.
static const Integer & Zero()
Integer representing 0.
Class file for performing modular arithmetic.