safeprime

Documentation

Overview

Package safeprime computes safe primes, i.e. primes of the form 2p+1 where p is also prime.

Index

• func Generate(bitsize int, stop chan struct{}) (*big.Int, error)
• func GenerateConcurrent(bitsize int, stop chan struct{}) (<-chan *big.Int, <-chan error)
• func ProbablySafePrime(x *big.Int, n int) bool

Functions

func Generate

func Generate(bitsize int, stop chan struct{}) (*big.Int, error)

Generate a safe prime of the given size, using the fact that:

If (and only if) q is prime and 2^(2q) = 1 mod (2q+1), then 2q+1 is a safe prime.

The algorithm works as follows:

• We take a random bigint q;
• We do some bit manipulation to ensure that q has the right size and is odd;
• We sieve out some small prime factors: We discard q if it is a multiple of any prime below and including 53;
• Then, if the above formula holds and q is prime, we return 2q+1.

(See https://groups.google.com/group/sci.crypt/msg/34c4abf63568a8eb and below.)

In order to cancel the generation algorithm, send a struct{} on the stop parameter or close() it. (Passing nil is allowed; then the algorithm cannot be cancelled).

func GenerateConcurrent

func GenerateConcurrent(bitsize int, stop chan struct{}) (<-chan *big.Int, <-chan error)

GenerateConcurrent concurrently and continuously generates safe primes on all CPU cores, until the stop channel receives a struct or is closed. If an error is encountered, generation is stopped in all goroutines, and the error is sent on the second return parameter.

func ProbablySafePrime

func ProbablySafePrime(x *big.Int, n int) bool

ProbablySafePrime reports whether x is probably a safe prime, by calling big.Int.ProbablyPrime(n) on x as well as on (x-1)/2.

If x is a safe prime, ProbablySafePrime returns true. If x is chosen randomly and not a safe prime, ProbablyPrime probably returns false.