Bitcoin ABC  0.28.12
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 https://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(SECP256K1_WIDEMUL_INT128)
17 #include "field_5x52_impl.h"
18 #elif defined(SECP256K1_WIDEMUL_INT64)
19 #include "field_10x26_impl.h"
20 #else
21 #error "Please select wide multiplication implementation"
22 #endif
23 
25  secp256k1_fe na;
26  secp256k1_fe_negate(&na, a, 1);
27  secp256k1_fe_add(&na, b);
29 }
30 
32  secp256k1_fe na;
33  secp256k1_fe_negate(&na, a, 1);
34  secp256k1_fe_add(&na, b);
36 }
37 
38 static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
48  secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
49  int j;
50 
51  VERIFY_CHECK(r != a);
52 
58  secp256k1_fe_sqr(&x2, a);
59  secp256k1_fe_mul(&x2, &x2, a);
60 
61  secp256k1_fe_sqr(&x3, &x2);
62  secp256k1_fe_mul(&x3, &x3, a);
63 
64  x6 = x3;
65  for (j=0; j<3; j++) {
66  secp256k1_fe_sqr(&x6, &x6);
67  }
68  secp256k1_fe_mul(&x6, &x6, &x3);
69 
70  x9 = x6;
71  for (j=0; j<3; j++) {
72  secp256k1_fe_sqr(&x9, &x9);
73  }
74  secp256k1_fe_mul(&x9, &x9, &x3);
75 
76  x11 = x9;
77  for (j=0; j<2; j++) {
78  secp256k1_fe_sqr(&x11, &x11);
79  }
80  secp256k1_fe_mul(&x11, &x11, &x2);
81 
82  x22 = x11;
83  for (j=0; j<11; j++) {
84  secp256k1_fe_sqr(&x22, &x22);
85  }
86  secp256k1_fe_mul(&x22, &x22, &x11);
87 
88  x44 = x22;
89  for (j=0; j<22; j++) {
90  secp256k1_fe_sqr(&x44, &x44);
91  }
92  secp256k1_fe_mul(&x44, &x44, &x22);
93 
94  x88 = x44;
95  for (j=0; j<44; j++) {
96  secp256k1_fe_sqr(&x88, &x88);
97  }
98  secp256k1_fe_mul(&x88, &x88, &x44);
99 
100  x176 = x88;
101  for (j=0; j<88; j++) {
102  secp256k1_fe_sqr(&x176, &x176);
103  }
104  secp256k1_fe_mul(&x176, &x176, &x88);
105 
106  x220 = x176;
107  for (j=0; j<44; j++) {
108  secp256k1_fe_sqr(&x220, &x220);
109  }
110  secp256k1_fe_mul(&x220, &x220, &x44);
111 
112  x223 = x220;
113  for (j=0; j<3; j++) {
114  secp256k1_fe_sqr(&x223, &x223);
115  }
116  secp256k1_fe_mul(&x223, &x223, &x3);
117 
118  /* The final result is then assembled using a sliding window over the blocks. */
119 
120  t1 = x223;
121  for (j=0; j<23; j++) {
122  secp256k1_fe_sqr(&t1, &t1);
123  }
124  secp256k1_fe_mul(&t1, &t1, &x22);
125  for (j=0; j<6; j++) {
126  secp256k1_fe_sqr(&t1, &t1);
127  }
128  secp256k1_fe_mul(&t1, &t1, &x2);
129  secp256k1_fe_sqr(&t1, &t1);
130  secp256k1_fe_sqr(r, &t1);
131 
132  /* Check that a square root was actually calculated */
133 
134  secp256k1_fe_sqr(&t1, r);
135  return secp256k1_fe_equal(&t1, a);
136 }
137 
139  secp256k1_fe r;
140  return secp256k1_fe_sqrt(&r, a);
141 }
142 
143 static const secp256k1_fe secp256k1_fe_one = SECP256K1_FE_CONST(0, 0, 0, 0, 0, 0, 0, 1);
144 
145 #endif /* SECP256K1_FIELD_IMPL_H */
static void secp256k1_fe_negate(secp256k1_fe *r, const secp256k1_fe *a, int m)
Set a field element equal to the additive inverse of another.
static void secp256k1_fe_mul(secp256k1_fe *r, const secp256k1_fe *a, const secp256k1_fe *SECP256K1_RESTRICT b)
Sets a field element to be the product of two others.
static int secp256k1_fe_normalizes_to_zero_var(secp256k1_fe *r)
Verify whether a field element represents zero i.e.
static void secp256k1_fe_sqr(secp256k1_fe *r, const secp256k1_fe *a)
Sets a field element to be the square of another.
static void secp256k1_fe_add(secp256k1_fe *r, const secp256k1_fe *a)
Adds a field element to another.
static int secp256k1_fe_normalizes_to_zero(secp256k1_fe *r)
Verify whether a field element represents zero i.e.
#define SECP256K1_FE_CONST(d7, d6, d5, d4, d3, d2, d1, d0)
Definition: field_10x26.h:40
static int secp256k1_fe_is_quad_var(const secp256k1_fe *a)
Definition: field_impl.h:138
static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a)
Definition: field_impl.h:38
static SECP256K1_INLINE int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b)
Definition: field_impl.h:31
static const secp256k1_fe secp256k1_fe_one
Definition: field_impl.h:143
static SECP256K1_INLINE int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b)
Definition: field_impl.h:24
#define VERIFY_CHECK(cond)
Definition: util.h:68
#define SECP256K1_INLINE
Definition: secp256k1.h:124