Is there a method to generate a large prime number with factorization p - 1?

Question

Mathematics

Hello!
There is a task - to build a large prime number (of the order of 2-3k bits) with a pre-known factorization p - 1.
This is necessary to find primitive roots (I'm trying to implement the Diffie-Hellman protocol)

Answer 1

Inventing the wheel and learning how it all works doesn't require large numbers to be generated.
If you really want to, then check it out . Well, either Atkin's Sieve , well, or the same Eratosthenes .
This is the first.
Second: never, never, never, never, never try to implement cryptographic algorithms for any purpose other than educational. Never use your own implementation to protect anything important. I don't know you, of course, but you most likely don't have a doctorate in mathematics and several years of experience in cryptography and cryptanalysis.

Answer 2

You can approach this: Generate two random prime numbers of length n/2 bits (Generate a random number until you get a prime). Then multiply them, add 1 and check that the result is also simple.
To do this, you need to be able to relatively quickly check that the number is prime. You can use the Miller-Rabin method . It is probabilistic, but by increasing the number of iterations, an arbitrarily small error probability can be achieved.