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();
53 const 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());
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);
89 bool SmallDivisorsTest(
const Integer &p)
91 unsigned int primeTableSize;
92 const word16 * primeTable = GetPrimeTable(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);
149 if (!IsStrongProbablePrime(n, b))
155 bool IsLucasProbablePrime(
const Integer &n)
169 while ((j=Jacobi(b.Squared()-4, n)) == 1)
179 return Lucas(n+1, b, n)==2;
182 bool IsStrongLucasProbablePrime(
const Integer &n)
196 while ((j=Jacobi(b.Squared()-4, n)) == 1)
220 z = (z.Squared()-2)%n;
239 if (p <= s_lastSmallPrime)
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);
255 unsigned int PrimeSearchInterval(
const Integer &max)
260 static 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;
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;
332 void 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)
346 void 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);
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)
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;
624 switch (Jacobi(D, p))
632 r1 = r2 = (-b*(a+a).InverseMod(p)) % p;
636 Integer s = ModularSquareRoot(D, p);
637 Integer t = (a+a).InverseMod(p);
654 p2 = ModularExponentiation((a % p), dp, p);
656 q2 = ModularExponentiation((a % q), dq, q);
658 return CRT(p2, p, q2, q, u);
664 Integer dp = EuclideanMultiplicativeInverse(e, p-1);
665 Integer dq = EuclideanMultiplicativeInverse(e, q-1);
666 Integer u = EuclideanMultiplicativeInverse(p, q);
668 return ModularRoot(a, dp, dq, p, q, u);
795 while (a.GetBit(i)==0)
799 if (i%2==1 && (b%8==3 || b%8==5))
802 if (a%4==3 && b%4==3)
809 return (b==1) ? result : 0;
814 unsigned i = e.BitCount();
820 Integer v=p, v1=m.Subtract(m.Square(p), two);
828 v = m.Subtract(m.Multiply(v,v1), p);
830 v1 = m.Subtract(m.Square(v1), two);
835 v1 = m.Subtract(m.Multiply(v,v1), p);
837 v = m.Subtract(m.Square(v), two);
840 return m.ConvertOut(v);
1002 #pragma omp parallel 1003 #pragma omp sections 1008 p2 = Lucas(EuclideanMultiplicativeInverse(e,p2), m, p);
1013 q2 = Lucas(EuclideanMultiplicativeInverse(e,q2), m, q);
1016 return CRT(p2, p, q2, q, u);
1019 unsigned int FactoringWorkFactor(
unsigned int n)
1024 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1027 unsigned int DiscreteLogWorkFactor(
unsigned int n)
1031 else return (
unsigned int)(2.4 * std::pow((
double)n, 1.0/3.0) * std::pow(log(
double(n)), 2.0/3.0) - 5);
1042 if (qbits+1 == pbits)
1046 bool success =
false;
1051 PrimeSieve sieve(p,
STDMIN(p+PrimeSearchInterval(maxP)*12, maxP), 12, delta);
1053 while (sieve.NextCandidate(p))
1058 if (FastProbablePrimeTest(q) && FastProbablePrimeTest(p) &&
IsPrime(q) &&
IsPrime(p))
1070 for (g=2; Jacobi(g, p) != 1; ++g) {}
1072 CRYPTOPP_ASSERT((p%8==1 || p%8==7) ? g==2 : (p%12==1 || p%12==11) ? g==3 : g==4);
1080 if (Jacobi(g*g-4, p)==-1 && Lucas(q, g, p)==2)
1102 g = a_exp_b_mod_c(h, (p-1)/q, p);
1112 if (Jacobi(h*h-4, p)==1)
1114 g = Lucas((p+1)/q, h, p);
An invalid argument was detected.
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
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 IsSquare() const
Determine whether this integer is a perfect square.
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.
signed long ConvertToLong() const
Convert the Integer to Long.
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.
bool IsNegative() const
Determines if the Integer is negative.
Interface for random number generators.
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
Integer InverseMod(const Integer &n) const
calculate multiplicative inverse of *this mod n
bool IsPositive() const
Determines if the Integer is positive.
static const Integer & One()
Integer representing 1.
Pointer that overloads operator ->
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.
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.
bool IsEven() const
Determines if the Integer is even parity.
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)
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
Classes and functions for number theoretic operations.
Integer Squared() const
Multiply this integer by itself.
Performs modular arithmetic in Montgomery representation for increased speed.
An object that implements NameValuePairs.
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
Multiple precision integer with arithmetic operations.
static const Integer & Zero()
Integer representing 0.
Class file for performing modular arithmetic.
Crypto++ library namespace.
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
bool IsOdd() const
Determines if the Integer is odd parity.