PRCYCoin  2.0.0.7rc1
P2P Digital Currency
field_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_IMPL_H_
8 #define _SECP256K1_FIELD_IMPL_H_
9 
10 #if defined HAVE_CONFIG_H
11 #include "libsecp256k1-config.h"
12 #endif
13 
14 #include "util.h"
15 
16 #if defined(USE_FIELD_GMP)
17 #include "field_gmp_impl.h"
18 #elif defined(USE_FIELD_10X26)
19 #include "field_10x26_impl.h"
20 #elif defined(USE_FIELD_5X52)
21 #include "field_5x52_impl.h"
22 #else
23 #error "Please select field implementation"
24 #endif
25 
26 static void secp256k1_fe_get_hex(char *r, int *rlen, const secp256k1_fe_t *a) {
27  if (*rlen < 65) {
28  *rlen = 65;
29  return;
30  }
31  *rlen = 65;
32  unsigned char tmp[32];
33  secp256k1_fe_t b = *a;
34  secp256k1_fe_normalize(&b);
35  secp256k1_fe_get_b32(tmp, &b);
36  for (int i=0; i<32; i++) {
37  static const char *c = "0123456789ABCDEF";
38  r[2*i] = c[(tmp[i] >> 4) & 0xF];
39  r[2*i+1] = c[(tmp[i]) & 0xF];
40  }
41  r[64] = 0x00;
42 }
43 
44 static int secp256k1_fe_set_hex(secp256k1_fe_t *r, const char *a, int alen) {
45  unsigned char tmp[32] = {};
46  static const int cvt[256] = {0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
47  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
48  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
49  0, 1, 2, 3, 4, 5, 6,7,8,9,0,0,0,0,0,0,
50  0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
51  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
52  0,10,11,12,13,14,15,0,0,0,0,0,0,0,0,0,
53  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
54  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
55  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
56  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
57  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
58  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
59  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
60  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,
61  0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0};
62  for (int i=0; i<32; i++) {
63  if (alen > i*2)
64  tmp[32 - alen/2 + i] = (cvt[(unsigned char)a[2*i]] << 4) + cvt[(unsigned char)a[2*i+1]];
65  }
66  return secp256k1_fe_set_b32(r, tmp);
67 }
68 
69 static int secp256k1_fe_sqrt(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
70 
76  secp256k1_fe_t x2;
77  secp256k1_fe_sqr(&x2, a);
78  secp256k1_fe_mul(&x2, &x2, a);
79 
80  secp256k1_fe_t x3;
81  secp256k1_fe_sqr(&x3, &x2);
82  secp256k1_fe_mul(&x3, &x3, a);
83 
84  secp256k1_fe_t x6 = x3;
85  for (int j=0; j<3; j++) secp256k1_fe_sqr(&x6, &x6);
86  secp256k1_fe_mul(&x6, &x6, &x3);
87 
88  secp256k1_fe_t x9 = x6;
89  for (int j=0; j<3; j++) secp256k1_fe_sqr(&x9, &x9);
90  secp256k1_fe_mul(&x9, &x9, &x3);
91 
92  secp256k1_fe_t x11 = x9;
93  for (int j=0; j<2; j++) secp256k1_fe_sqr(&x11, &x11);
94  secp256k1_fe_mul(&x11, &x11, &x2);
95 
96  secp256k1_fe_t x22 = x11;
97  for (int j=0; j<11; j++) secp256k1_fe_sqr(&x22, &x22);
98  secp256k1_fe_mul(&x22, &x22, &x11);
99 
100  secp256k1_fe_t x44 = x22;
101  for (int j=0; j<22; j++) secp256k1_fe_sqr(&x44, &x44);
102  secp256k1_fe_mul(&x44, &x44, &x22);
103 
104  secp256k1_fe_t x88 = x44;
105  for (int j=0; j<44; j++) secp256k1_fe_sqr(&x88, &x88);
106  secp256k1_fe_mul(&x88, &x88, &x44);
107 
108  secp256k1_fe_t x176 = x88;
109  for (int j=0; j<88; j++) secp256k1_fe_sqr(&x176, &x176);
110  secp256k1_fe_mul(&x176, &x176, &x88);
111 
112  secp256k1_fe_t x220 = x176;
113  for (int j=0; j<44; j++) secp256k1_fe_sqr(&x220, &x220);
114  secp256k1_fe_mul(&x220, &x220, &x44);
115 
116  secp256k1_fe_t x223 = x220;
117  for (int j=0; j<3; j++) secp256k1_fe_sqr(&x223, &x223);
118  secp256k1_fe_mul(&x223, &x223, &x3);
119 
120  /* The final result is then assembled using a sliding window over the blocks. */
121 
122  secp256k1_fe_t t1 = x223;
123  for (int j=0; j<23; j++) secp256k1_fe_sqr(&t1, &t1);
124  secp256k1_fe_mul(&t1, &t1, &x22);
125  for (int j=0; j<6; j++) secp256k1_fe_sqr(&t1, &t1);
126  secp256k1_fe_mul(&t1, &t1, &x2);
127  secp256k1_fe_sqr(&t1, &t1);
128  secp256k1_fe_sqr(r, &t1);
129 
130  /* Check that a square root was actually calculated */
131 
132  secp256k1_fe_sqr(&t1, r);
133  secp256k1_fe_negate(&t1, &t1, 1);
134  secp256k1_fe_add(&t1, a);
135  secp256k1_fe_normalize(&t1);
136  return secp256k1_fe_is_zero(&t1);
137 }
138 
139 static void secp256k1_fe_inv(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
140 
146  secp256k1_fe_t x2;
147  secp256k1_fe_sqr(&x2, a);
148  secp256k1_fe_mul(&x2, &x2, a);
149 
150  secp256k1_fe_t x3;
151  secp256k1_fe_sqr(&x3, &x2);
152  secp256k1_fe_mul(&x3, &x3, a);
153 
154  secp256k1_fe_t x6 = x3;
155  for (int j=0; j<3; j++) secp256k1_fe_sqr(&x6, &x6);
156  secp256k1_fe_mul(&x6, &x6, &x3);
157 
158  secp256k1_fe_t x9 = x6;
159  for (int j=0; j<3; j++) secp256k1_fe_sqr(&x9, &x9);
160  secp256k1_fe_mul(&x9, &x9, &x3);
161 
162  secp256k1_fe_t x11 = x9;
163  for (int j=0; j<2; j++) secp256k1_fe_sqr(&x11, &x11);
164  secp256k1_fe_mul(&x11, &x11, &x2);
165 
166  secp256k1_fe_t x22 = x11;
167  for (int j=0; j<11; j++) secp256k1_fe_sqr(&x22, &x22);
168  secp256k1_fe_mul(&x22, &x22, &x11);
169 
170  secp256k1_fe_t x44 = x22;
171  for (int j=0; j<22; j++) secp256k1_fe_sqr(&x44, &x44);
172  secp256k1_fe_mul(&x44, &x44, &x22);
173 
174  secp256k1_fe_t x88 = x44;
175  for (int j=0; j<44; j++) secp256k1_fe_sqr(&x88, &x88);
176  secp256k1_fe_mul(&x88, &x88, &x44);
177 
178  secp256k1_fe_t x176 = x88;
179  for (int j=0; j<88; j++) secp256k1_fe_sqr(&x176, &x176);
180  secp256k1_fe_mul(&x176, &x176, &x88);
181 
182  secp256k1_fe_t x220 = x176;
183  for (int j=0; j<44; j++) secp256k1_fe_sqr(&x220, &x220);
184  secp256k1_fe_mul(&x220, &x220, &x44);
185 
186  secp256k1_fe_t x223 = x220;
187  for (int j=0; j<3; j++) secp256k1_fe_sqr(&x223, &x223);
188  secp256k1_fe_mul(&x223, &x223, &x3);
189 
190  /* The final result is then assembled using a sliding window over the blocks. */
191 
192  secp256k1_fe_t t1 = x223;
193  for (int j=0; j<23; j++) secp256k1_fe_sqr(&t1, &t1);
194  secp256k1_fe_mul(&t1, &t1, &x22);
195  for (int j=0; j<5; j++) secp256k1_fe_sqr(&t1, &t1);
196  secp256k1_fe_mul(&t1, &t1, a);
197  for (int j=0; j<3; j++) secp256k1_fe_sqr(&t1, &t1);
198  secp256k1_fe_mul(&t1, &t1, &x2);
199  for (int j=0; j<2; j++) secp256k1_fe_sqr(&t1, &t1);
200  secp256k1_fe_mul(r, a, &t1);
201 }
202 
203 static void secp256k1_fe_inv_var(secp256k1_fe_t *r, const secp256k1_fe_t *a) {
204 #if defined(USE_FIELD_INV_BUILTIN)
205  secp256k1_fe_inv(r, a);
206 #elif defined(USE_FIELD_INV_NUM)
207  unsigned char b[32];
208  secp256k1_fe_t c = *a;
209  secp256k1_fe_normalize(&c);
210  secp256k1_fe_get_b32(b, &c);
211  secp256k1_num_t n;
212  secp256k1_num_set_bin(&n, b, 32);
213  secp256k1_num_mod_inverse(&n, &n, &secp256k1_fe_consts->p);
214  secp256k1_num_get_bin(b, 32, &n);
215  VERIFY_CHECK(secp256k1_fe_set_b32(r, b));
216 #else
217 #error "Please select field inverse implementation"
218 #endif
219 }
220 
221 static void secp256k1_fe_inv_all(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
222  if (len < 1)
223  return;
224 
225  VERIFY_CHECK((r + len <= a) || (a + len <= r));
226 
227  r[0] = a[0];
228 
229  size_t i = 0;
230  while (++i < len) {
231  secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
232  }
233 
234  secp256k1_fe_t u; secp256k1_fe_inv(&u, &r[--i]);
235 
236  while (i > 0) {
237  int j = i--;
238  secp256k1_fe_mul(&r[j], &r[i], &u);
239  secp256k1_fe_mul(&u, &u, &a[j]);
240  }
241 
242  r[0] = u;
243 }
244 
245 static void secp256k1_fe_inv_all_var(size_t len, secp256k1_fe_t r[len], const secp256k1_fe_t a[len]) {
246  if (len < 1)
247  return;
248 
249  VERIFY_CHECK((r + len <= a) || (a + len <= r));
250 
251  r[0] = a[0];
252 
253  size_t i = 0;
254  while (++i < len) {
255  secp256k1_fe_mul(&r[i], &r[i - 1], &a[i]);
256  }
257 
258  secp256k1_fe_t u; secp256k1_fe_inv_var(&u, &r[--i]);
259 
260  while (i > 0) {
261  int j = i--;
262  secp256k1_fe_mul(&r[j], &r[i], &u);
263  secp256k1_fe_mul(&u, &u, &a[j]);
264  }
265 
266  r[0] = u;
267 }
268 
269 static void secp256k1_fe_start(void) {
270 #ifndef USE_NUM_NONE
271  static const unsigned char secp256k1_fe_consts_p[] = {
272  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
273  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
274  0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
275  0xFF,0xFF,0xFF,0xFE,0xFF,0xFF,0xFC,0x2F
276  };
277 #endif
278  if (secp256k1_fe_consts == NULL) {
279  secp256k1_fe_inner_start();
280  secp256k1_fe_consts_t *ret = (secp256k1_fe_consts_t*)malloc(sizeof(secp256k1_fe_consts_t));
281 #ifndef USE_NUM_NONE
282  secp256k1_num_set_bin(&ret->p, secp256k1_fe_consts_p, sizeof(secp256k1_fe_consts_p));
283 #endif
284  secp256k1_fe_consts = ret;
285  }
286 }
287 
288 static void secp256k1_fe_stop(void) {
289  if (secp256k1_fe_consts != NULL) {
290  secp256k1_fe_consts_t *c = (secp256k1_fe_consts_t*)secp256k1_fe_consts;
291  free((void*)c);
292  secp256k1_fe_consts = NULL;
293  secp256k1_fe_inner_stop();
294  }
295 }
296 
297 #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_fe_consts_t
Field element module.
Definition: field.h:35
util.h
secp256k1_num_t
Definition: num_gmp.h:14
field_gmp_impl.h
r
void const uint64_t uint64_t * r
Definition: field_5x52_asm_impl.h:10
secp256k1_fe_consts_t::p
secp256k1_num_t p
Definition: field.h:41
secp256k1_fe_t
Definition: field_10x26.h:12
Generated on Tue Apr 28 2026 00:02:58 for PRCYCoin by   doxygen 1.8.17