This is a prime search project. It currently searches for Proth Primes.
How does it work?
The project uses the Proth prime test to search for prime numbers of the form \(k \cdot 2^n + 1\), where \(k\) is an odd integer and \(2^n > k\). To test whether a number of this form is a Proth prime, we use the following method:
A Proth number \(p\) is prime if and only if there exists an integer \(a\) such that \(a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p)\).
The algorithm iterates through possible values of \(k\) and \(n\), performing this test for each combination.
Mathematical Explanation
Given \(p = k \cdot 2^n + 1\) and \(k < 2^n\), we check if:
\[ a^{\frac{p-1}{2}} \equiv -1 \ (\text{mod} \ p) \]
If the condition holds for some \(a\), then \(p\) is a Proth prime.
If \(a^{\frac{p-1}{2}} (\text{mod} \ p)\) is not \(1\) or \(p-1\), then \(p\) is not a Proth prime.
Example
For example, let’s consider \(k = 5\) and \(n = 3\):
\[ p = 5 \cdot 2^3 + 1 = 3 \cdot 8 + 1 = 41 \]
We need to check if there exists an \(a\) such that:
\[ a^{20} \equiv -1 \ (\text{mod} \ 41) \]
After testing various values of \(a\), we find that \(a = 3\) satisfies the condition, so 41 is a Proth prime.
Download
Do this on your terminal:
git clone https://github.com/StevenJinyanCheng/prime-search.git
pip install gmpy2 tqdm
cd prime-search
python proth.py