5
$\begingroup$

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$]

$\endgroup$
1
  • $\begingroup$ Have you tried it? There are many primes. Bruteforce it and you will find examples. $\endgroup$
    – user69015
    May 8, 2020 at 9:54

2 Answers 2

5
$\begingroup$

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<r<\sqrt p}\frac{r\,(r-2)}{(r-1)^2}\\ &\approx\frac{2\,C_2}{\ln(p)+k\ln(2)}\ \text{ with }C_2=0.66016\ldots \end{align}$$ 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$ ).

$\endgroup$
3
$\begingroup$

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)

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.