# Find a prime $p$ vulnerable to pohlig-Hellman

I need to find a prime number $$p$$ with the following constraints:

• $$p$$ is at least $$1000$$ bits long
• $$p-1$$ is a smooth number with the largest factor below $$1000$$
• any factor of $$p-1$$ can be present multiple times

Does this number exist? and if yes, does there is an algorithm to find it?

• Welcome to crypto-SE. This looks like homework, thus I'll only give a (strong) hint: propose a simple algorithm that constructs randomly-seeded $r$ with the characteristics asked for $p-1$ (including size), ignoring for now the requirement that $p$ is prime; then derive using the Prime Number Theorem a plausible lower bound for the probability that $p=r+1$ is prime, and from that a rough plausible higher bound of the expected cost of the now obvious probabilistic algorithm. It's smart to answer your own question.
– fgrieu
Sep 22 at 10:00