Electroneum
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 #include "util.h"
11 
12 #if defined(SECP256K1_WIDEMUL_INT128)
13 #include "field_5x52_impl.h"
14 #elif defined(SECP256K1_WIDEMUL_INT64)
15 #include "field_10x26_impl.h"
16 #else
17 #error "Please select wide multiplication implementation"
18 #endif
19 
20 SECP256K1_INLINE static int secp256k1_fe_equal(const secp256k1_fe *a, const secp256k1_fe *b) {
21  secp256k1_fe na;
22  secp256k1_fe_negate(&na, a, 1);
23  secp256k1_fe_add(&na, b);
24  return secp256k1_fe_normalizes_to_zero(&na);
25 }
26 
27 SECP256K1_INLINE static int secp256k1_fe_equal_var(const secp256k1_fe *a, const secp256k1_fe *b) {
28  secp256k1_fe na;
29  secp256k1_fe_negate(&na, a, 1);
30  secp256k1_fe_add(&na, b);
31  return secp256k1_fe_normalizes_to_zero_var(&na);
32 }
33 
34 static int secp256k1_fe_sqrt(secp256k1_fe *r, const secp256k1_fe *a) {
44  secp256k1_fe x2, x3, x6, x9, x11, x22, x44, x88, x176, x220, x223, t1;
45  int j;
46 
47  VERIFY_CHECK(r != a);
48 
54  secp256k1_fe_sqr(&x2, a);
55  secp256k1_fe_mul(&x2, &x2, a);
56 
57  secp256k1_fe_sqr(&x3, &x2);
58  secp256k1_fe_mul(&x3, &x3, a);
59 
60  x6 = x3;
61  for (j=0; j<3; j++) {
62  secp256k1_fe_sqr(&x6, &x6);
63  }
64  secp256k1_fe_mul(&x6, &x6, &x3);
65 
66  x9 = x6;
67  for (j=0; j<3; j++) {
68  secp256k1_fe_sqr(&x9, &x9);
69  }
70  secp256k1_fe_mul(&x9, &x9, &x3);
71 
72  x11 = x9;
73  for (j=0; j<2; j++) {
74  secp256k1_fe_sqr(&x11, &x11);
75  }
76  secp256k1_fe_mul(&x11, &x11, &x2);
77 
78  x22 = x11;
79  for (j=0; j<11; j++) {
80  secp256k1_fe_sqr(&x22, &x22);
81  }
82  secp256k1_fe_mul(&x22, &x22, &x11);
83 
84  x44 = x22;
85  for (j=0; j<22; j++) {
86  secp256k1_fe_sqr(&x44, &x44);
87  }
88  secp256k1_fe_mul(&x44, &x44, &x22);
89 
90  x88 = x44;
91  for (j=0; j<44; j++) {
92  secp256k1_fe_sqr(&x88, &x88);
93  }
94  secp256k1_fe_mul(&x88, &x88, &x44);
95 
96  x176 = x88;
97  for (j=0; j<88; j++) {
98  secp256k1_fe_sqr(&x176, &x176);
99  }
100  secp256k1_fe_mul(&x176, &x176, &x88);
101 
102  x220 = x176;
103  for (j=0; j<44; j++) {
104  secp256k1_fe_sqr(&x220, &x220);
105  }
106  secp256k1_fe_mul(&x220, &x220, &x44);
107 
108  x223 = x220;
109  for (j=0; j<3; j++) {
110  secp256k1_fe_sqr(&x223, &x223);
111  }
112  secp256k1_fe_mul(&x223, &x223, &x3);
113 
114  /* The final result is then assembled using a sliding window over the blocks. */
115 
116  t1 = x223;
117  for (j=0; j<23; j++) {
118  secp256k1_fe_sqr(&t1, &t1);
119  }
120  secp256k1_fe_mul(&t1, &t1, &x22);
121  for (j=0; j<6; j++) {
122  secp256k1_fe_sqr(&t1, &t1);
123  }
124  secp256k1_fe_mul(&t1, &t1, &x2);
125  secp256k1_fe_sqr(&t1, &t1);
126  secp256k1_fe_sqr(r, &t1);
127 
128  /* Check that a square root was actually calculated */
129 
130  secp256k1_fe_sqr(&t1, r);
131  return secp256k1_fe_equal(&t1, a);
132 }
133 
134 #endif /* SECP256K1_FIELD_IMPL_H */
#define VERIFY_CHECK(cond)
Definition: util.h:96
#define SECP256K1_INLINE
Definition: secp256k1.h:131
const GenericPointer< typename T::ValueType > T2 T::AllocatorType & a
Definition: pointer.h:1124
t1
Definition: pow22523.h:58