5 #ifndef CRYPTOPP_IMPORTS
21 const 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();
56 size = (
unsigned int)primeTable.size();
57 return &primeTable[0];
62 unsigned int primeTableSize;
65 if (p.
IsPositive() && p <= primeTable[primeTableSize-1])
66 return std::binary_search(primeTable, primeTable+primeTableSize, (
word16)p.
ConvertToLong());
73 unsigned int 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;
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);
169 while ((j=
Jacobi(b.Squared()-4, n)) == 1)
179 return Lucas(n+1, b, n)==2;
196 while ((j=
Jacobi(b.Squared()-4, n)) == 1)
220 z = (z.Squared()-2)%n;
229 struct NewLastSmallPrimeSquared
239 if (p <= s_lastSmallPrime)
255 unsigned int PrimeSearchInterval(
const Integer &max)
260 static inline bool FastProbablePrimeTest(
const Integer &n)
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;
302 PrimeSieve::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)
308 bool 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;
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)
346 void PrimeSieve::DoSieve()
348 unsigned int 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)
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;
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);
431 PrimeSieve sieve(p, max, mod);
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;
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);
497 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*q2, maxP), q2);
499 while (sieve.NextCandidate(p))
501 if (FastProbablePrimeTest(p) && ProvePrime(p, q))
512 const unsigned smallPrimeBound = 29, c_opt=10;
515 unsigned int primeTableSize;
518 if (bits < smallPrimeBound)
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);
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;
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++)
623 Integer D = (b.Squared() - 4*a*c) % p;
632 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
637 Integer t = (a+a).InverseMod(p);
665 return CRT(p2, p, q2, q, u);
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;
827 Integer v=p, v1=m.Subtract(m.Square(p), two);
835 v = m.Subtract(m.Multiply(v,v1), p);
837 v1 = m.Subtract(m.Square(v1), two);
842 v1 = m.Subtract(m.Multiply(v,v1), p);
844 v = m.Subtract(m.Square(v), two);
847 return m.ConvertOut(v);
1011 #pragma omp parallel
1012 #pragma omp sections
1034 return CRT(p2, p, q2, q, u);
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);
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);
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);
1120 g = a_exp_b_mod_c(h, (p-1)/q, p);
1132 g =
Lucas((p+1)/q, h, p);