1 package common
2 3 // Given -2¹⁵ q ≤ x < 2¹⁵ q, returns -q < y < q with x 2⁻¹⁶ = y (mod q).
4 func montReduce(x int32) int16 {
5 // This is Montgomery reduction with R=2¹⁶.
6 //
7 // Note gcd(2¹⁶, q) = 1 as q is prime. Write q' := 62209 = q⁻¹ mod R.
8 // First we compute
9 //
10 // m := ((x mod R) q') mod R
11 // = x q' mod R
12 // = int16(x q')
13 // = int16(int32(x) * int32(q'))
14 //
15 // Note that x q' might be as big as 2³² and could overflow the int32
16 // multiplication in the last line. However for any int32s a and b,
17 // we have int32(int64(a)*int64(b)) = int32(a*b) and so the result is ok.
18 m := int16(x * 62209)
19 20 // Note that x - m q is divisible by R; indeed modulo R we have
21 //
22 // x - m q ≡ x - x q' q ≡ x - x q⁻¹ q ≡ x - x = 0.
23 //
24 // We return y := (x - m q) / R. Note that y is indeed correct as
25 // modulo q we have
26 //
27 // y ≡ x R⁻¹ - m q R⁻¹ = x R⁻¹
28 //
29 // and as both 2¹⁵ q ≤ m q, x < 2¹⁵ q, we have
30 // 2¹⁶ q ≤ x - m q < 2¹⁶ and so q ≤ (x - m q) / R < q as desired.
31 return int16(uint32(x-int32(m)*int32(Q)) >> 16)
32 }
33 34 // Given any x, returns x R mod q where R=2¹⁶.
35 func toMont(x int16) int16 {
36 // Note |1353 x| ≤ 1353 2¹⁵ ≤ 13318 q ≤ 2¹⁵ q and so we're within
37 // the bounds of montReduce.
38 return montReduce(int32(x) * 1353) // 1353 = R² mod q.
39 }
40 41 // Given any x, compute 0 ≤ y ≤ q with x = y (mod q).
42 //
43 // Beware: we might have barrettReduce(x) = q ≠ 0 for some x. In fact,
44 // this happens if and only if x = -nq for some positive integer n.
45 func barrettReduce(x int16) int16 {
46 // This is standard Barrett reduction.
47 //
48 // For any x we have x mod q = x - ⌊x/q⌋ q. We will use 20159/2²⁶ as
49 // an approximation of 1/q. Note that 0 ≤ 20159/2²⁶ - 1/q ≤ 0.135/2²⁶
50 // and so | x 20156/2²⁶ - x/q | ≤ 2⁻¹⁰ for |x| ≤ 2¹⁶. For all x
51 // not a multiple of q, the number x/q is further than 1/q from any integer
52 // and so ⌊x 20156/2²⁶⌋ = ⌊x/q⌋. If x is a multiple of q and x is positive,
53 // then x 20156/2²⁶ is larger than x/q so ⌊x 20156/2²⁶⌋ = ⌊x/q⌋ as well.
54 // Finally, if x is negative multiple of q, then ⌊x 20156/2²⁶⌋ = ⌊x/q⌋-1.
55 // Thus
56 // [ q if x=-nq for pos. integer n
57 // x - ⌊x 20156/2²⁶⌋ q = [
58 // [ x mod q otherwise
59 //
60 // To compute actually compute this, note that
61 //
62 // ⌊x 20156/2²⁶⌋ = (20159 x) >> 26.
63 return x - int16((int32(x)*20159)>>26)*Q
64 }
65 66 // Returns x if x < q and x - q otherwise. Assumes x ≥ -29439.
67 func csubq(x int16) int16 {
68 x -= Q // no overflow due to assumption x ≥ -29439.
69 // If x is positive, then x >> 15 = 0. If x is negative,
70 // then uint16(x >> 15) = 2¹⁶-1. So this will add back in q
71 // if x was smaller than q.
72 x += (x >> 15) & Q
73 return x
74 }
75