Crypto++
8.2
Free C++ class library of cryptographic schemes
|
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;
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);
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;
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;
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;
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;
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);
658 return CRT(p2, p, q2, 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();
1002 #pragma omp parallel
1003 #pragma omp sections
1016 return CRT(p2, p, q2, q, u);
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);
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);
1102 g = a_exp_b_mod_c(h, (p-1)/q, p);
1114 g =
Lucas((p+1)/q, h, p);
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
An object that implements NameValuePairs.
Integer InverseMod(const Integer &n) const
Calculate multiplicative inverse.
AlgorithmParameters MakeParameters(const char *name, const T &value, bool throwIfNotUsed=true)
Create an object that implements NameValuePairs.
Pointer that overloads operator ->
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Classes and functions for number theoretic operations.
Integer Squared() const
Multiply this integer by itself.
Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Extract a modular root.
signed long ConvertToLong() const
Convert the Integer to Long.
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Calculate multiplicative inverse.
static const Integer & One()
Integer representing 1.
Integer MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
Integer ConvertOut(const Integer &a) const
Reduces an element in the congruence class.
@ ANY
a number with no special properties
#define CRYPTOPP_ASSERT(exp)
Debugging and diagnostic assertion.
Integer ConvertIn(const Integer &a) const
Reduces an element in the congruence class.
const T1 UnsignedMin(const T1 &a, const T2 &b)
Safe comparison of values that could be neagtive and incorrectly promoted.
Classes for automatic resource management.
bool SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
Solve a Modular Quadratic Equation.
bool SmallDivisorsTest(const Integer &p)
Tests whether a number is divisible by a small prime.
bool IsEven() const
Determines if the Integer is even parity.
Restricts the instantiation of a class to one static object without locks.
Class file for performing modular arithmetic.
void Generate(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits)
Generate a Prime and Generator.
static Integer Power2(size_t e)
Exponentiates to a power of 2.
bool SafeConvert(T1 from, T2 &to)
Tests whether a conversion from -> to is safe to perform.
Integer ModularExponentiation(const Integer &x, const Integer &e, const Integer &m)
Modular exponentiation.
bool IsLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
Integer ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.
Interface for random number generators.
bool IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
int Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
Integer CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
Chinese Remainder Theorem.
bool IsStrongLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
Utility functions for the Crypto++ library.
const T & STDMIN(const T &a, const T &b)
Replacement function for std::min.
const Integer & Multiply(const Integer &a, const Integer &b) const
Multiplies elements in the ring.
bool IsOdd() const
Determines if the Integer is odd parity.
const word16 * GetPrimeTable(unsigned int &size)
The Small Prime table.
Application callback to signal suitability of a cabdidate prime.
Integer InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
Calculate the inverse Lucas value.
bool FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
Finds a random prime of special form.
bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
Integer Lucas(const Integer &e, const Integer &p, const Integer &n)
Calculate the Lucas value.
virtual word32 GenerateWord32(word32 min=0, word32 max=0xffffffffUL)
Generate a random 32 bit word in the range min to max, inclusive.
bool IsSquare() const
Determine whether this integer is a perfect square.
void Randomize(RandomNumberGenerator &rng, size_t bitCount)
Set this Integer to random integer.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
bool IsPositive() const
Determines if the Integer is positive.
An invalid argument was detected.
bool TrialDivision(const Integer &p, unsigned bound)
Tests whether a number is divisible by a small prime.
unsigned int FactoringWorkFactor(unsigned int bitlength)
Estimate work factor.
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
bool IsStrongProbablePrime(const Integer &n, const Integer &b)
Determine if a number is probably prime.
bool IsPrime(const Integer &p)
Verifies a number is probably prime.
static const Integer & Zero()
Integer representing 0.
Crypto++ library namespace.
const Integer & Square(const Integer &a) const
Square an element in the ring.
bool IsNegative() const
Determines if the Integer is negative.
bool RabinMillerTest(RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
Determine if a number is probably prime.
static const Integer & Two()
Integer representing 2.
bool IsFermatProbablePrime(const Integer &n, const Integer &b)
Determine if a number is probably prime.
unsigned int DiscreteLogWorkFactor(unsigned int bitlength)
Estimate work factor.
Performs modular arithmetic in Montgomery representation for increased speed.
@ PRIME
a number which is probabilistically prime
Integer MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
Classes for working with NameValuePairs.
Multiple precision integer with arithmetic operations.
Multiple precision integer with arithmetic operations.