0

I generated a random prime $p$. Now I want to find a random prime with a fixed size of $256$ Bits which divides $p - 1$. $p$ has $3072$ Bits, so I can't just try it out.

Klangen
  • 5,075
91378246
  • 101
  • 3
    Do you know that such a prime exists in your case? Usually it won't. – quid Jan 26 '19 at 19:30
  • No, I don't, but I hoped some one knows an algorithm, which could tell me if one exists and, if so, which prime it is. – 91378246 Jan 26 '19 at 19:34
  • 2
    @91378246: such algorithm would have solved the factorization problem and broken RSA. Given some large integer (integers of the form $p-1$ are not really special) there is no simple (polynomial) way to get a divisor, but you may employ sieve methods (like the quadratic sieve) to find divisors in some range, then a primality test (AKS is polynomial, for instance) to select prime divisors. Anyway, it will be computationally expensive. – Jack D'Aurizio Jan 27 '19 at 00:47
  • Thank you very much, I will look into that. – 91378246 Jan 27 '19 at 12:45

0 Answers0