Quantum++  v1.0-rc2
A modern C++11 quantum computing library
number_theory.h File Reference

Number theory functions. More...

This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Namespaces

 qpp
 Quantum++ main namespace.
 

Functions

std::vector< int > qpp::x2contfrac (double x, idx N, idx cut=1e5)
 Simple continued fraction expansion. More...
 
double qpp::contfrac2x (const std::vector< int > &cf, idx N=idx(-1))
 Real representation of a simple continued fraction. More...
 
bigint qpp::gcd (bigint a, bigint b)
 Greatest common divisor of two integers. More...
 
bigint qpp::gcd (const std::vector< bigint > &as)
 Greatest common divisor of a list of integers. More...
 
bigint qpp::lcm (bigint a, bigint b)
 Least common multiple of two integers. More...
 
bigint qpp::lcm (const std::vector< bigint > &as)
 Least common multiple of a list of integers. More...
 
std::vector< idx > qpp::invperm (const std::vector< idx > &perm)
 Inverse permutation. More...
 
std::vector< idx > qpp::compperm (const std::vector< idx > &perm, const std::vector< idx > &sigma)
 Compose permutations. More...
 
std::vector< bigint > qpp::factors (bigint a)
 Prime factor decomposition. More...
 
bigint qpp::modmul (bigint a, bigint b, bigint p)
 Modular multiplication without overflow. More...
 
bigint qpp::modpow (bigint a, bigint n, bigint p)
 Fast integer power modulo p based on the SQUARE-AND-MULTIPLY algorithm. More...
 
std::tuple< bigint, bigint, bigint > qpp::egcd (bigint a, bigint b)
 Extended greatest common divisor of two integers. More...
 
bigint qpp::modinv (bigint a, bigint p)
 Modular inverse of a mod p. More...
 
bool qpp::isprime (bigint p, idx k=80)
 Primality test based on the Miller-Rabin's algorithm. More...
 
bigint qpp::randprime (bigint a, bigint b, idx N=1000)
 Generates a random big prime uniformly distributed in the interval [a, b]. More...
 

Detailed Description

Number theory functions.