PrimesFinder.h File Reference

This file provides static functions to search for integers \(m\) that are prime and for which the integer \(r = (m^k-1)/(m-1)\) is also prime for a given \(k\), and possibly for which \((m-1)/2\) is also prime. More...

Namespaces
namespace	LatMRG
	This has to be redone in a way similar to Rank1Lattice.

Functions
template<typename Int>
static void	LatMRG::findPrime (int64_t e, int64_t s, bool facto, std::ostream &fout, const int64_t RMtrials=200)
	Finds and prints the \(s\) largest prime integers \(m < 2^e\).
template<typename Int>
static void	LatMRG::findPrime (int64_t k, int64_t e, int64_t s, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200)
	Finds the \(s\) largest prime integers \(m<2^e\) for which \(r = (m^k-1)/(m-1)\) is also prime.
template<typename Int>
static void	LatMRG::findPrime (int64_t k, int64_t e, int64_t c1, int64_t c2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200)
	Finds all integers \(m\), in \(2^e + c_1 \le m \le 2^e + c_2\), such that \(m\) and \(r = (m^k-1)/(m-1)\) are prime.
template<typename Int>
static void	LatMRG::findPrime (int64_t k, int64_t e, int64_t s, const Int &S1, const Int &S2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200)
	This is the general purpose function, called by the other ones.
static void	LatMRG::writeHeader (int64_t k, int64_t e, int64_t c1, int64_t c2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials=200)
	Writes the search parameters to the stream fout.
template<typename Int>
static void	LatMRG::nextM (Int &m)
template<typename Int>
void	LatMRG::findPrime (int64_t k, int64_t e, int64_t s, const Int &S1, const Int &S2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials)
	This is the general purpose function, called by the other ones.
template<typename Int>
void	LatMRG::findPrime (int64_t e, int64_t s, bool facto, std::ostream &fout, const int64_t RMtrials)
	Finds and prints the \(s\) largest prime integers \(m < 2^e\).
template<typename Int>
void	LatMRG::findPrime (int64_t k, int64_t e, int64_t s, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials)
	Finds the \(s\) largest prime integers \(m<2^e\) for which \(r = (m^k-1)/(m-1)\) is also prime.
template<typename Int>
void	LatMRG::findPrime (int64_t k, int64_t e, int64_t c1, int64_t c2, bool safe, bool facto, std::ostream &fout, const int64_t RMtrials)
	Finds all integers \(m\), in \(2^e + c_1 \le m \le 2^e + c_2\), such that \(m\) and \(r = (m^k-1)/(m-1)\) are prime.

Detailed Description

This file provides static functions to search for integers \(m\) that are prime and for which the integer \(r = (m^k-1)/(m-1)\) is also prime for a given \(k\), and possibly for which \((m-1)/2\) is also prime.

For \(k=1\), we have \(r=1\), so the first condition is removed. These functions use solely Rabin-Miller probabilistic primality tests with RMtrials trials. If facto is true, the factorization of \(m-1\) is also computed and returned. Each function writes its results on the given stream fout.

We could possibly use deterministic primality tests when \(m\) and \(k\) are small, because it is possible to do everything this class does with efficient deterministic tests for integers \( < 2^{64}\); see https://math.stackexchange.com/questions/2481148/primality-testing-for-64-bit-numbers. However \(r\) is typically much larger than \(2^{64}\) in actual cases.