Effective implementation of algorithms (Master Thesis)
Effective and error-free implementation of algorithms
|
#include <primes_fast.h>
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") |
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))
PowerModImpl | implementation of modular exponentiation |
typedef long long int math::primes::PrimesFast_< PowerModImpl >::BaseType [private] |
Base type for our computation, at least 50 bits
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.)
p | number to test, should be positive |
math::primes::PrimesFast_< PowerModImpl >::STATIC_ASSERT | ( | std::numeric_limits< BaseType >::digits | , |
50 | , | ||
"We need at least 50-bit integer as a base tyep" | |||
) | [private] |