大きな素数（かもしれない）

はじめに

大きな素数(1024bitより大きい)を求める必要がある場合を考えました。
RSA暗号 - Wikipediaなどをみると、乱数を生成して、それが素数かどうか調べるのが速いそうです。
ただし、ガチ計算だと時間がかかりすぎるので、確率的素数判定法で素数判定をおこないます。

ミラー–ラビン素数判定法（Miller–Rabin primality test）

ミラー–ラビン素数判定法 - Wikipediaによると、内部で仕様している$k$から$4^{-k}$の確率で合成数を素数と誤認識してしまうようです。
$k$をある程度大きくしておけば、黙認できるレベルになるそうです。

func isProbablyPrime(n *big.Int) bool {
    ONE := big.NewInt(1)
    TWO := big.NewInt(2)
    if n.Cmp(ONE) <= 0 {
        return false
    }
    // if n == 2 then prime
    if n.Cmp(TWO) == 0 {
        return true
    }
    // odd check
    if n.Bit(0) == 0 {
        return false
    }
    // n-1 = 2^s * d
    d := new(big.Int).Sub(n, ONE)
    s := big.NewInt(0)
    for d.Bit(0) == 0 {
        d.Rsh(d, 1)
        s.Add(s, ONE)
    }
    k := 1024
    nm1 := new(big.Int).Sub(n, ONE)
    for i := 0; i < k; i++ {
        // a in [1,n-1]
        a := Rnd(nm1)
        a.Add(a, ONE)
        // a^{d} mod n == 1
        t := new(big.Int).Exp(a, d, n)
        if t.Cmp(ONE) == 0 {
            continue
        }
        flg := false
        // r in [0,s-1] , a^{2^rd} mod n == -1
        // a^{2^0 * d} , a^{2^1 * d} , a^{2^2 * d} , .... , a^{2^(s-1) * d}
        for r := big.NewInt(0); r.Cmp(s) < 0; r.Add(r, ONE) {
            if t.Cmp(nm1) == 0 {
                flg = true
                break
            }
            t.Exp(t, TWO, n)
        }
        if !flg {
            return false
        }
    }
    return true
}

// Rnd returns a random number less than n
func Rnd(n *big.Int) *big.Int {
    tmp := make([]byte, len(n.Bytes()))
    rand.Read(tmp)
    return new(big.Int).Mod(new(big.Int).SetBytes(tmp), n)
}

素数生成

bit数の素数を生成するプログラムを作成します。
単純に乱数生成して、それが素数かを判定するだけのプログラムです。

func probablyPrime(bits int) *big.Int {
    max := new(big.Int).Exp(big.NewInt(2), big.NewInt(int64(bits)), nil)
    p := big.NewInt(0)
    for !isProbablyPrime(p) {
        p = Rnd(max)
        for p.BitLen() != bits {
            p = Rnd(max)
        }
    }
    return p
}

さいごに

RSAの乱数生成とか、どうやってたか調べたら案外単純な方針だったことに驚きました。
そして、確実でないってことも・・・