New answers tagged safe-prime
3
This problem has been studied already; see this Wikipedia article.
Does there a exist a prime $q$ such that $p = 2^kq + 1$ is also prime?
A number $q$ such that $p$ is never prime is called a Sierpiński number; such numbers do exist, and some of them are prime. The smallest known such prime is $q = 271129$; the next known ones are $322523, 327739, ...
5
There is numerical evidence that for the vast majority of primes $p$, there exists $k$ making $q=2^k\,p+1$ prime. See first exceptions in A137715.
The only practical way I see to find which $(p,k)$ make $q=2^k\,p+1$ prime in the question's context is testing $q$ for primality using a fast test. As noted in the other answer, sieving for small primes can be ...
Top 50 recent answers are included
