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?

  • 2
    $\begingroup$ 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. $\endgroup$
    – fgrieu
    Sep 22 '21 at 10:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.