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

问题描述：

我以实现RSA为例。几个星期前，它似乎工作正常。rand.Prime（rand.Reader，3072）需要很长时间才能执行

然而，现在，键的生成需要很长时间（> 10秒）。我已经缩小到线：

import "crypto/rand" 

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

为什么这会花费大量的时间？

为什么？你认为应该花多长时间？像Miller-Rabin这样的概率素性测试必须执行许多次数模幂运算。它非常昂贵，素数的分布意味着它有时会很快找到一个素数，有时需要更长的时间。 –

答

除了根据crypto/rand文档进行素性测试的计算成本之外，这些数字来源于“密码安全的伪随机数生成器”。这种随机性来源might be slow，取决于您的环境。

这可能是为什么crypto/prime消耗io.Reader，所以我们可以喂它另一个随机来源。 e.g.：

package main 

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

// Adapted from http://*.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) 
}

即便如此，试图产生3000位的素数确实出现了天生就慢（把我的机器上也几秒钟）由于素性测试的成本，如詹姆斯·诺克斯·波尔克建议。

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

相关推荐