-
Notifications
You must be signed in to change notification settings - Fork 1
/
primes.go
171 lines (114 loc) · 3.52 KB
/
primes.go
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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
package ring
import (
"fmt"
"math/bits"
)
// IsPrime applies the Baillie-PSW, which is 100% accurate for numbers bellow 2^64.
func IsPrime(x uint64) bool {
return NewUint(x).ProbablyPrime(0)
}
// GenerateNTTPrimes generates n NthRoot NTT friendly primes given logQ = size of the primes.
// It will return all the appropriate primes, up to the number of n, with the
// best available deviation from the base power of 2 for the given n.
func GenerateNTTPrimes(logQ, NthRoot, n int) (primes []uint64) {
if logQ > 61 {
panic("logQ must be between 1 and 61")
}
if logQ == 61 {
return GenerateNTTPrimesP(logQ, NthRoot, n)
}
return GenerateNTTPrimesQ(logQ, NthRoot, n)
}
// NextNTTPrime returns the next NthRoot NTT prime after q.
// The input q must be itself an NTT prime for the given NthRoot.
func NextNTTPrime(q uint64, NthRoot int) (qNext uint64, err error) {
qNext = q + uint64(NthRoot)
for !IsPrime(qNext) {
qNext += uint64(NthRoot)
if bits.Len64(qNext) > 61 {
return 0, fmt.Errorf("next NTT prime exceeds the maximum bit-size of 61 bits")
}
}
return qNext, nil
}
// PreviousNTTPrime returns the previous NthRoot NTT prime after q.
// The input q must be itself an NTT prime for the given NthRoot.
func PreviousNTTPrime(q uint64, NthRoot int) (qPrev uint64, err error) {
if q < uint64(NthRoot) {
return 0, fmt.Errorf("previous NTT prime is smaller than NthRoot")
}
qPrev = q - uint64(NthRoot)
for !IsPrime(qPrev) {
if q < uint64(NthRoot) {
return 0, fmt.Errorf("previous NTT prime is smaller than NthRoot")
}
qPrev -= uint64(NthRoot)
}
return qPrev, nil
}
// GenerateNTTPrimesQ generates "levels" different NthRoot NTT-friendly
// primes starting from 2**LogQ and alternating between upward and downward.
func GenerateNTTPrimesQ(logQ, NthRoot, levels int) (primes []uint64) {
var nextPrime, previousPrime, Qpow2 uint64
var checkfornextprime, checkforpreviousprime bool
primes = []uint64{}
Qpow2 = uint64(1 << logQ)
nextPrime = Qpow2 + 1
previousPrime = Qpow2 + 1
checkfornextprime = true
checkforpreviousprime = true
for {
if !(checkfornextprime || checkforpreviousprime) {
panic("generateNTTPrimesQ error: cannot generate enough primes for the given parameters")
}
if checkfornextprime {
if nextPrime > 0xffffffffffffffff-uint64(NthRoot) {
checkfornextprime = false
} else {
nextPrime += uint64(NthRoot)
if IsPrime(nextPrime) {
primes = append(primes, nextPrime)
if len(primes) == levels {
return
}
}
}
}
if checkforpreviousprime {
if previousPrime < uint64(NthRoot) {
checkforpreviousprime = false
} else {
previousPrime -= uint64(NthRoot)
if IsPrime(previousPrime) {
primes = append(primes, previousPrime)
if len(primes) == levels {
return
}
}
}
}
}
}
// GenerateNTTPrimesP generates "levels" different NthRoot NTT-friendly
// primes starting from 2**LogP and downward.
// Special case were primes close to 2^{LogP} but with a smaller bit-size than LogP are sought.
func GenerateNTTPrimesP(logP, NthRoot, n int) (primes []uint64) {
var x, Ppow2 uint64
primes = []uint64{}
Ppow2 = uint64(1 << logP)
x = Ppow2 + 1
for {
// We start by subtracting 2N to ensure that the prime bit-length is smaller than LogP
if x > uint64(NthRoot) {
x -= uint64(NthRoot)
if IsPrime(x) {
primes = append(primes, x)
if len(primes) == n {
return primes
}
}
} else {
panic("generateNTTPrimesP error: cannot generate enough primes for the given parameters")
}
}
}