5 #ifndef CRYPTOPP_IMPORTS 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);
78 assert(primeTable[primeTableSize-1] >= bound);
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);
103 assert(n>3 && b>1 && b<n-1);
104 return a_exp_b_mod_c(b, n-1, n)==1;
112 assert(n>3 && b>1 && b<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);
313 CRYPTOPP_UNUSED(safe); assert(safe);
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);
383 assert(!equiv.IsNegative() && equiv < mod);
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;
423 assert(p > primeTable[primeTableSize-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);
462 assert(primeTableSize >= 50);
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;
635 assert(((r1.
Squared()*a + r1*b + c) % p).IsZero());
638 Integer s = ModularSquareRoot(D, p);
639 Integer t = (a+a).InverseMod(p);
642 assert(((r1.
Squared()*a + r1*b + c) % p).IsZero());
643 assert(((r2.
Squared()*a + r2*b + c) % p).IsZero());
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);
669 assert(!!dp && !!dq && !!u);
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)
1042 assert(pbits > 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 assert((p%8==1 || p%8==7) ? g==2 : (p%12==1 || p%12==11) ? g==3 : g==4);
1078 assert(delta == -1);
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);
1106 assert(a_exp_b_mod_c(g, q, p)==1);
1114 if (Jacobi(h*h-4, p)==1)
1116 g = Lucas((p+1)/q, h, p);
1118 assert(Lucas(q, g, p) == 2);
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
return the i-th bit, i=0 being the least significant bit
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.
unsigned int WordCount() const
number of significant words = ceiling(ByteCount()/sizeof(word))
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
number of significant bits = floor(log2(abs(*this))) + 1
Integer MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
a number with no special properties
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
signed long ConvertToLong() const
return equivalent signed long if possible, otherwise undefined
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.
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
static const Integer & Zero()
Integer representing 0.
Class file for performing modular arithmetic.
Crypto++ library namespace.