/* * Copyright (c) 2002 Apple Computer, Inc. All rights reserved. * * @APPLE_LICENSE_HEADER_START@ * * The contents of this file constitute Original Code as defined in and * are subject to the Apple Public Source License Version 1.1 (the * "License"). You may not use this file except in compliance with the * License. Please obtain a copy of the License at * http://www.apple.com/publicsource and read it before using this file. * * This Original Code and all software distributed under the License are * distributed on an "AS IS" basis, WITHOUT WARRANTY OF ANY KIND, EITHER * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES, * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT. Please see the * License for the specific language governing rights and limitations * under the License. * * @APPLE_LICENSE_HEADER_END@ */ // nbtheory.h - written and placed in the public domain by Wei Dai #ifndef CRYPTOPP_NBTHEORY_H #define CRYPTOPP_NBTHEORY_H #include "integer.h" NAMESPACE_BEGIN(CryptoPP) // export a table of small primes extern const unsigned int maxPrimeTableSize; extern const word lastSmallPrime; extern unsigned int primeTableSize; extern word primeTable[]; // build up the table to maxPrimeTableSize void BuildPrimeTable(); // ************ primality testing **************** // generate a provable prime Integer MaurerProvablePrime(RandomNumberGenerator &rng, unsigned int bits); Integer MihailescuProvablePrime(RandomNumberGenerator &rng, unsigned int bits); bool IsSmallPrime(const Integer &p); // returns true if p is divisible by some prime less than bound // bound not be greater than the largest entry in the prime table bool TrialDivision(const Integer &p, unsigned bound); // returns true if p is NOT divisible by small primes bool SmallDivisorsTest(const Integer &p); // These is no reason to use these two, use the ones below instead bool IsFermatProbablePrime(const Integer &n, const Integer &b); bool IsLucasProbablePrime(const Integer &n); bool IsStrongProbablePrime(const Integer &n, const Integer &b); bool IsStrongLucasProbablePrime(const Integer &n); // Rabin-Miller primality test, i.e. repeating the strong probable prime test // for several rounds with random bases bool RabinMillerTest(RandomNumberGenerator &rng, const Integer &w, unsigned int rounds); // primality test, used to generate primes bool IsPrime(const Integer &p); // more reliable than IsPrime(), used to verify primes generated by others bool VerifyPrime(RandomNumberGenerator &rng, const Integer &p); // use a fast sieve to find the first probable prime in {x | p<=x<=max and x%mod==equiv} // returns true iff successful, value of p is undefined if no such prime exists bool FirstPrime(Integer &p, const Integer &max, const Integer &equiv, const Integer &mod); unsigned int PrimeSearchInterval(const Integer &max); // ********** other number theoretic functions ************ inline Integer GCD(const Integer &a, const Integer &b) {return Integer::Gcd(a,b);} inline Integer LCM(const Integer &a, const Integer &b) {return a/GCD(a,b)*b;} inline Integer EuclideanMultiplicativeInverse(const Integer &a, const Integer &b) {return a.InverseMod(b);} // use Chinese Remainder Theorem to calculate x given x mod p and x mod q Integer CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q); // use this one if u = inverse of p mod q has been precalculated Integer CRT(const Integer &xp, const Integer &p, const Integer &xq, const Integer &q, const Integer &u); // if b is prime, then Jacobi(a, b) returns 0 if a%b==0, 1 if a is quadratic residue mod b, -1 otherwise // check a number theory book for what Jacobi symbol means when b is not prime int Jacobi(const Integer &a, const Integer &b); // calculates the Lucas function V_e(p, 1) mod n Integer Lucas(const Integer &e, const Integer &p, const Integer &n); // calculates x such that m==Lucas(e, x, p*q), p q primes Integer InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q); // use this one if u=inverse of p mod q has been precalculated Integer InverseLucas(const Integer &e, const Integer &m, const Integer &p, const Integer &q, const Integer &u); inline Integer ModularExponentiation(const Integer &a, const Integer &e, const Integer &m) {return a_exp_b_mod_c(a, e, m);} // returns x such that x*x%p == a, p prime Integer ModularSquareRoot(const Integer &a, const Integer &p); // returns x such that a==ModularExponentiation(x, e, p*q), p q primes, // and e relatively prime to (p-1)*(q-1) Integer ModularRoot(const Integer &a, const Integer &e, const Integer &p, const Integer &q); // use this one if dp=d%(p-1), dq=d%(q-1), (d is inverse of e mod (p-1)*(q-1)) // and u=inverse of p mod q have been precalculated Integer ModularRoot(const Integer &a, const Integer &dp, const Integer &dq, const Integer &p, const Integer &q, const Integer &u); // find r1 and r2 such that ax^2 + bx + c == 0 (mod p) for x in {r1, r2}, p prime // returns true if solutions exist bool SolveModularQuadraticEquation(Integer &r1, Integer &r2, const Integer &a, const Integer &b, const Integer &c, const Integer &p); // returns log base 2 of estimated number of operations to calculate discrete log or factor a number unsigned int DiscreteLogWorkFactor(unsigned int bitlength); unsigned int FactoringWorkFactor(unsigned int bitlength); // ******************************************************** //! generator of prime numbers of special forms class PrimeAndGenerator { public: // generate a random prime p of the form 2*q+delta, where delta is 1 or -1 and q is also prime // Precondition: pbits > 5 // warning: this is slow! PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits); // generate a random prime p of the form 2*r*q+delta, where q is also prime // Precondition: qbits > 4 && pbits > qbits PrimeAndGenerator(signed int delta, RandomNumberGenerator &rng, unsigned int pbits, unsigned qbits); const Integer& Prime() const {return p;} const Integer& SubPrime() const {return q;} const Integer& Generator() const {return g;} private: Integer p, q, g; }; NAMESPACE_END #endif