PRCYCoin  2.0.0.7rc1
P2P Digital Currency
field_10x26_impl.h
Go to the documentation of this file.
1 /**********************************************************************
2  * Copyright (c) 2013, 2014 Pieter Wuille *
3  * Distributed under the MIT software license, see the accompanying *
4  * file COPYING or http://www.opensource.org/licenses/mit-license.php.*
5  **********************************************************************/
6 
7 #ifndef _SECP256K1_FIELD_REPR_IMPL_H_
8 #define _SECP256K1_FIELD_REPR_IMPL_H_
9 
10 #include <stdio.h>
11 #include <string.h>
12 #include "util.h"
13 #include "num.h"
14 #include "field.h"
15 
16 static void secp256k1_fe_inner_start(void) {}
17 static void secp256k1_fe_inner_stop(void) {}
18 
19 #ifdef VERIFY
20 static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
21  const uint32_t *d = a->n;
22  int m = a->normalized ? 1 : 2 * a->magnitude, r = 1;
23  r &= (d[0] <= 0x3FFFFFFUL * m);
24  r &= (d[1] <= 0x3FFFFFFUL * m);
25  r &= (d[2] <= 0x3FFFFFFUL * m);
26  r &= (d[3] <= 0x3FFFFFFUL * m);
27  r &= (d[4] <= 0x3FFFFFFUL * m);
28  r &= (d[5] <= 0x3FFFFFFUL * m);
29  r &= (d[6] <= 0x3FFFFFFUL * m);
30  r &= (d[7] <= 0x3FFFFFFUL * m);
31  r &= (d[8] <= 0x3FFFFFFUL * m);
32  r &= (d[9] <= 0x03FFFFFUL * m);
33  r &= (a->magnitude >= 0);
34  if (a->normalized) {
35  r &= (a->magnitude <= 1);
36  if (r && (d[9] == 0x03FFFFFUL)) {
37  uint32_t mid = d[8] & d[7] & d[6] & d[5] & d[4] & d[3] & d[2];
38  if (mid == 0x3FFFFFFUL) {
39  r &= ((d[1] + 0x40UL + ((d[0] + 0x3D1UL) >> 26)) <= 0x3FFFFFFUL);
40  }
41  }
42  }
43  VERIFY_CHECK(r == 1);
44 }
45 #else
46 static void secp256k1_fe_verify(const secp256k1_fe_t *a) {
47  (void)a;
48 }
49 #endif
50 
51 static void secp256k1_fe_normalize(secp256k1_fe_t *r) {
52  uint32_t t0 = r->n[0], t1 = r->n[1], t2 = r->n[2], t3 = r->n[3], t4 = r->n[4],
53  t5 = r->n[5], t6 = r->n[6], t7 = r->n[7], t8 = r->n[8], t9 = r->n[9];
54 
55  /* Reduce t9 at the start so there will be at most a single carry from the first pass */
56  uint32_t x = t9 >> 22; t9 &= 0x03FFFFFUL;
57  uint32_t m;
58 
59  /* The first pass ensures the magnitude is 1, ... */
60  t0 += x * 0x3D1UL; t1 += (x << 6);
61  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
62  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
63  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL; m = t2;
64  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL; m &= t3;
65  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL; m &= t4;
66  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL; m &= t5;
67  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL; m &= t6;
68  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL; m &= t7;
69  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL; m &= t8;
70 
71  /* ... except for a possible carry at bit 22 of t9 (i.e. bit 256 of the field element) */
72  VERIFY_CHECK(t9 >> 23 == 0);
73 
74  /* At most a single final reduction is needed; check if the value is >= the field characteristic */
75  x = (t9 >> 22) | ((t9 == 0x03FFFFFUL) & (m == 0x3FFFFFFUL)
76  & ((t1 + 0x40UL + ((t0 + 0x3D1UL) >> 26)) > 0x3FFFFFFUL));
77 
78  /* Apply the final reduction (for constant-time behaviour, we do it always) */
79  t0 += x * 0x3D1UL; t1 += (x << 6);
80  t1 += (t0 >> 26); t0 &= 0x3FFFFFFUL;
81  t2 += (t1 >> 26); t1 &= 0x3FFFFFFUL;
82  t3 += (t2 >> 26); t2 &= 0x3FFFFFFUL;
83  t4 += (t3 >> 26); t3 &= 0x3FFFFFFUL;
84  t5 += (t4 >> 26); t4 &= 0x3FFFFFFUL;
85  t6 += (t5 >> 26); t5 &= 0x3FFFFFFUL;
86  t7 += (t6 >> 26); t6 &= 0x3FFFFFFUL;
87  t8 += (t7 >> 26); t7 &= 0x3FFFFFFUL;
88  t9 += (t8 >> 26); t8 &= 0x3FFFFFFUL;
89 
90  /* If t9 didn't carry to bit 22 already, then it should have after any final reduction */
91  VERIFY_CHECK(t9 >> 22 == x);
92 
93  /* Mask off the possible multiple of 2^256 from the final reduction */
94  t9 &= 0x03FFFFFUL;
95 
96  r->n[0] = t0; r->n[1] = t1; r->n[2] = t2; r->n[3] = t3; r->n[4] = t4;
97  r->n[5] = t5; r->n[6] = t6; r->n[7] = t7; r->n[8] = t8; r->n[9] = t9;
98 
99 #ifdef VERIFY
100  r->magnitude = 1;
101  r->normalized = 1;
102  secp256k1_fe_verify(r);
103 #endif
104 }
105 
106 SECP256K1_INLINE static void secp256k1_fe_set_int(secp256k1_fe_t *r, int a) {
107  r->n[0] = a;
108  r->n[1] = r->n[2] = r->n[3] = r->n[4] = r->n[5] = r->n[6] = r->n[7] = r->n[8] = r->n[9] = 0;
109 #ifdef VERIFY
110  r->magnitude = 1;
111  r->normalized = 1;
112  secp256k1_fe_verify(r);
113 #endif
114 }
115 
116 SECP256K1_INLINE static int secp256k1_fe_is_zero(const secp256k1_fe_t *a) {
117 #ifdef VERIFY
118  VERIFY_CHECK(a->normalized);
119  secp256k1_fe_verify(a);
120 #endif
121  const uint32_t *t = a->n;
122  return (t[0] | t[1] | t[2] | t[3] | t[4] | t[5] | t[6] | t[7] | t[8] | t[9]) == 0;
123 }
124 
125 SECP256K1_INLINE static int secp256k1_fe_is_odd(const secp256k1_fe_t *a) {
126 #ifdef VERIFY
127  VERIFY_CHECK(a->normalized);
128  secp256k1_fe_verify(a);
129 #endif
130  return a->n[0] & 1;
131 }
132 
133 SECP256K1_INLINE static void secp256k1_fe_clear(secp256k1_fe_t *a) {
134 #ifdef VERIFY
135  a->magnitude = 0;
136  a->normalized = 1;
137 #endif
138  for (int i=0; i<10; i++) {
139  a->n[i] = 0;
140  }
141 }
142 
143 SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
144 #ifdef VERIFY
145  VERIFY_CHECK(a->normalized);
146  VERIFY_CHECK(b->normalized);
147  secp256k1_fe_verify(a);
148  secp256k1_fe_verify(b);
149 #endif
150  const uint32_t *t = a->n, *u = b->n;
151  return ((t[0]^u[0]) | (t[1]^u[1]) | (t[2]^u[2]) | (t[3]^u[3]) | (t[4]^u[4])
152  | (t[5]^u[5]) | (t[6]^u[6]) | (t[7]^u[7]) | (t[8]^u[8]) | (t[9]^u[9])) == 0;
153 }
154 
155 static int secp256k1_fe_cmp_var(const secp256k1_fe_t *a, const secp256k1_fe_t *b) {
156 #ifdef VERIFY
157  VERIFY_CHECK(a->normalized);
158  VERIFY_CHECK(b->normalized);
159  secp256k1_fe_verify(a);
160  secp256k1_fe_verify(b);
161 #endif
162  for (int i = 9; i >= 0; i--) {
163  if (a->n[i] > b->n[i]) return 1;
164  if (a->n[i] < b->n[i]) return -1;
165  }
166  return 0;
167 }
168 
169 static int secp256k1_fe_set_b32(secp256k1_fe_t *r, const unsigned char *a) {
170  r->n[0] = r->n[1] = r->n[2] = r->n[3] = r->n[4] = 0;
171  r->n[5] = r->n[6] = r->n[7] = r->n[8] = r->n[9] = 0;
172  for (int i=0; i<32; i++) {
173  for (int j=0; j<4; j++) {
174  int limb = (8*i+2*j)/26;
175  int shift = (8*i+2*j)%26;
176  r->n[limb] |= (uint32_t)((a[31-i] >> (2*j)) & 0x3) << shift;
177  }
178  }
179  if (r->n[9] == 0x3FFFFFUL && (r->n[8] & r->n[7] & r->n[6] & r->n[5] & r->n[4] & r->n[3] & r->n[2]) == 0x3FFFFFFUL && (r->n[1] + 0x40UL + ((r->n[0] + 0x3D1UL) >> 26)) > 0x3FFFFFFUL) {
180  return 0;
181  }
182 #ifdef VERIFY
183  r->magnitude = 1;
184  r->normalized = 1;
185  secp256k1_fe_verify(r);
186 #endif
187  return 1;
188 }
189 
191 static void secp256k1_fe_get_b32(unsigned char *r, const secp256k1_fe_t *a) {
192 #ifdef VERIFY
193  VERIFY_CHECK(a->normalized);
194  secp256k1_fe_verify(a);
195 #endif
196  for (int i=0; i<32; i++) {
197  int c = 0;
198  for (int j=0; j<4; j++) {
199  int limb = (8*i+2*j)/26;
200  int shift = (8*i+2*j)%26;
201  c |= ((a->n[limb] >> shift) & 0x3) << (2 * j);
202  }
203  r[31-i] = c;
204  }
205 }
206 
207 SECP256K1_INLINE static void secp256k1_fe_negate(secp256k1_fe_t *r, const secp256k1_fe_t *a, int m) {
208 #ifdef VERIFY
209  VERIFY_CHECK(a->magnitude <= m);
210  secp256k1_fe_verify(a);
211 #endif
212  r->n[0] = 0x3FFFC2FUL * 2 * (m + 1) - a->n[0];
213  r->n[1] = 0x3FFFFBFUL * 2 * (m + 1) - a->n[1];
214  r->n[2] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[2];
215  r->n[3] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[3];
216  r->n[4] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[4];
217  r->n[5] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[5];
218  r->n[6] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[6];
219  r->n[7] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[7];
220  r->n[8] = 0x3FFFFFFUL * 2 * (m + 1) - a->n[8];
221  r->n[9] = 0x03FFFFFUL * 2 * (m + 1) - a->n[9];
222 #ifdef VERIFY
223  r->magnitude = m + 1;
224  r->normalized = 0;
225  secp256k1_fe_verify(r);
226 #endif
227 }
228 
229 SECP256K1_INLINE static void secp256k1_fe_mul_int(secp256k1_fe_t *r, int a) {
230  r->n[0] *= a;
231  r->n[1] *= a;
232  r->n[2] *= a;
233  r->n[3] *= a;
234  r->n[4] *= a;
235  r->n[5] *= a;
236  r->n[6] *= a;
237  r->n[7] *= a;
238  r->n[8] *= a;
239  r->n[9] *= a;
240 #ifdef VERIFY
241  r->magnitude *= a;
242  r->normalized = 0;
243  secp256k1_fe_verify(r);
244 #endif
245 }
246 
247 SECP256K1_INLINE static void secp256k1_fe_add(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
248 #ifdef VERIFY
249  secp256k1_fe_verify(a);
250 #endif
251  r->n[0] += a->n[0];
252  r->n[1] += a->n[1];
253  r->n[2] += a->n[2];
254  r->n[3] += a->n[3];
255  r->n[4] += a->n[4];
256  r->n[5] += a->n[5];
257  r->n[6] += a->n[6];
258  r->n[7] += a->n[7];
259  r->n[8] += a->n[8];
260  r->n[9] += a->n[9];
261 #ifdef VERIFY
262  r->magnitude += a->magnitude;
263  r->normalized = 0;
264  secp256k1_fe_verify(r);
265 #endif
266 }
267 
268 #ifdef VERIFY
269 #define VERIFY_BITS(x, n) VERIFY_CHECK(((x) >> (n)) == 0)
270 #else
271 #define VERIFY_BITS(x, n) do { } while(0)
272 #endif
273 
274 SECP256K1_INLINE static void secp256k1_fe_mul_inner(const uint32_t *a, const uint32_t * SECP256K1_RESTRICT b, uint32_t *r) {
275  VERIFY_BITS(a[0], 30);
276  VERIFY_BITS(a[1], 30);
277  VERIFY_BITS(a[2], 30);
278  VERIFY_BITS(a[3], 30);
279  VERIFY_BITS(a[4], 30);
280  VERIFY_BITS(a[5], 30);
281  VERIFY_BITS(a[6], 30);
282  VERIFY_BITS(a[7], 30);
283  VERIFY_BITS(a[8], 30);
284  VERIFY_BITS(a[9], 26);
285  VERIFY_BITS(b[0], 30);
286  VERIFY_BITS(b[1], 30);
287  VERIFY_BITS(b[2], 30);
288  VERIFY_BITS(b[3], 30);
289  VERIFY_BITS(b[4], 30);
290  VERIFY_BITS(b[5], 30);
291  VERIFY_BITS(b[6], 30);
292  VERIFY_BITS(b[7], 30);
293  VERIFY_BITS(b[8], 30);
294  VERIFY_BITS(b[9], 26);
295 
296  const uint32_t M = 0x3FFFFFFUL, R0 = 0x3D10UL, R1 = 0x400UL;
302  uint64_t c, d;
303 
304  d = (uint64_t)a[0] * b[9]
305  + (uint64_t)a[1] * b[8]
306  + (uint64_t)a[2] * b[7]
307  + (uint64_t)a[3] * b[6]
308  + (uint64_t)a[4] * b[5]
309  + (uint64_t)a[5] * b[4]
310  + (uint64_t)a[6] * b[3]
311  + (uint64_t)a[7] * b[2]
312  + (uint64_t)a[8] * b[1]
313  + (uint64_t)a[9] * b[0];
314  /* VERIFY_BITS(d, 64); */
315  /* [d 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
316  uint32_t t9 = d & M; d >>= 26;
317  VERIFY_BITS(t9, 26);
318  VERIFY_BITS(d, 38);
319  /* [d t9 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
320 
321  c = (uint64_t)a[0] * b[0];
322  VERIFY_BITS(c, 60);
323  /* [d t9 0 0 0 0 0 0 0 0 c] = [p9 0 0 0 0 0 0 0 0 p0] */
324  d += (uint64_t)a[1] * b[9]
325  + (uint64_t)a[2] * b[8]
326  + (uint64_t)a[3] * b[7]
327  + (uint64_t)a[4] * b[6]
328  + (uint64_t)a[5] * b[5]
329  + (uint64_t)a[6] * b[4]
330  + (uint64_t)a[7] * b[3]
331  + (uint64_t)a[8] * b[2]
332  + (uint64_t)a[9] * b[1];
333  VERIFY_BITS(d, 63);
334  /* [d t9 0 0 0 0 0 0 0 0 c] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
335  uint64_t u0 = d & M; d >>= 26; c += u0 * R0;
336  VERIFY_BITS(u0, 26);
337  VERIFY_BITS(d, 37);
338  VERIFY_BITS(c, 61);
339  /* [d u0 t9 0 0 0 0 0 0 0 0 c-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
340  uint32_t t0 = c & M; c >>= 26; c += u0 * R1;
341  VERIFY_BITS(t0, 26);
342  VERIFY_BITS(c, 37);
343  /* [d u0 t9 0 0 0 0 0 0 0 c-u0*R1 t0-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
344  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
345 
346  c += (uint64_t)a[0] * b[1]
347  + (uint64_t)a[1] * b[0];
348  VERIFY_BITS(c, 62);
349  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 p1 p0] */
350  d += (uint64_t)a[2] * b[9]
351  + (uint64_t)a[3] * b[8]
352  + (uint64_t)a[4] * b[7]
353  + (uint64_t)a[5] * b[6]
354  + (uint64_t)a[6] * b[5]
355  + (uint64_t)a[7] * b[4]
356  + (uint64_t)a[8] * b[3]
357  + (uint64_t)a[9] * b[2];
358  VERIFY_BITS(d, 63);
359  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
360  uint64_t u1 = d & M; d >>= 26; c += u1 * R0;
361  VERIFY_BITS(u1, 26);
362  VERIFY_BITS(d, 37);
363  VERIFY_BITS(c, 63);
364  /* [d u1 0 t9 0 0 0 0 0 0 0 c-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
365  uint32_t t1 = c & M; c >>= 26; c += u1 * R1;
366  VERIFY_BITS(t1, 26);
367  VERIFY_BITS(c, 38);
368  /* [d u1 0 t9 0 0 0 0 0 0 c-u1*R1 t1-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
369  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
370 
371  c += (uint64_t)a[0] * b[2]
372  + (uint64_t)a[1] * b[1]
373  + (uint64_t)a[2] * b[0];
374  VERIFY_BITS(c, 62);
375  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
376  d += (uint64_t)a[3] * b[9]
377  + (uint64_t)a[4] * b[8]
378  + (uint64_t)a[5] * b[7]
379  + (uint64_t)a[6] * b[6]
380  + (uint64_t)a[7] * b[5]
381  + (uint64_t)a[8] * b[4]
382  + (uint64_t)a[9] * b[3];
383  VERIFY_BITS(d, 63);
384  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
385  uint64_t u2 = d & M; d >>= 26; c += u2 * R0;
386  VERIFY_BITS(u2, 26);
387  VERIFY_BITS(d, 37);
388  VERIFY_BITS(c, 63);
389  /* [d u2 0 0 t9 0 0 0 0 0 0 c-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
390  uint32_t t2 = c & M; c >>= 26; c += u2 * R1;
391  VERIFY_BITS(t2, 26);
392  VERIFY_BITS(c, 38);
393  /* [d u2 0 0 t9 0 0 0 0 0 c-u2*R1 t2-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
394  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
395 
396  c += (uint64_t)a[0] * b[3]
397  + (uint64_t)a[1] * b[2]
398  + (uint64_t)a[2] * b[1]
399  + (uint64_t)a[3] * b[0];
400  VERIFY_BITS(c, 63);
401  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
402  d += (uint64_t)a[4] * b[9]
403  + (uint64_t)a[5] * b[8]
404  + (uint64_t)a[6] * b[7]
405  + (uint64_t)a[7] * b[6]
406  + (uint64_t)a[8] * b[5]
407  + (uint64_t)a[9] * b[4];
408  VERIFY_BITS(d, 63);
409  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
410  uint64_t u3 = d & M; d >>= 26; c += u3 * R0;
411  VERIFY_BITS(u3, 26);
412  VERIFY_BITS(d, 37);
413  /* VERIFY_BITS(c, 64); */
414  /* [d u3 0 0 0 t9 0 0 0 0 0 c-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
415  uint32_t t3 = c & M; c >>= 26; c += u3 * R1;
416  VERIFY_BITS(t3, 26);
417  VERIFY_BITS(c, 39);
418  /* [d u3 0 0 0 t9 0 0 0 0 c-u3*R1 t3-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
419  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
420 
421  c += (uint64_t)a[0] * b[4]
422  + (uint64_t)a[1] * b[3]
423  + (uint64_t)a[2] * b[2]
424  + (uint64_t)a[3] * b[1]
425  + (uint64_t)a[4] * b[0];
426  VERIFY_BITS(c, 63);
427  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
428  d += (uint64_t)a[5] * b[9]
429  + (uint64_t)a[6] * b[8]
430  + (uint64_t)a[7] * b[7]
431  + (uint64_t)a[8] * b[6]
432  + (uint64_t)a[9] * b[5];
433  VERIFY_BITS(d, 62);
434  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
435  uint64_t u4 = d & M; d >>= 26; c += u4 * R0;
436  VERIFY_BITS(u4, 26);
437  VERIFY_BITS(d, 36);
438  /* VERIFY_BITS(c, 64); */
439  /* [d u4 0 0 0 0 t9 0 0 0 0 c-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
440  uint32_t t4 = c & M; c >>= 26; c += u4 * R1;
441  VERIFY_BITS(t4, 26);
442  VERIFY_BITS(c, 39);
443  /* [d u4 0 0 0 0 t9 0 0 0 c-u4*R1 t4-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
444  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
445 
446  c += (uint64_t)a[0] * b[5]
447  + (uint64_t)a[1] * b[4]
448  + (uint64_t)a[2] * b[3]
449  + (uint64_t)a[3] * b[2]
450  + (uint64_t)a[4] * b[1]
451  + (uint64_t)a[5] * b[0];
452  VERIFY_BITS(c, 63);
453  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
454  d += (uint64_t)a[6] * b[9]
455  + (uint64_t)a[7] * b[8]
456  + (uint64_t)a[8] * b[7]
457  + (uint64_t)a[9] * b[6];
458  VERIFY_BITS(d, 62);
459  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
460  uint64_t u5 = d & M; d >>= 26; c += u5 * R0;
461  VERIFY_BITS(u5, 26);
462  VERIFY_BITS(d, 36);
463  /* VERIFY_BITS(c, 64); */
464  /* [d u5 0 0 0 0 0 t9 0 0 0 c-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
465  uint32_t t5 = c & M; c >>= 26; c += u5 * R1;
466  VERIFY_BITS(t5, 26);
467  VERIFY_BITS(c, 39);
468  /* [d u5 0 0 0 0 0 t9 0 0 c-u5*R1 t5-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
469  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
470 
471  c += (uint64_t)a[0] * b[6]
472  + (uint64_t)a[1] * b[5]
473  + (uint64_t)a[2] * b[4]
474  + (uint64_t)a[3] * b[3]
475  + (uint64_t)a[4] * b[2]
476  + (uint64_t)a[5] * b[1]
477  + (uint64_t)a[6] * b[0];
478  VERIFY_BITS(c, 63);
479  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
480  d += (uint64_t)a[7] * b[9]
481  + (uint64_t)a[8] * b[8]
482  + (uint64_t)a[9] * b[7];
483  VERIFY_BITS(d, 61);
484  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
485  uint64_t u6 = d & M; d >>= 26; c += u6 * R0;
486  VERIFY_BITS(u6, 26);
487  VERIFY_BITS(d, 35);
488  /* VERIFY_BITS(c, 64); */
489  /* [d u6 0 0 0 0 0 0 t9 0 0 c-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
490  uint32_t t6 = c & M; c >>= 26; c += u6 * R1;
491  VERIFY_BITS(t6, 26);
492  VERIFY_BITS(c, 39);
493  /* [d u6 0 0 0 0 0 0 t9 0 c-u6*R1 t6-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
494  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
495 
496  c += (uint64_t)a[0] * b[7]
497  + (uint64_t)a[1] * b[6]
498  + (uint64_t)a[2] * b[5]
499  + (uint64_t)a[3] * b[4]
500  + (uint64_t)a[4] * b[3]
501  + (uint64_t)a[5] * b[2]
502  + (uint64_t)a[6] * b[1]
503  + (uint64_t)a[7] * b[0];
504  /* VERIFY_BITS(c, 64); */
505  VERIFY_CHECK(c <= 0x8000007C00000007ULL);
506  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
507  d += (uint64_t)a[8] * b[9]
508  + (uint64_t)a[9] * b[8];
509  VERIFY_BITS(d, 58);
510  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
511  uint64_t u7 = d & M; d >>= 26; c += u7 * R0;
512  VERIFY_BITS(u7, 26);
513  VERIFY_BITS(d, 32);
514  /* VERIFY_BITS(c, 64); */
515  VERIFY_CHECK(c <= 0x800001703FFFC2F7ULL);
516  /* [d u7 0 0 0 0 0 0 0 t9 0 c-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
517  uint32_t t7 = c & M; c >>= 26; c += u7 * R1;
518  VERIFY_BITS(t7, 26);
519  VERIFY_BITS(c, 38);
520  /* [d u7 0 0 0 0 0 0 0 t9 c-u7*R1 t7-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
521  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
522 
523  c += (uint64_t)a[0] * b[8]
524  + (uint64_t)a[1] * b[7]
525  + (uint64_t)a[2] * b[6]
526  + (uint64_t)a[3] * b[5]
527  + (uint64_t)a[4] * b[4]
528  + (uint64_t)a[5] * b[3]
529  + (uint64_t)a[6] * b[2]
530  + (uint64_t)a[7] * b[1]
531  + (uint64_t)a[8] * b[0];
532  /* VERIFY_BITS(c, 64); */
533  VERIFY_CHECK(c <= 0x9000007B80000008ULL);
534  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
535  d += (uint64_t)a[9] * b[9];
536  VERIFY_BITS(d, 57);
537  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
538  uint64_t u8 = d & M; d >>= 26; c += u8 * R0;
539  VERIFY_BITS(u8, 26);
540  VERIFY_BITS(d, 31);
541  /* VERIFY_BITS(c, 64); */
542  VERIFY_CHECK(c <= 0x9000016FBFFFC2F8ULL);
543  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
544 
545  r[3] = t3;
546  VERIFY_BITS(r[3], 26);
547  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
548  r[4] = t4;
549  VERIFY_BITS(r[4], 26);
550  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
551  r[5] = t5;
552  VERIFY_BITS(r[5], 26);
553  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
554  r[6] = t6;
555  VERIFY_BITS(r[6], 26);
556  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
557  r[7] = t7;
558  VERIFY_BITS(r[7], 26);
559  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
560 
561  r[8] = c & M; c >>= 26; c += u8 * R1;
562  VERIFY_BITS(r[8], 26);
563  VERIFY_BITS(c, 39);
564  /* [d u8 0 0 0 0 0 0 0 0 t9+c-u8*R1 r8-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
565  /* [d 0 0 0 0 0 0 0 0 0 t9+c r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
566  c += d * R0 + t9;
567  VERIFY_BITS(c, 45);
568  /* [d 0 0 0 0 0 0 0 0 0 c-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
569  r[9] = c & (M >> 4); c >>= 22; c += d * (R1 << 4);
570  VERIFY_BITS(r[9], 22);
571  VERIFY_BITS(c, 46);
572  /* [d 0 0 0 0 0 0 0 0 r9+((c-d*R1<<4)<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
573  /* [d 0 0 0 0 0 0 0 -d*R1 r9+(c<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
574  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
575 
576  d = c * (R0 >> 4) + t0;
577  VERIFY_BITS(d, 56);
578  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 d-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
579  r[0] = d & M; d >>= 26;
580  VERIFY_BITS(r[0], 26);
581  VERIFY_BITS(d, 30);
582  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1+d r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
583  d += c * (R1 >> 4) + t1;
584  VERIFY_BITS(d, 53);
585  VERIFY_CHECK(d <= 0x10000003FFFFBFULL);
586  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 d-c*R1>>4 r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
587  /* [r9 r8 r7 r6 r5 r4 r3 t2 d r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
588  r[1] = d & M; d >>= 26;
589  VERIFY_BITS(r[1], 26);
590  VERIFY_BITS(d, 27);
591  VERIFY_CHECK(d <= 0x4000000ULL);
592  /* [r9 r8 r7 r6 r5 r4 r3 t2+d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
593  d += t2;
594  VERIFY_BITS(d, 27);
595  /* [r9 r8 r7 r6 r5 r4 r3 d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
596  r[2] = d;
597  VERIFY_BITS(r[2], 27);
598  /* [r9 r8 r7 r6 r5 r4 r3 r2 r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
599 }
600 
601 SECP256K1_INLINE static void secp256k1_fe_sqr_inner(const uint32_t *a, uint32_t *r) {
602  VERIFY_BITS(a[0], 30);
603  VERIFY_BITS(a[1], 30);
604  VERIFY_BITS(a[2], 30);
605  VERIFY_BITS(a[3], 30);
606  VERIFY_BITS(a[4], 30);
607  VERIFY_BITS(a[5], 30);
608  VERIFY_BITS(a[6], 30);
609  VERIFY_BITS(a[7], 30);
610  VERIFY_BITS(a[8], 30);
611  VERIFY_BITS(a[9], 26);
612 
613  const uint32_t M = 0x3FFFFFFUL, R0 = 0x3D10UL, R1 = 0x400UL;
619  uint64_t c, d;
620 
621  d = (uint64_t)(a[0]*2) * a[9]
622  + (uint64_t)(a[1]*2) * a[8]
623  + (uint64_t)(a[2]*2) * a[7]
624  + (uint64_t)(a[3]*2) * a[6]
625  + (uint64_t)(a[4]*2) * a[5];
626  /* VERIFY_BITS(d, 64); */
627  /* [d 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
628  uint32_t t9 = d & M; d >>= 26;
629  VERIFY_BITS(t9, 26);
630  VERIFY_BITS(d, 38);
631  /* [d t9 0 0 0 0 0 0 0 0 0] = [p9 0 0 0 0 0 0 0 0 0] */
632 
633  c = (uint64_t)a[0] * a[0];
634  VERIFY_BITS(c, 60);
635  /* [d t9 0 0 0 0 0 0 0 0 c] = [p9 0 0 0 0 0 0 0 0 p0] */
636  d += (uint64_t)(a[1]*2) * a[9]
637  + (uint64_t)(a[2]*2) * a[8]
638  + (uint64_t)(a[3]*2) * a[7]
639  + (uint64_t)(a[4]*2) * a[6]
640  + (uint64_t)a[5] * a[5];
641  VERIFY_BITS(d, 63);
642  /* [d t9 0 0 0 0 0 0 0 0 c] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
643  uint64_t u0 = d & M; d >>= 26; c += u0 * R0;
644  VERIFY_BITS(u0, 26);
645  VERIFY_BITS(d, 37);
646  VERIFY_BITS(c, 61);
647  /* [d u0 t9 0 0 0 0 0 0 0 0 c-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
648  uint32_t t0 = c & M; c >>= 26; c += u0 * R1;
649  VERIFY_BITS(t0, 26);
650  VERIFY_BITS(c, 37);
651  /* [d u0 t9 0 0 0 0 0 0 0 c-u0*R1 t0-u0*R0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
652  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 0 p0] */
653 
654  c += (uint64_t)(a[0]*2) * a[1];
655  VERIFY_BITS(c, 62);
656  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p10 p9 0 0 0 0 0 0 0 p1 p0] */
657  d += (uint64_t)(a[2]*2) * a[9]
658  + (uint64_t)(a[3]*2) * a[8]
659  + (uint64_t)(a[4]*2) * a[7]
660  + (uint64_t)(a[5]*2) * a[6];
661  VERIFY_BITS(d, 63);
662  /* [d 0 t9 0 0 0 0 0 0 0 c t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
663  uint64_t u1 = d & M; d >>= 26; c += u1 * R0;
664  VERIFY_BITS(u1, 26);
665  VERIFY_BITS(d, 37);
666  VERIFY_BITS(c, 63);
667  /* [d u1 0 t9 0 0 0 0 0 0 0 c-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
668  uint32_t t1 = c & M; c >>= 26; c += u1 * R1;
669  VERIFY_BITS(t1, 26);
670  VERIFY_BITS(c, 38);
671  /* [d u1 0 t9 0 0 0 0 0 0 c-u1*R1 t1-u1*R0 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
672  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 0 p1 p0] */
673 
674  c += (uint64_t)(a[0]*2) * a[2]
675  + (uint64_t)a[1] * a[1];
676  VERIFY_BITS(c, 62);
677  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
678  d += (uint64_t)(a[3]*2) * a[9]
679  + (uint64_t)(a[4]*2) * a[8]
680  + (uint64_t)(a[5]*2) * a[7]
681  + (uint64_t)a[6] * a[6];
682  VERIFY_BITS(d, 63);
683  /* [d 0 0 t9 0 0 0 0 0 0 c t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
684  uint64_t u2 = d & M; d >>= 26; c += u2 * R0;
685  VERIFY_BITS(u2, 26);
686  VERIFY_BITS(d, 37);
687  VERIFY_BITS(c, 63);
688  /* [d u2 0 0 t9 0 0 0 0 0 0 c-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
689  uint32_t t2 = c & M; c >>= 26; c += u2 * R1;
690  VERIFY_BITS(t2, 26);
691  VERIFY_BITS(c, 38);
692  /* [d u2 0 0 t9 0 0 0 0 0 c-u2*R1 t2-u2*R0 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
693  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 0 p2 p1 p0] */
694 
695  c += (uint64_t)(a[0]*2) * a[3]
696  + (uint64_t)(a[1]*2) * a[2];
697  VERIFY_BITS(c, 63);
698  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
699  d += (uint64_t)(a[4]*2) * a[9]
700  + (uint64_t)(a[5]*2) * a[8]
701  + (uint64_t)(a[6]*2) * a[7];
702  VERIFY_BITS(d, 63);
703  /* [d 0 0 0 t9 0 0 0 0 0 c t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
704  uint64_t u3 = d & M; d >>= 26; c += u3 * R0;
705  VERIFY_BITS(u3, 26);
706  VERIFY_BITS(d, 37);
707  /* VERIFY_BITS(c, 64); */
708  /* [d u3 0 0 0 t9 0 0 0 0 0 c-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
709  uint32_t t3 = c & M; c >>= 26; c += u3 * R1;
710  VERIFY_BITS(t3, 26);
711  VERIFY_BITS(c, 39);
712  /* [d u3 0 0 0 t9 0 0 0 0 c-u3*R1 t3-u3*R0 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
713  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 0 p3 p2 p1 p0] */
714 
715  c += (uint64_t)(a[0]*2) * a[4]
716  + (uint64_t)(a[1]*2) * a[3]
717  + (uint64_t)a[2] * a[2];
718  VERIFY_BITS(c, 63);
719  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
720  d += (uint64_t)(a[5]*2) * a[9]
721  + (uint64_t)(a[6]*2) * a[8]
722  + (uint64_t)a[7] * a[7];
723  VERIFY_BITS(d, 62);
724  /* [d 0 0 0 0 t9 0 0 0 0 c t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
725  uint64_t u4 = d & M; d >>= 26; c += u4 * R0;
726  VERIFY_BITS(u4, 26);
727  VERIFY_BITS(d, 36);
728  /* VERIFY_BITS(c, 64); */
729  /* [d u4 0 0 0 0 t9 0 0 0 0 c-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
730  uint32_t t4 = c & M; c >>= 26; c += u4 * R1;
731  VERIFY_BITS(t4, 26);
732  VERIFY_BITS(c, 39);
733  /* [d u4 0 0 0 0 t9 0 0 0 c-u4*R1 t4-u4*R0 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
734  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 0 p4 p3 p2 p1 p0] */
735 
736  c += (uint64_t)(a[0]*2) * a[5]
737  + (uint64_t)(a[1]*2) * a[4]
738  + (uint64_t)(a[2]*2) * a[3];
739  VERIFY_BITS(c, 63);
740  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
741  d += (uint64_t)(a[6]*2) * a[9]
742  + (uint64_t)(a[7]*2) * a[8];
743  VERIFY_BITS(d, 62);
744  /* [d 0 0 0 0 0 t9 0 0 0 c t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
745  uint64_t u5 = d & M; d >>= 26; c += u5 * R0;
746  VERIFY_BITS(u5, 26);
747  VERIFY_BITS(d, 36);
748  /* VERIFY_BITS(c, 64); */
749  /* [d u5 0 0 0 0 0 t9 0 0 0 c-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
750  uint32_t t5 = c & M; c >>= 26; c += u5 * R1;
751  VERIFY_BITS(t5, 26);
752  VERIFY_BITS(c, 39);
753  /* [d u5 0 0 0 0 0 t9 0 0 c-u5*R1 t5-u5*R0 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
754  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 0 p5 p4 p3 p2 p1 p0] */
755 
756  c += (uint64_t)(a[0]*2) * a[6]
757  + (uint64_t)(a[1]*2) * a[5]
758  + (uint64_t)(a[2]*2) * a[4]
759  + (uint64_t)a[3] * a[3];
760  VERIFY_BITS(c, 63);
761  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
762  d += (uint64_t)(a[7]*2) * a[9]
763  + (uint64_t)a[8] * a[8];
764  VERIFY_BITS(d, 61);
765  /* [d 0 0 0 0 0 0 t9 0 0 c t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
766  uint64_t u6 = d & M; d >>= 26; c += u6 * R0;
767  VERIFY_BITS(u6, 26);
768  VERIFY_BITS(d, 35);
769  /* VERIFY_BITS(c, 64); */
770  /* [d u6 0 0 0 0 0 0 t9 0 0 c-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
771  uint32_t t6 = c & M; c >>= 26; c += u6 * R1;
772  VERIFY_BITS(t6, 26);
773  VERIFY_BITS(c, 39);
774  /* [d u6 0 0 0 0 0 0 t9 0 c-u6*R1 t6-u6*R0 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
775  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 0 p6 p5 p4 p3 p2 p1 p0] */
776 
777  c += (uint64_t)(a[0]*2) * a[7]
778  + (uint64_t)(a[1]*2) * a[6]
779  + (uint64_t)(a[2]*2) * a[5]
780  + (uint64_t)(a[3]*2) * a[4];
781  /* VERIFY_BITS(c, 64); */
782  VERIFY_CHECK(c <= 0x8000007C00000007ULL);
783  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
784  d += (uint64_t)(a[8]*2) * a[9];
785  VERIFY_BITS(d, 58);
786  /* [d 0 0 0 0 0 0 0 t9 0 c t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
787  uint64_t u7 = d & M; d >>= 26; c += u7 * R0;
788  VERIFY_BITS(u7, 26);
789  VERIFY_BITS(d, 32);
790  /* VERIFY_BITS(c, 64); */
791  VERIFY_CHECK(c <= 0x800001703FFFC2F7ULL);
792  /* [d u7 0 0 0 0 0 0 0 t9 0 c-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
793  uint32_t t7 = c & M; c >>= 26; c += u7 * R1;
794  VERIFY_BITS(t7, 26);
795  VERIFY_BITS(c, 38);
796  /* [d u7 0 0 0 0 0 0 0 t9 c-u7*R1 t7-u7*R0 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
797  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 0 p7 p6 p5 p4 p3 p2 p1 p0] */
798 
799  c += (uint64_t)(a[0]*2) * a[8]
800  + (uint64_t)(a[1]*2) * a[7]
801  + (uint64_t)(a[2]*2) * a[6]
802  + (uint64_t)(a[3]*2) * a[5]
803  + (uint64_t)a[4] * a[4];
804  /* VERIFY_BITS(c, 64); */
805  VERIFY_CHECK(c <= 0x9000007B80000008ULL);
806  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
807  d += (uint64_t)a[9] * a[9];
808  VERIFY_BITS(d, 57);
809  /* [d 0 0 0 0 0 0 0 0 t9 c t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
810  uint64_t u8 = d & M; d >>= 26; c += u8 * R0;
811  VERIFY_BITS(u8, 26);
812  VERIFY_BITS(d, 31);
813  /* VERIFY_BITS(c, 64); */
814  VERIFY_CHECK(c <= 0x9000016FBFFFC2F8ULL);
815  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 t3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
816 
817  r[3] = t3;
818  VERIFY_BITS(r[3], 26);
819  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 t4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
820  r[4] = t4;
821  VERIFY_BITS(r[4], 26);
822  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 t5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
823  r[5] = t5;
824  VERIFY_BITS(r[5], 26);
825  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 t6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
826  r[6] = t6;
827  VERIFY_BITS(r[6], 26);
828  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 t7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
829  r[7] = t7;
830  VERIFY_BITS(r[7], 26);
831  /* [d u8 0 0 0 0 0 0 0 0 t9 c-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
832 
833  r[8] = c & M; c >>= 26; c += u8 * R1;
834  VERIFY_BITS(r[8], 26);
835  VERIFY_BITS(c, 39);
836  /* [d u8 0 0 0 0 0 0 0 0 t9+c-u8*R1 r8-u8*R0 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
837  /* [d 0 0 0 0 0 0 0 0 0 t9+c r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
838  c += d * R0 + t9;
839  VERIFY_BITS(c, 45);
840  /* [d 0 0 0 0 0 0 0 0 0 c-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
841  r[9] = c & (M >> 4); c >>= 22; c += d * (R1 << 4);
842  VERIFY_BITS(r[9], 22);
843  VERIFY_BITS(c, 46);
844  /* [d 0 0 0 0 0 0 0 0 r9+((c-d*R1<<4)<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
845  /* [d 0 0 0 0 0 0 0 -d*R1 r9+(c<<22)-d*R0 r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
846  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 t0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
847 
848  d = c * (R0 >> 4) + t0;
849  VERIFY_BITS(d, 56);
850  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1 d-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
851  r[0] = d & M; d >>= 26;
852  VERIFY_BITS(r[0], 26);
853  VERIFY_BITS(d, 30);
854  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 t1+d r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
855  d += c * (R1 >> 4) + t1;
856  VERIFY_BITS(d, 53);
857  VERIFY_CHECK(d <= 0x10000003FFFFBFULL);
858  /* [r9+(c<<22) r8 r7 r6 r5 r4 r3 t2 d-c*R1>>4 r0-c*R0>>4] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
859  /* [r9 r8 r7 r6 r5 r4 r3 t2 d r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
860  r[1] = d & M; d >>= 26;
861  VERIFY_BITS(r[1], 26);
862  VERIFY_BITS(d, 27);
863  VERIFY_CHECK(d <= 0x4000000ULL);
864  /* [r9 r8 r7 r6 r5 r4 r3 t2+d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
865  d += t2;
866  VERIFY_BITS(d, 27);
867  /* [r9 r8 r7 r6 r5 r4 r3 d r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
868  r[2] = d;
869  VERIFY_BITS(r[2], 27);
870  /* [r9 r8 r7 r6 r5 r4 r3 r2 r1 r0] = [p18 p17 p16 p15 p14 p13 p12 p11 p10 p9 p8 p7 p6 p5 p4 p3 p2 p1 p0] */
871 }
872 
873 
874 static void secp256k1_fe_mul(secp256k1_fe_t *r, const secp256k1_fe_t *a, const secp256k1_fe_t * SECP256K1_RESTRICT b) {
875 #ifdef VERIFY
876  VERIFY_CHECK(a->magnitude <= 8);
877  VERIFY_CHECK(b->magnitude <= 8);
878  secp256k1_fe_verify(a);
879  secp256k1_fe_verify(b);
880  VERIFY_CHECK(r != b);
881 #endif
882  secp256k1_fe_mul_inner(a->n, b->n, r->n);
883 #ifdef VERIFY
884  r->magnitude = 1;
885  r->normalized = 0;
886  secp256k1_fe_verify(r);
887 #endif
888 }
889 
890 static void secp256k1_fe_sqr(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
891 #ifdef VERIFY
892  VERIFY_CHECK(a->magnitude <= 8);
893  secp256k1_fe_verify(a);
894 #endif
895  secp256k1_fe_sqr_inner(a->n, r->n);
896 #ifdef VERIFY
897  r->magnitude = 1;
898  r->normalized = 0;
899  secp256k1_fe_verify(r);
900 #endif
901 }
902 
903 static void secp256k1_fe_cmov(secp256k1_fe_t *r, const secp256k1_fe_t *a, int flag) {
904  uint32_t mask0 = flag + ~((uint32_t)0), mask1 = ~mask0;
905  r->n[0] = (r->n[0] & mask0) | (a->n[0] & mask1);
906  r->n[1] = (r->n[1] & mask0) | (a->n[1] & mask1);
907  r->n[2] = (r->n[2] & mask0) | (a->n[2] & mask1);
908  r->n[3] = (r->n[3] & mask0) | (a->n[3] & mask1);
909  r->n[4] = (r->n[4] & mask0) | (a->n[4] & mask1);
910  r->n[5] = (r->n[5] & mask0) | (a->n[5] & mask1);
911  r->n[6] = (r->n[6] & mask0) | (a->n[6] & mask1);
912  r->n[7] = (r->n[7] & mask0) | (a->n[7] & mask1);
913  r->n[8] = (r->n[8] & mask0) | (a->n[8] & mask1);
914  r->n[9] = (r->n[9] & mask0) | (a->n[9] & mask1);
915 #ifdef VERIFY
916  if (flag) {
917  r->magnitude = a->magnitude;
918  r->normalized = a->normalized;
919  }
920 #endif
921 }
922 
923 #endif
VERIFY_CHECK
#define VERIFY_CHECK(cond)
Definition: util.h:61
b
void const uint64_t * b
Definition: field_5x52_asm_impl.h:10
SECP256K1_RESTRICT
#define SECP256K1_RESTRICT
Definition: util.h:74
secp256k1_fe_t::n
uint32_t n[10]
Definition: field_10x26.h:18
util.h
r
void const uint64_t uint64_t * r
Definition: field_5x52_asm_impl.h:10
secp256k1_fe_t
Definition: field_10x26.h:12
num.h
M
#define M(x)
VERIFY_BITS
#define VERIFY_BITS(x, n)
Definition: field_10x26_impl.h:271
SECP256K1_INLINE
#define SECP256K1_INLINE
Definition: secp256k1.h:23
field.h
Generated on Tue Apr 28 2026 00:02:58 for PRCYCoin by   doxygen 1.8.17