1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
|
package main
import (
"math/big"
)
var (
_D = []*big.Int{big.NewInt(3), big.NewInt(4), big.NewInt(7), big.NewInt(8), big.NewInt(11), big.NewInt(19), big.NewInt(43), big.NewInt(67), big.NewInt(163)}
one = big.NewInt(1)
two = big.NewInt(2)
)
func test(t *big.Int, q *big.Int) bool {
for _, d := range _D {
q.Exp(t, two, nil)
q.Add(q, d)
if q.Bits()[0]&3 != 0 {
continue
}
q.Rsh(q, 2)
// TODO: check if q is a prime power
if q.ProbablyPrime(20) {
return true
}
}
return false
}
func nextSiec(M *big.Int) (q, t *big.Int) {
t = new(big.Int)
q = new(big.Int)
t.Lsh(M, 2)
t.Sub(t, _D[8])
t.Sqrt(t)
t.Sub(t, one)
for {
if test(t, q) && q.Cmp(M) > 0 {
return
}
t.Add(t, one)
}
}
func prevSiec(M *big.Int) (q, t *big.Int) {
t = new(big.Int)
q = new(big.Int)
t.Lsh(M, 2)
t.Sub(t, _D[0])
t.Sqrt(t)
t.Add(t, one)
for {
if test(t, q) && q.Cmp(M) < 0 {
return
}
t.Sub(t, one)
}
}
|
