# Generating a large prime, $p$, such that $2^{k}$ divides $p-1$ for some $k<p$

I want to generate a prime $p$ of a certain size $2^{k}$ divides $p-1$ for some $k < p$. Is there any trick that I can use to do that instead of a brute-force search?

-
mathoverflow.net/questions/115560/… –  user51427 Dec 6 '12 at 19:01
Not really! You need to use an efficient compositeness test, certainly must not check for compositeness by looking for divisors. A "probabilistic" test sounds good. –  André Nicolas Dec 6 '12 at 19:03