nbtheory.h

来自「各种加密算法的集合」· C头文件 代码 · 共 65 行

#ifndef NBTHEORY_H 
#define NBTHEORY_H 

#include "bignum.h" 

// the following functions do not depend on the details of bignum implementation 

// greatest common divisor 
bignum Gcd(const bignum &amt;a, const bignum &amt;b); 

// multiplicative inverse of a modulus m 
bignum Inverse(const bignum &amt;a, const bignum &amt;m); 

boolean IsSmallPrime(const bignum &amt;p); 

boolean SmallDivisorsTest(const bignum &amt;p); 

// use Fermat's Little Theorem with a = {first rounds number of primes} to test for primality 
boolean FermatTest(const bignum &amt;p, unsigned int rounds); 

// one round of the Rabin-Miller primality test 
boolean RabinMillerTest(RandomNumberGenerator &amt;rng, const bignum &amt;w, unsigned int rounds); 

// small divisors test + Fermat test 
// should be good enough for most practical purposes 
// but feel free to change this to suit your fancy 
inline boolean IsPrime(const bignum &amt;p) 
{ 
return (IsSmallPrime(p) || (SmallDivisorsTest(p) &amt;&amt; FermatTest(p, 2))); 
} 

// use a fast sieve to find the next prime after p 
// returns TRUE iff successful 
boolean NextPrime(bignum &amt;p, const bignum &amt;max, boolean blumInt=FALSE); 

// exponentiation using the Chinese Remainder Theorem 
bignum a_exp_b_mod_pq(const bignum &amt;a, const bignum &amt;ep, const bignum &amt;eq, 
const bignum &amt;p, const bignum &amt;q, const bignum &amt;u); 

class PrimeAndGenerator 
{ 
public: 
// generate random prime of pbits (with maximal subprime) and primitive g 
PrimeAndGenerator(RandomNumberGenerator &amt;rng, unsigned int pbits); 
// generate random prime of pbits (with subprime of qbits) and g of order q 
PrimeAndGenerator(RandomNumberGenerator &amt;rng, unsigned int pbits, unsigned qbits); 

const bignum&amt; Prime() const {return p;} 
const bignum&amt; SubPrime() const {return q;} 
const bignum&amt; Generator() const {return g;} 

private: 
bignum p, q, g; 
}; 

#endif