Crypto++
8.3
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);
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;
821 unsigned i = e.BitCount();
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);
bool GetBit(size_t i) const
Provides the i-th bit of the Integer.
CRYPTOPP_DLL bool CRYPTOPP_API SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p)
Solve a Modular Quadratic Equation.
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 ->
CRYPTOPP_DLL Integer CRYPTOPP_API CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u)
Chinese Remainder Theorem.
const Integer & Subtract(const Integer &a, const Integer &b) const
Subtracts elements in the ring.
Classes and functions for number theoretic operations.
void swap(::SecBlock< T, A > &a, ::SecBlock< T, A > &b)
Swap two SecBlocks.
CRYPTOPP_DLL bool CRYPTOPP_API IsPrime(const Integer &p)
Verifies a number is probably prime.
CRYPTOPP_DLL bool CRYPTOPP_API IsFermatProbablePrime(const Integer &n, const Integer &b)
Determine if a number is probably prime.
Integer Squared() const
Multiply this integer by itself.
CRYPTOPP_DLL Integer CRYPTOPP_API MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
signed long ConvertToLong() const
Convert the Integer to Long.
Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b)
Calculate multiplicative inverse.
static const Integer &CRYPTOPP_API One()
Integer representing 1.
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 IsEven() const
Determines if the Integer is even parity.
CRYPTOPP_DLL bool CRYPTOPP_API FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod, const PrimeSelector *pSelector)
Finds a random prime of special form.
CRYPTOPP_DLL bool CRYPTOPP_API VerifyPrime(RandomNumberGenerator &rng, const Integer &p, unsigned int level=1)
Verifies a number is probably prime.
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 CRYPTOPP_API 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.
Interface for random number generators.
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongProbablePrime(const Integer &n, const Integer &b)
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.
CRYPTOPP_DLL bool CRYPTOPP_API IsStrongLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
CRYPTOPP_DLL bool CRYPTOPP_API SmallDivisorsTest(const Integer &p)
Tests whether a number is divisible by a small prime.
Application callback to signal suitability of a cabdidate prime.
Integer GCD(const Integer &a, const Integer &b)
Calculate the greatest common divisor.
CRYPTOPP_DLL bool CRYPTOPP_API RabinMillerTest(RandomNumberGenerator &rng, const Integer &n, unsigned int rounds)
Determine if a number is probably prime.
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.
CRYPTOPP_DLL unsigned int CRYPTOPP_API FactoringWorkFactor(unsigned int bitlength)
Estimate work factor.
CRYPTOPP_DLL bool CRYPTOPP_API TrialDivision(const Integer &p, unsigned bound)
Tests whether a number is divisible by a small prime.
unsigned int BitCount() const
Determines the number of bits required to represent the Integer.
CRYPTOPP_DLL int CRYPTOPP_API Jacobi(const Integer &a, const Integer &b)
Calculate the Jacobi symbol.
bool IsPositive() const
Determines if the Integer is positive.
CRYPTOPP_DLL unsigned int CRYPTOPP_API DiscreteLogWorkFactor(unsigned int bitlength)
Estimate work factor.
An invalid argument was detected.
unsigned int WordCount() const
Determines the number of words required to represent the Integer.
CRYPTOPP_DLL Integer CRYPTOPP_API InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u)
Calculate the inverse Lucas value.
static const Integer &CRYPTOPP_API Zero()
Integer representing 0.
Crypto++ library namespace.
CRYPTOPP_DLL const word16 *CRYPTOPP_API GetPrimeTable(unsigned int &size)
The Small Prime table.
bool IsNegative() const
Determines if the Integer is negative.
static const Integer &CRYPTOPP_API Two()
Integer representing 2.
CRYPTOPP_DLL Integer CRYPTOPP_API ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u)
Extract a modular root.
Performs modular arithmetic in Montgomery representation for increased speed.
@ PRIME
a number which is probabilistically prime
Classes for working with NameValuePairs.
Multiple precision integer with arithmetic operations.
CRYPTOPP_DLL bool CRYPTOPP_API IsLucasProbablePrime(const Integer &n)
Determine if a number is probably prime.
Multiple precision integer with arithmetic operations.
CRYPTOPP_DLL Integer CRYPTOPP_API Lucas(const Integer &e, const Integer &p, const Integer &n)
Calculate the Lucas value.
CRYPTOPP_DLL Integer CRYPTOPP_API MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits)
Generates a provable prime.
CRYPTOPP_DLL bool CRYPTOPP_API IsSmallPrime(const Integer &p)
Tests whether a number is a small prime.
CRYPTOPP_DLL Integer CRYPTOPP_API ModularSquareRoot(const Integer &a, const Integer &p)
Extract a modular square root.