1 //! Arithmetic mod 2^252 + 27742317777372353535851937790883648493
2 //! with 9 29-bit unsigned limbs
3 //!
4 //! To see that this is safe for intermediate results, note that
5 //! the largest limb in a 9 by 9 product of 29-bit limbs will be
6 //! (0x1fffffff^2) * 9 = 0x23fffffdc0000009 (62 bits).
7 //!
8 //! For a one level Karatsuba decomposition, the specific ranges
9 //! depend on how the limbs are combined, but will stay within
10 //! -0x1ffffffe00000008 (62 bits with sign bit) to
11 //! 0x43fffffbc0000011 (63 bits), which is still safe.
12
13 use core::fmt::Debug;
14 use core::ops::{Index, IndexMut};
15
16 use zeroize::Zeroize;
17
18 use constants;
19
20 /// The `Scalar29` struct represents an element in ℤ/lℤ as 9 29-bit limbs
21 #[derive(Copy,Clone)]
22 pub struct Scalar29(pub [u32; 9]);
23
24 impl Debug for Scalar29 {
fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result25 fn fmt(&self, f: &mut ::core::fmt::Formatter) -> ::core::fmt::Result {
26 write!(f, "Scalar29: {:?}", &self.0[..])
27 }
28 }
29
30 impl Zeroize for Scalar29 {
zeroize(&mut self)31 fn zeroize(&mut self) {
32 self.0.zeroize();
33 }
34 }
35
36 impl Index<usize> for Scalar29 {
37 type Output = u32;
index(&self, _index: usize) -> &u3238 fn index(&self, _index: usize) -> &u32 {
39 &(self.0[_index])
40 }
41 }
42
43 impl IndexMut<usize> for Scalar29 {
index_mut(&mut self, _index: usize) -> &mut u3244 fn index_mut(&mut self, _index: usize) -> &mut u32 {
45 &mut (self.0[_index])
46 }
47 }
48
49 /// u32 * u32 = u64 multiply helper
50 #[inline(always)]
m(x: u32, y: u32) -> u6451 fn m(x: u32, y: u32) -> u64 {
52 (x as u64) * (y as u64)
53 }
54
55 impl Scalar29 {
56 /// Return the zero scalar.
zero() -> Scalar2957 pub fn zero() -> Scalar29 {
58 Scalar29([0,0,0,0,0,0,0,0,0])
59 }
60
61 /// Unpack a 32 byte / 256 bit scalar into 9 29-bit limbs.
from_bytes(bytes: &[u8; 32]) -> Scalar2962 pub fn from_bytes(bytes: &[u8; 32]) -> Scalar29 {
63 let mut words = [0u32; 8];
64 for i in 0..8 {
65 for j in 0..4 {
66 words[i] |= (bytes[(i * 4) + j] as u32) << (j * 8);
67 }
68 }
69
70 let mask = (1u32 << 29) - 1;
71 let top_mask = (1u32 << 24) - 1;
72 let mut s = Scalar29::zero();
73
74 s[ 0] = words[0] & mask;
75 s[ 1] = ((words[0] >> 29) | (words[1] << 3)) & mask;
76 s[ 2] = ((words[1] >> 26) | (words[2] << 6)) & mask;
77 s[ 3] = ((words[2] >> 23) | (words[3] << 9)) & mask;
78 s[ 4] = ((words[3] >> 20) | (words[4] << 12)) & mask;
79 s[ 5] = ((words[4] >> 17) | (words[5] << 15)) & mask;
80 s[ 6] = ((words[5] >> 14) | (words[6] << 18)) & mask;
81 s[ 7] = ((words[6] >> 11) | (words[7] << 21)) & mask;
82 s[ 8] = (words[7] >> 8) & top_mask;
83
84 s
85 }
86
87 /// Reduce a 64 byte / 512 bit scalar mod l.
from_bytes_wide(bytes: &[u8; 64]) -> Scalar2988 pub fn from_bytes_wide(bytes: &[u8; 64]) -> Scalar29 {
89 let mut words = [0u32; 16];
90 for i in 0..16 {
91 for j in 0..4 {
92 words[i] |= (bytes[(i * 4) + j] as u32) << (j * 8);
93 }
94 }
95
96 let mask = (1u32 << 29) - 1;
97 let mut lo = Scalar29::zero();
98 let mut hi = Scalar29::zero();
99
100 lo[0] = words[ 0] & mask;
101 lo[1] = ((words[ 0] >> 29) | (words[ 1] << 3)) & mask;
102 lo[2] = ((words[ 1] >> 26) | (words[ 2] << 6)) & mask;
103 lo[3] = ((words[ 2] >> 23) | (words[ 3] << 9)) & mask;
104 lo[4] = ((words[ 3] >> 20) | (words[ 4] << 12)) & mask;
105 lo[5] = ((words[ 4] >> 17) | (words[ 5] << 15)) & mask;
106 lo[6] = ((words[ 5] >> 14) | (words[ 6] << 18)) & mask;
107 lo[7] = ((words[ 6] >> 11) | (words[ 7] << 21)) & mask;
108 lo[8] = ((words[ 7] >> 8) | (words[ 8] << 24)) & mask;
109 hi[0] = ((words[ 8] >> 5) | (words[ 9] << 27)) & mask;
110 hi[1] = (words[ 9] >> 2) & mask;
111 hi[2] = ((words[ 9] >> 31) | (words[10] << 1)) & mask;
112 hi[3] = ((words[10] >> 28) | (words[11] << 4)) & mask;
113 hi[4] = ((words[11] >> 25) | (words[12] << 7)) & mask;
114 hi[5] = ((words[12] >> 22) | (words[13] << 10)) & mask;
115 hi[6] = ((words[13] >> 19) | (words[14] << 13)) & mask;
116 hi[7] = ((words[14] >> 16) | (words[15] << 16)) & mask;
117 hi[8] = words[15] >> 13 ;
118
119 lo = Scalar29::montgomery_mul(&lo, &constants::R); // (lo * R) / R = lo
120 hi = Scalar29::montgomery_mul(&hi, &constants::RR); // (hi * R^2) / R = hi * R
121
122 Scalar29::add(&hi, &lo) // (hi * R) + lo
123 }
124
125 /// Pack the limbs of this `Scalar29` into 32 bytes.
to_bytes(&self) -> [u8; 32]126 pub fn to_bytes(&self) -> [u8; 32] {
127 let mut s = [0u8; 32];
128
129 s[0] = (self.0[ 0] >> 0) as u8;
130 s[1] = (self.0[ 0] >> 8) as u8;
131 s[2] = (self.0[ 0] >> 16) as u8;
132 s[3] = ((self.0[ 0] >> 24) | (self.0[ 1] << 5)) as u8;
133 s[4] = (self.0[ 1] >> 3) as u8;
134 s[5] = (self.0[ 1] >> 11) as u8;
135 s[6] = (self.0[ 1] >> 19) as u8;
136 s[7] = ((self.0[ 1] >> 27) | (self.0[ 2] << 2)) as u8;
137 s[8] = (self.0[ 2] >> 6) as u8;
138 s[9] = (self.0[ 2] >> 14) as u8;
139 s[10] = ((self.0[ 2] >> 22) | (self.0[ 3] << 7)) as u8;
140 s[11] = (self.0[ 3] >> 1) as u8;
141 s[12] = (self.0[ 3] >> 9) as u8;
142 s[13] = (self.0[ 3] >> 17) as u8;
143 s[14] = ((self.0[ 3] >> 25) | (self.0[ 4] << 4)) as u8;
144 s[15] = (self.0[ 4] >> 4) as u8;
145 s[16] = (self.0[ 4] >> 12) as u8;
146 s[17] = (self.0[ 4] >> 20) as u8;
147 s[18] = ((self.0[ 4] >> 28) | (self.0[ 5] << 1)) as u8;
148 s[19] = (self.0[ 5] >> 7) as u8;
149 s[20] = (self.0[ 5] >> 15) as u8;
150 s[21] = ((self.0[ 5] >> 23) | (self.0[ 6] << 6)) as u8;
151 s[22] = (self.0[ 6] >> 2) as u8;
152 s[23] = (self.0[ 6] >> 10) as u8;
153 s[24] = (self.0[ 6] >> 18) as u8;
154 s[25] = ((self.0[ 6] >> 26) | (self.0[ 7] << 3)) as u8;
155 s[26] = (self.0[ 7] >> 5) as u8;
156 s[27] = (self.0[ 7] >> 13) as u8;
157 s[28] = (self.0[ 7] >> 21) as u8;
158 s[29] = (self.0[ 8] >> 0) as u8;
159 s[30] = (self.0[ 8] >> 8) as u8;
160 s[31] = (self.0[ 8] >> 16) as u8;
161
162 s
163 }
164
165 /// Compute `a + b` (mod l).
add(a: &Scalar29, b: &Scalar29) -> Scalar29166 pub fn add(a: &Scalar29, b: &Scalar29) -> Scalar29 {
167 let mut sum = Scalar29::zero();
168 let mask = (1u32 << 29) - 1;
169
170 // a + b
171 let mut carry: u32 = 0;
172 for i in 0..9 {
173 carry = a[i] + b[i] + (carry >> 29);
174 sum[i] = carry & mask;
175 }
176
177 // subtract l if the sum is >= l
178 Scalar29::sub(&sum, &constants::L)
179 }
180
181 /// Compute `a - b` (mod l).
sub(a: &Scalar29, b: &Scalar29) -> Scalar29182 pub fn sub(a: &Scalar29, b: &Scalar29) -> Scalar29 {
183 let mut difference = Scalar29::zero();
184 let mask = (1u32 << 29) - 1;
185
186 // a - b
187 let mut borrow: u32 = 0;
188 for i in 0..9 {
189 borrow = a[i].wrapping_sub(b[i] + (borrow >> 31));
190 difference[i] = borrow & mask;
191 }
192
193 // conditionally add l if the difference is negative
194 let underflow_mask = ((borrow >> 31) ^ 1).wrapping_sub(1);
195 let mut carry: u32 = 0;
196 for i in 0..9 {
197 carry = (carry >> 29) + difference[i] + (constants::L[i] & underflow_mask);
198 difference[i] = carry & mask;
199 }
200
201 difference
202 }
203
204 /// Compute `a * b`.
205 ///
206 /// This is implemented with a one-level refined Karatsuba decomposition
207 #[inline(always)]
mul_internal(a: &Scalar29, b: &Scalar29) -> [u64; 17]208 pub (crate) fn mul_internal(a: &Scalar29, b: &Scalar29) -> [u64; 17] {
209 let mut z = [0u64; 17];
210
211 z[0] = m(a[0],b[0]); // c00
212 z[1] = m(a[0],b[1]) + m(a[1],b[0]); // c01
213 z[2] = m(a[0],b[2]) + m(a[1],b[1]) + m(a[2],b[0]); // c02
214 z[3] = m(a[0],b[3]) + m(a[1],b[2]) + m(a[2],b[1]) + m(a[3],b[0]); // c03
215 z[4] = m(a[0],b[4]) + m(a[1],b[3]) + m(a[2],b[2]) + m(a[3],b[1]) + m(a[4],b[0]); // c04
216 z[5] = m(a[1],b[4]) + m(a[2],b[3]) + m(a[3],b[2]) + m(a[4],b[1]); // c05
217 z[6] = m(a[2],b[4]) + m(a[3],b[3]) + m(a[4],b[2]); // c06
218 z[7] = m(a[3],b[4]) + m(a[4],b[3]); // c07
219 z[8] = (m(a[4],b[4])).wrapping_sub(z[3]); // c08 - c03
220
221 z[10] = z[5].wrapping_sub(m(a[5],b[5])); // c05mc10
222 z[11] = z[6].wrapping_sub(m(a[5],b[6]) + m(a[6],b[5])); // c06mc11
223 z[12] = z[7].wrapping_sub(m(a[5],b[7]) + m(a[6],b[6]) + m(a[7],b[5])); // c07mc12
224 z[13] = m(a[5],b[8]) + m(a[6],b[7]) + m(a[7],b[6]) + m(a[8],b[5]); // c13
225 z[14] = m(a[6],b[8]) + m(a[7],b[7]) + m(a[8],b[6]); // c14
226 z[15] = m(a[7],b[8]) + m(a[8],b[7]); // c15
227 z[16] = m(a[8],b[8]); // c16
228
229 z[ 5] = z[10].wrapping_sub(z[ 0]); // c05mc10 - c00
230 z[ 6] = z[11].wrapping_sub(z[ 1]); // c06mc11 - c01
231 z[ 7] = z[12].wrapping_sub(z[ 2]); // c07mc12 - c02
232 z[ 8] = z[ 8].wrapping_sub(z[13]); // c08mc13 - c03
233 z[ 9] = z[14].wrapping_add(z[ 4]); // c14 + c04
234 z[10] = z[15].wrapping_add(z[10]); // c15 + c05mc10
235 z[11] = z[16].wrapping_add(z[11]); // c16 + c06mc11
236
237 let aa = [
238 a[0]+a[5],
239 a[1]+a[6],
240 a[2]+a[7],
241 a[3]+a[8]
242 ];
243
244 let bb = [
245 b[0]+b[5],
246 b[1]+b[6],
247 b[2]+b[7],
248 b[3]+b[8]
249 ];
250
251 z[ 5] = (m(aa[0],bb[0])) .wrapping_add(z[ 5]); // c20 + c05mc10 - c00
252 z[ 6] = (m(aa[0],bb[1]) + m(aa[1],bb[0])) .wrapping_add(z[ 6]); // c21 + c06mc11 - c01
253 z[ 7] = (m(aa[0],bb[2]) + m(aa[1],bb[1]) + m(aa[2],bb[0])) .wrapping_add(z[ 7]); // c22 + c07mc12 - c02
254 z[ 8] = (m(aa[0],bb[3]) + m(aa[1],bb[2]) + m(aa[2],bb[1]) + m(aa[3],bb[0])) .wrapping_add(z[ 8]); // c23 + c08mc13 - c03
255 z[ 9] = (m(aa[0], b[4]) + m(aa[1],bb[3]) + m(aa[2],bb[2]) + m(aa[3],bb[1]) + m(a[4],bb[0])).wrapping_sub(z[ 9]); // c24 - c14 - c04
256 z[10] = ( m(aa[1], b[4]) + m(aa[2],bb[3]) + m(aa[3],bb[2]) + m(a[4],bb[1])).wrapping_sub(z[10]); // c25 - c15 - c05mc10
257 z[11] = ( m(aa[2], b[4]) + m(aa[3],bb[3]) + m(a[4],bb[2])).wrapping_sub(z[11]); // c26 - c16 - c06mc11
258 z[12] = ( m(aa[3], b[4]) + m(a[4],bb[3])).wrapping_sub(z[12]); // c27 - c07mc12
259
260 z
261 }
262
263 /// Compute `a^2`.
264 #[inline(always)]
square_internal(a: &Scalar29) -> [u64; 17]265 fn square_internal(a: &Scalar29) -> [u64; 17] {
266 let aa = [
267 a[0]*2,
268 a[1]*2,
269 a[2]*2,
270 a[3]*2,
271 a[4]*2,
272 a[5]*2,
273 a[6]*2,
274 a[7]*2
275 ];
276
277 [
278 m( a[0],a[0]),
279 m(aa[0],a[1]),
280 m(aa[0],a[2]) + m( a[1],a[1]),
281 m(aa[0],a[3]) + m(aa[1],a[2]),
282 m(aa[0],a[4]) + m(aa[1],a[3]) + m( a[2],a[2]),
283 m(aa[0],a[5]) + m(aa[1],a[4]) + m(aa[2],a[3]),
284 m(aa[0],a[6]) + m(aa[1],a[5]) + m(aa[2],a[4]) + m( a[3],a[3]),
285 m(aa[0],a[7]) + m(aa[1],a[6]) + m(aa[2],a[5]) + m(aa[3],a[4]),
286 m(aa[0],a[8]) + m(aa[1],a[7]) + m(aa[2],a[6]) + m(aa[3],a[5]) + m( a[4],a[4]),
287 m(aa[1],a[8]) + m(aa[2],a[7]) + m(aa[3],a[6]) + m(aa[4],a[5]),
288 m(aa[2],a[8]) + m(aa[3],a[7]) + m(aa[4],a[6]) + m( a[5],a[5]),
289 m(aa[3],a[8]) + m(aa[4],a[7]) + m(aa[5],a[6]),
290 m(aa[4],a[8]) + m(aa[5],a[7]) + m( a[6],a[6]),
291 m(aa[5],a[8]) + m(aa[6],a[7]),
292 m(aa[6],a[8]) + m( a[7],a[7]),
293 m(aa[7],a[8]),
294 m( a[8],a[8]),
295 ]
296 }
297
298 /// Compute `limbs/R` (mod l), where R is the Montgomery modulus 2^261
299 #[inline(always)]
montgomery_reduce(limbs: &[u64; 17]) -> Scalar29300 pub (crate) fn montgomery_reduce(limbs: &[u64; 17]) -> Scalar29 {
301
302 #[inline(always)]
part1(sum: u64) -> (u64, u32)303 fn part1(sum: u64) -> (u64, u32) {
304 let p = (sum as u32).wrapping_mul(constants::LFACTOR) & ((1u32 << 29) - 1);
305 ((sum + m(p,constants::L[0])) >> 29, p)
306 }
307
308 #[inline(always)]
part2(sum: u64) -> (u64, u32)309 fn part2(sum: u64) -> (u64, u32) {
310 let w = (sum as u32) & ((1u32 << 29) - 1);
311 (sum >> 29, w)
312 }
313
314 // note: l5,l6,l7 are zero, so their multiplies can be skipped
315 let l = &constants::L;
316
317 // the first half computes the Montgomery adjustment factor n, and begins adding n*l to make limbs divisible by R
318 let (carry, n0) = part1( limbs[ 0]);
319 let (carry, n1) = part1(carry + limbs[ 1] + m(n0,l[1]));
320 let (carry, n2) = part1(carry + limbs[ 2] + m(n0,l[2]) + m(n1,l[1]));
321 let (carry, n3) = part1(carry + limbs[ 3] + m(n0,l[3]) + m(n1,l[2]) + m(n2,l[1]));
322 let (carry, n4) = part1(carry + limbs[ 4] + m(n0,l[4]) + m(n1,l[3]) + m(n2,l[2]) + m(n3,l[1]));
323 let (carry, n5) = part1(carry + limbs[ 5] + m(n1,l[4]) + m(n2,l[3]) + m(n3,l[2]) + m(n4,l[1]));
324 let (carry, n6) = part1(carry + limbs[ 6] + m(n2,l[4]) + m(n3,l[3]) + m(n4,l[2]) + m(n5,l[1]));
325 let (carry, n7) = part1(carry + limbs[ 7] + m(n3,l[4]) + m(n4,l[3]) + m(n5,l[2]) + m(n6,l[1]));
326 let (carry, n8) = part1(carry + limbs[ 8] + m(n0,l[8]) + m(n4,l[4]) + m(n5,l[3]) + m(n6,l[2]) + m(n7,l[1]));
327
328 // limbs is divisible by R now, so we can divide by R by simply storing the upper half as the result
329 let (carry, r0) = part2(carry + limbs[ 9] + m(n1,l[8]) + m(n5,l[4]) + m(n6,l[3]) + m(n7,l[2]) + m(n8,l[1]));
330 let (carry, r1) = part2(carry + limbs[10] + m(n2,l[8]) + m(n6,l[4]) + m(n7,l[3]) + m(n8,l[2]));
331 let (carry, r2) = part2(carry + limbs[11] + m(n3,l[8]) + m(n7,l[4]) + m(n8,l[3]));
332 let (carry, r3) = part2(carry + limbs[12] + m(n4,l[8]) + m(n8,l[4]));
333 let (carry, r4) = part2(carry + limbs[13] + m(n5,l[8]) );
334 let (carry, r5) = part2(carry + limbs[14] + m(n6,l[8]) );
335 let (carry, r6) = part2(carry + limbs[15] + m(n7,l[8]) );
336 let (carry, r7) = part2(carry + limbs[16] + m(n8,l[8]));
337 let r8 = carry as u32;
338
339 // result may be >= l, so attempt to subtract l
340 Scalar29::sub(&Scalar29([r0,r1,r2,r3,r4,r5,r6,r7,r8]), l)
341 }
342
343 /// Compute `a * b` (mod l).
344 #[inline(never)]
mul(a: &Scalar29, b: &Scalar29) -> Scalar29345 pub fn mul(a: &Scalar29, b: &Scalar29) -> Scalar29 {
346 let ab = Scalar29::montgomery_reduce(&Scalar29::mul_internal(a, b));
347 Scalar29::montgomery_reduce(&Scalar29::mul_internal(&ab, &constants::RR))
348 }
349
350 /// Compute `a^2` (mod l).
351 #[inline(never)]
352 #[allow(dead_code)] // XXX we don't expose square() via the Scalar API
square(&self) -> Scalar29353 pub fn square(&self) -> Scalar29 {
354 let aa = Scalar29::montgomery_reduce(&Scalar29::square_internal(self));
355 Scalar29::montgomery_reduce(&Scalar29::mul_internal(&aa, &constants::RR))
356 }
357
358 /// Compute `(a * b) / R` (mod l), where R is the Montgomery modulus 2^261
359 #[inline(never)]
montgomery_mul(a: &Scalar29, b: &Scalar29) -> Scalar29360 pub fn montgomery_mul(a: &Scalar29, b: &Scalar29) -> Scalar29 {
361 Scalar29::montgomery_reduce(&Scalar29::mul_internal(a, b))
362 }
363
364 /// Compute `(a^2) / R` (mod l) in Montgomery form, where R is the Montgomery modulus 2^261
365 #[inline(never)]
montgomery_square(&self) -> Scalar29366 pub fn montgomery_square(&self) -> Scalar29 {
367 Scalar29::montgomery_reduce(&Scalar29::square_internal(self))
368 }
369
370 /// Puts a Scalar29 in to Montgomery form, i.e. computes `a*R (mod l)`
371 #[inline(never)]
to_montgomery(&self) -> Scalar29372 pub fn to_montgomery(&self) -> Scalar29 {
373 Scalar29::montgomery_mul(self, &constants::RR)
374 }
375
376 /// Takes a Scalar29 out of Montgomery form, i.e. computes `a/R (mod l)`
from_montgomery(&self) -> Scalar29377 pub fn from_montgomery(&self) -> Scalar29 {
378 let mut limbs = [0u64; 17];
379 for i in 0..9 {
380 limbs[i] = self[i] as u64;
381 }
382 Scalar29::montgomery_reduce(&limbs)
383 }
384 }
385
386 #[cfg(test)]
387 mod test {
388 use super::*;
389
390 /// Note: x is 2^253-1 which is slightly larger than the largest scalar produced by
391 /// this implementation (l-1), and should verify there are no overflows for valid scalars
392 ///
393 /// x = 2^253-1 = 14474011154664524427946373126085988481658748083205070504932198000989141204991
394 /// x = 7237005577332262213973186563042994240801631723825162898930247062703686954002 mod l
395 /// x = 5147078182513738803124273553712992179887200054963030844803268920753008712037*R mod l in Montgomery form
396 pub static X: Scalar29 = Scalar29(
397 [0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff,
398 0x1fffffff, 0x1fffffff, 0x1fffffff, 0x1fffffff,
399 0x001fffff]);
400
401 /// x^2 = 3078544782642840487852506753550082162405942681916160040940637093560259278169 mod l
402 pub static XX: Scalar29 = Scalar29(
403 [0x00217559, 0x000b3401, 0x103ff43b, 0x1462a62c,
404 0x1d6f9f38, 0x18e7a42f, 0x09a3dcee, 0x008dbe18,
405 0x0006ce65]);
406
407 /// x^2 = 2912514428060642753613814151688322857484807845836623976981729207238463947987*R mod l in Montgomery form
408 pub static XX_MONT: Scalar29 = Scalar29(
409 [0x152b4d2e, 0x0571d53b, 0x1da6d964, 0x188663b6,
410 0x1d1b5f92, 0x19d50e3f, 0x12306c29, 0x0c6f26fe,
411 0x00030edb]);
412
413 /// y = 6145104759870991071742105800796537629880401874866217824609283457819451087098
414 pub static Y: Scalar29 = Scalar29(
415 [0x1e1458fa, 0x165ba838, 0x1d787b36, 0x0e577f3a,
416 0x1d2baf06, 0x1d689a19, 0x1fff3047, 0x117704ab,
417 0x000d9601]);
418
419 /// x*y = 36752150652102274958925982391442301741
420 pub static XY: Scalar29 = Scalar29(
421 [0x0ba7632d, 0x017736bb, 0x15c76138, 0x0c69daa1,
422 0x000001ba, 0x00000000, 0x00000000, 0x00000000,
423 0x00000000]);
424
425 /// x*y = 3783114862749659543382438697751927473898937741870308063443170013240655651591*R mod l in Montgomery form
426 pub static XY_MONT: Scalar29 = Scalar29(
427 [0x077b51e1, 0x1c64e119, 0x02a19ef5, 0x18d2129e,
428 0x00de0430, 0x045a7bc8, 0x04cfc7c9, 0x1c002681,
429 0x000bdc1c]);
430
431 /// a = 2351415481556538453565687241199399922945659411799870114962672658845158063753
432 pub static A: Scalar29 = Scalar29(
433 [0x07b3be89, 0x02291b60, 0x14a99f03, 0x07dc3787,
434 0x0a782aae, 0x16262525, 0x0cfdb93f, 0x13f5718d,
435 0x000532da]);
436
437 /// b = 4885590095775723760407499321843594317911456947580037491039278279440296187236
438 pub static B: Scalar29 = Scalar29(
439 [0x15421564, 0x1e69fd72, 0x093d9692, 0x161785be,
440 0x1587d69f, 0x09d9dada, 0x130246c0, 0x0c0a8e72,
441 0x000acd25]);
442
443 /// a+b = 0
444 /// a-b = 4702830963113076907131374482398799845891318823599740229925345317690316127506
445 pub static AB: Scalar29 = Scalar29(
446 [0x0f677d12, 0x045236c0, 0x09533e06, 0x0fb86f0f,
447 0x14f0555c, 0x0c4c4a4a, 0x19fb727f, 0x07eae31a,
448 0x000a65b5]);
449
450 // c = (2^512 - 1) % l = 1627715501170711445284395025044413883736156588369414752970002579683115011840
451 pub static C: Scalar29 = Scalar29(
452 [0x049c0f00, 0x00308f1a, 0x0164d1e9, 0x1c374ed1,
453 0x1be65d00, 0x19e90bfa, 0x08f73bb1, 0x036f8613,
454 0x00039941]);
455
456 #[test]
mul_max()457 fn mul_max() {
458 let res = Scalar29::mul(&X, &X);
459 for i in 0..9 {
460 assert!(res[i] == XX[i]);
461 }
462 }
463
464 #[test]
square_max()465 fn square_max() {
466 let res = X.square();
467 for i in 0..9 {
468 assert!(res[i] == XX[i]);
469 }
470 }
471
472 #[test]
montgomery_mul_max()473 fn montgomery_mul_max() {
474 let res = Scalar29::montgomery_mul(&X, &X);
475 for i in 0..9 {
476 assert!(res[i] == XX_MONT[i]);
477 }
478 }
479
480 #[test]
montgomery_square_max()481 fn montgomery_square_max() {
482 let res = X.montgomery_square();
483 for i in 0..9 {
484 assert!(res[i] == XX_MONT[i]);
485 }
486 }
487
488 #[test]
mul()489 fn mul() {
490 let res = Scalar29::mul(&X, &Y);
491 for i in 0..9 {
492 assert!(res[i] == XY[i]);
493 }
494 }
495
496 #[test]
montgomery_mul()497 fn montgomery_mul() {
498 let res = Scalar29::montgomery_mul(&X, &Y);
499 for i in 0..9 {
500 assert!(res[i] == XY_MONT[i]);
501 }
502 }
503
504 #[test]
add()505 fn add() {
506 let res = Scalar29::add(&A, &B);
507 let zero = Scalar29::zero();
508 for i in 0..9 {
509 assert!(res[i] == zero[i]);
510 }
511 }
512
513 #[test]
sub()514 fn sub() {
515 let res = Scalar29::sub(&A, &B);
516 for i in 0..9 {
517 assert!(res[i] == AB[i]);
518 }
519 }
520
521 #[test]
from_bytes_wide()522 fn from_bytes_wide() {
523 let bignum = [255u8; 64]; // 2^512 - 1
524 let reduced = Scalar29::from_bytes_wide(&bignum);
525 for i in 0..9 {
526 assert!(reduced[i] == C[i]);
527 }
528 }
529 }
530