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
|
package dilithium
// Returns a y with y < 2q and y = x mod q.
// Note that in general *not*: ReduceLe2Q(ReduceLe2Q(x)) == x.
func ReduceLe2Q(x uint32) uint32 {
// Note 2²³ = 2¹³ - 1 mod q. So, writing x = x₁ 2²³ + x₂ with x₂ < 2²³
// and x₁ < 2⁹, we have x = y (mod q) where
// y = x₂ + x₁ 2¹³ - x₁ ≤ 2²³ + 2¹³ < 2q.
x1 := x >> 23
x2 := x & 0x7FFFFF // 2²³-1
return x2 + (x1 << 13) - x1
}
// Returns x mod q.
func modQ(x uint32) uint32 {
return le2qModQ(ReduceLe2Q(x))
}
// For x R ≤ q 2³², find y ≤ 2q with y = x mod q.
func montReduceLe2Q(x uint64) uint32 {
// Qinv = 4236238847 = -(q⁻¹) mod 2³²
m := (x * Qinv) & 0xffffffff
return uint32((x + m*uint64(Q)) >> 32)
}
// Returns x mod q for 0 ≤ x < 2q.
func le2qModQ(x uint32) uint32 {
x -= Q
mask := uint32(int32(x) >> 31) // mask is 2³²-1 if x was neg.; 0 otherwise
return x + (mask & Q)
}
// Splits 0 ≤ a < Q into a0 and a1 with a = a1*2ᴰ + a0
// and -2ᴰ⁻¹ < a0 < 2ᴰ⁻¹. Returns a0 + Q and a1.
func power2round(a uint32) (a0plusQ, a1 uint32) {
// We effectively compute a0 = a mod± 2ᵈ
// and a1 = (a - a0) / 2ᵈ.
a0 := a & ((1 << D) - 1) // a mod 2ᵈ
// a0 is one of 0, 1, ..., 2ᵈ⁻¹-1, 2ᵈ⁻¹, 2ᵈ⁻¹+1, ..., 2ᵈ-1
a0 -= (1 << (D - 1)) + 1
// now a0 is -2ᵈ⁻¹-1, -2ᵈ⁻¹, ..., -2, -1, 0, ..., 2ᵈ⁻¹-2
// Next, we add 2ᴰ to those a0 that are negative (seen as int32).
a0 += uint32(int32(a0)>>31) & (1 << D)
// now a0 is 2ᵈ⁻¹-1, 2ᵈ⁻¹, ..., 2ᵈ-2, 2ᵈ-1, 0, ..., 2ᵈ⁻¹-2
a0 -= (1 << (D - 1)) - 1
// now a0 id 0, 1, 2, ..., 2ᵈ⁻¹-1, 2ᵈ⁻¹-1, -2ᵈ⁻¹-1, ...
// which is what we want.
a0plusQ = Q + a0
a1 = (a - a0) >> D
return
}
|
