# Prime numbers of the form $(2^k)p+1$, for a given prime $p$

Let $$p$$ be a prime. (say 256 bit)

Does there a exist a prime $$q$$ such that $$q = (2^k)p + 1$$, for a large $$k$$ (something like 256), if it does exist, is there a way to find out for which all $$k$$ such a $$q$$ exist.

[I know it exists for k =1, I am looking for a large $$k$$]

• Have you tried it? There are many primes. Bruteforce it and you will find examples. – corpsfini May 8 at 9:54

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 shared across multiple $$k$$.

An overly crude approximation of the probability that $$q=2^k\,p+1$$ is prime is that probability for an integer of same magnitude divisible by neither $$2$$ nor prime $$p$$, that is for $$p>2$$ and by the Prime Number Theorem roughly $$\displaystyle\frac{2-2/p}{\ln(q)}$$, which we can approximate as $$\displaystyle\frac2{\ln(p)+k\ln(2)}$$ for our large $$p$$. A numerical experiment shows that's in the right ballpark, but sizably too high.

A better analysis is that for random large prime $$p$$, and a small prime $$r>2$$, the quantity $$p\bmod r$$ is about uniformly distributed on $$[1,r)$$, thus $$2^k\,p\bmod r$$ also is, thus $$q=2^k\,p+1$$ is divisible by $$r$$ with probability $$1/(r-1)$$, rather than $$1/r$$ for a random integer. It thus contributes to reducing the probability to be prime by a factor $$\frac{r-2}{r-1}$$ rather than $$\frac{r-1}r$$. We can correct for that effect, yielding \begin{align} \Pr(2^k\,p+1\text{ is prime})&\approx\frac2{\ln(p)+k\ln(2)}\ \prod_{r\in\Bbb P,\ 2 since the product quickly converges to the twin prime constant $$C_2$$ (see A005597). That improved approximation is excellent for large $$p$$ as in the question.

We move to estimating the probability to find a prime $$2^k\,p+1$$ for a given $$p$$ and $$k\in[k_0,k_1]$$ with $$k_0$$ and $$k_1$$ close and commensurate with $$\log_2(p)$$.

As a crude approximation we can pretend that the probabilities to get a prime for one $$k$$ are independent of $$k$$, and approximate the probability that there is one prime $$2^k\,p+1$$ for $$k\in[k_0,k_1]$$ as the easily computed $$1-\prod_{k=k_0}^{k_1}\left(1-\frac{2\,C_2}{\ln(p)+k\ln(2)}\right)$$

For $$p\approx 2^{256}$$, $$k\in[248,264]$$ that gives a probability $$0.061403\ldots$$, meaning we'd need to test about one in $$16.286\ldots$$ primes $$p$$ to find a suitable one¹.

This approximation could likely be improved by taking into account that the probabilities for $$2^k\,p+1$$ to be divisible by a small prime $$r$$ for a given $$p$$ are strongly dependent on $$k$$, since $$2^k\bmod r$$ is a cyclic function of $$k$$, and worse of period $$(r-1)/s$$ often with $$s\ge2$$ (e.g. for $$r=7$$).

¹ What I got experimentally is close: $$\frac{3395526}{208621}=16.27\ldots$$ and $$\frac{2116707}{130242}=16.25\ldots$$ (scanning primes $$p$$ starting from $$\left\lceil\frac7{22}\,\pi\,2^{256}\right\rceil$$ and $$\left\lceil\frac{113}{355}\,\pi\,2^{256}\right\rceil$$ ).

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, 482719, 934909$$.

I say "known" because there are several smaller primes where it is unknown whether they are Sierpiński numbers (that is, whether all values of the form $$2^kq + 1$$ are composite).

And, no, I don't have any great insight on, given $$q$$, how to find a prime $$2^kq + 1$$ (apart from the obvious "try various values of $$k$$, and check if results in a prime"); I do see that you could speed up the search slightly by tracking $$q \bmod r$$ for small $$r$$ (which would allow you to quickly eliminate values $$2^kq + 1$$ which are multiples of $$r$$ without explicitly computing the modulus)

• Do these numbers has any usage in Cryptography? – kelalaka May 8 at 14:32
• @kelalaka: I don't know of any way they are used... – poncho May 8 at 14:34