rand.Prime（rand.Reader，3072）需要很长时间才能执行

I implemented RSA as an example. Several weeks ago, it seemed to work fine.

Now, however, the generation of keys takes a long time (>10 seconds). I've narrowed it down to the line:

import "crypto/rand"

p, _ := rand.Prime(rand.Reader, 3072)

Why would this take a significant amount of time?

Besides the computational cost of doing primality testing, according to the crypto/rand documentation, the numbers are sourced from a "cryptographically secure pseudorandom number generator". Such sources of randomness might be slow, depending on your environment.

That's probably why crypto/prime consumes an io.Reader, so that we can feed it another source of randomness. e.g.:

package main

import (
    cRand "crypto/rand"
    "fmt"
    mRand "math/rand"
)

// Adapted from http://stackoverflow.com/questions/12771930/
type randReader struct {
    src mRand.Source
}

func newRandReader() *randReader {
    // FIXME: source the seed from crypto/rand instead.
    return &randReader{mRand.NewSource(42)}
}

func (r *randReader) Read(p []byte) (n int, err error) {
    for i := range p {
        p[i] = byte(r.src.Int63() & 0xff)
    }
    return len(p), nil
}

func main() {
    fmt.Println("Hello, playground")
    r := newRandReader()
    p, _ := cRand.Prime(r, 300)
    fmt.Println(p)
}

Even with this, trying to generate 3000-bit primes does appear to be inherently slow (takes several seconds on my machine too) due to the cost of primality testing, as James K Polk suggests.