Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
math::primes::PrimesFast_< PowerModImpl > Class Template Reference

#include <primes_fast.h>

List of all members.

Static Public Member Functions

static bool isPrime (BaseType p)

Private Types

typedef long long int BaseType

Private Member Functions

 STATIC_ASSERT (std::numeric_limits< BaseType >::digits > 50,"We need at least 50-bit integer as a base tyep")

Detailed Description

template<class PowerModImpl>
class math::primes::PrimesFast_< PowerModImpl >

Deterministic version of Miller-Rabbin primality test.

The implementation is based on article ON STRONG PSEUDOPRIMES TO SEVERAL BASES by GERHARD JAESCHKE It's running time is O(log(n)^2) (multiplication is supposed to be O(log n))

Parameters:
PowerModImplimplementation of modular exponentiation
Precondition:
  • PowerModImpl have functions
    • powermod(base, exponent, modulus)
    • multmod(a, b, modulus)
  • long long int is 64bit

Member Typedef Documentation

template<class PowerModImpl >
typedef long long int math::primes::PrimesFast_< PowerModImpl >::BaseType [private]

Base type for our computation, at least 50 bits


Member Function Documentation

template<class PowerModImpl >
static bool math::primes::PrimesFast_< PowerModImpl >::isPrime ( BaseType  p) [inline, static]

Miller-Rabin test with fixed withesses which is correct up to 3*10^14. (but the implementation is only for integers.)

Parameters:
pnumber to test, should be positive
Returns:
true iff p is prime
template<class PowerModImpl >
math::primes::PrimesFast_< PowerModImpl >::STATIC_ASSERT ( std::numeric_limits< BaseType >::digits  ,
50  ,
"We need at least 50-bit integer as a base tyep"   
) [private]

The documentation for this class was generated from the following file:
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Defines