Ask Your Question
3

Randomly generate a safe prime of given length

asked 2018-12-24 00:32:36 +0100

panther gravatar image

A prime p is said to be safe prime if (p-1)/2 is also a prime. Safe primes are heavily used in cryptography. In order to generate a random prime of 512 bits, I use

random_prime(2^512-1, false, 2^511)

How to randomly generate a safe prime of given length?

edit retag flag offensive close merge delete

2 Answers

Sort by ยป oldest newest most voted
3

answered 2018-12-24 01:10:01 +0100

tmonteil gravatar image

updated 2022-04-30 09:23:56 +0100

You can use a rejection method: try a new random prime until you get a safe one:

sage: def rdp(nbits=512):
....:     while True:
....:         p = random_prime(2^nbits-1, false, 2^(nbits-1))
....:         if ZZ((p-1)/2).is_prime():
....:             return p
....:         
sage: rdp()
9075892275451579482861175762932106084253268411540277039314929550059578374557168263115660009649748089090540343402740578371326513035684052420493647284687893

For other number of bits:

sage: rdp(200)
1011992113066581800000651861935373321407012277464235251049677
edit flag offensive delete link more

Comments

Thanks for your snippet, but a typo/bug! Must be: "ZZ((p-1)/2).is_prime()". Not plus. Minus.

Dennis Yurichev gravatar imageDennis Yurichev ( 2022-04-25 13:59:32 +0100 )edit

Fixed, sorry for the typo.

tmonteil gravatar imagetmonteil ( 2022-04-30 09:24:08 +0100 )edit
0

answered 2019-04-05 20:16:39 +0100

A much faster method is to generate a random integer p, to try dividing both p and (p-1)/2 by the first 100000 primes (just generate a table with those primes, using any suitable method) and reject p as soon as it is found that either p or (p-1)/2 has a divisor. If this is successful, then use the Miller-Rabin test on p and on (p-2)/2, using the first 10 primes as witnesses.

This is much faster because most p value will be rejected quickly, while first finding a prime p is much work and this work is useless because most of the time you can quickly find that (p-1)/2 is NOT prime. Better evaluate p and (p-1)/2 together, not focusing on one of them while ignoring the other one for a long time.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

1 follower

Stats

Asked: 2018-12-24 00:32:36 +0100

Seen: 6,826 times

Last updated: Apr 30 '22