はじめに
大きな素数(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の乱数生成とか、どうやってたか調べたら案外単純な方針だったことに驚きました。
そして、確実でないってことも・・・