Let us walk on the 3-isogeny graph
Loading...
Searching...
No Matches
Functions
isogeny_walks.h File Reference
#include "../common/fp/mulx/fp.h"
#include "../common/mont.h"
#include "../common/primes.h"
Include dependency graph for isogeny_walks.h:
This graph shows which files directly or indirectly include this file:

Go to the source code of this file.

Functions

void isogeny_walks_get_points_3_fp (fp *output, const proj input_A)
 
void isogeny_walks_to_montgomery_model_3_fp (fp *output_A, const fp *input_t)
 
void isogeny_walks_3_fp (fp output_A, const proj input_A, size_t input_length, uint8_t direction)
 

Function Documentation

◆ isogeny_walks_3_fp()

void isogeny_walks_3_fp ( fp  output_A,
const proj  input_A,
size_t  input_length,
uint8_t  direction 
)

Definition at line 236 of file isogeny_walks_3_fp.c.

236 {
237 (void)input_length;
238 fp aux[2], num_den[3];
239
240 isogeny_walks_get_points_3_fp(num_den, input_A);
241
242 fp_cmov(&aux[0], (const fp*)num_den[0], direction);
243 fp_cmov(&aux[0], (const fp*)num_den[1], direction ^ 1);
244 fp_copy(aux[1], num_den[2]);
245
246 for(int i = 0; i < BOUND; i++){
247 fp t[2] = {0};
248 uint64_t d = constant_time_is_lessthan_u64(i, input_length);
249 isogeny_walks_to_montgomery_model_3_fp(t, (const fp*)aux);
250 fp_cmov(&aux[0], (const fp*)t[0], d);
251 fp_cmov(&aux[1], (const fp*)t[1], d);
252 }
253 isogeny_to_montgomery(output_A, (const fp*)aux);
254}
isogeny_walks_get_points_3_fp
void isogeny_walks_get_points_3_fp(fp_t *output, const fp_t *input_A)
Definition isogeny_walks_3_fp.c:18
isogeny_to_montgomery
void isogeny_to_montgomery(fp_t output_A, const fp_t *input_t)
Definition isogeny_walks_3_fp.c:183
isogeny_walks_to_montgomery_model_3_fp
void isogeny_walks_to_montgomery_model_3_fp(fp_t *output_A, const fp_t *input_t)
Definition isogeny_walks_3_fp.c:144
BOUND
#define BOUND
Definition isogeny_walks_3_fp.c:229
fp
uint64_t fp[NUMBER_OF_WORDS]
Definition fp-gmp.h:22
fp_cmov
#define fp_cmov
Definition fp-gmp.h:323
fp_copy
#define fp_copy
Definition fp-gmp.h:79
pip._vendor.packaging._musllinux.t
t
Definition _musllinux.py:136
pip._vendor.rich.pretty.d
d
Definition pretty.py:949
i
for i
Definition prime_search.m:10
constant_time_is_lessthan_u64
uint64_t constant_time_is_lessthan_u64(uint64_t x, uint64_t y)
Definition utilities.c:58

References BOUND, constant_time_is_lessthan_u64(), fp_cmov, fp_copy, i, isogeny_to_montgomery(), isogeny_walks_get_points_3_fp(), and isogeny_walks_to_montgomery_model_3_fp().

Here is the call graph for this function:

◆ isogeny_walks_get_points_3_fp()

void isogeny_walks_get_points_3_fp ( fp *  output,
const proj  input_A 
)

Definition at line 26 of file isogeny_walks_3_fp.c.

26 {
27 fp A_times_one_third, A_squared, C_squared;
28 fp t, r, s, u, aux, tmp, y;
29 fp s0, s1, s2, s0_squared, v;
30
31 // input_A.x is A
32 // input_A.z is C
33 // A_times_one_third = A * one_third # M𝒸
34 fp_mul(A_times_one_third, ONE_THIRD, input_A.x);
35 // A_squared = A**2 # S
36 fp_sqr(A_squared, input_A.x);
37 // C_squared = C**2 # S
38 fp_sqr(C_squared, input_A.z);
39
40 // t = (3 * C_squared - A_squared) * one_ninth # M𝒸 + 3A
41 fp_add(t, C_squared, C_squared);
42 fp_add(t, t, C_squared);
43 fp_sub(t, t, A_squared);
44 fp_mul(t, ONE_NINTH, t);
45
46 // r = 16 * (A_squared * A) * one_by_27 # M + M𝒸 + 4A
47 fp_mul(r, A_squared, input_A.x);
48 fp_mul(r, ONE_BY_27, r);
49 fp_add(r, r, r);
50 fp_add(r, r, r);
51 fp_add(r, r, r);
52 fp_add(r, r, r);
53
54 // s = 8 * A_times_one_third # 3A
55 fp_add(s, A_times_one_third, A_times_one_third);
56 fp_add(s, s, s);
57 fp_add(s, s, s);
58
59 // u = r - s * C_squared # M + A
60 fp_mul(u, s, C_squared);
61 fp_sub(u, r, u);
62
63 // aux = 2*C_squared**2 # S + A
64 fp_sqr(aux, C_squared);
65 fp_add(aux, aux, aux);
66 // y = 4 * C_squared # 2A
67 fp_add(y, C_squared, C_squared);
68 fp_add(y, y, y);
69 // y = y - A_squared # A
70 fp_sub(y, y, A_squared);
71 // y = aux * y # M
72 fp_mul(y, aux, y);
73
74 // y = t + one_third * setup['curt'](y) # M𝒸 + A + E (TOTAL = S + M + Mc + 5A + E)
75 fp_curt(y, y);
76 fp_mul(y, y, ONE_THIRD);
77 fp_add(y, y, t);
78
79 // r = 2 * y # A
80 fp_add(r, y, y);
81 // s = 6 * t # 3A
82 fp_add(s, t, t);
83 fp_add(t, s, s);
84 fp_add(s, s, t);
85
86 // s0 = setup['sqrt'](r - s) # A + E
87 fp_sub(s0, r, s);
88 fp_sqrt(&s0);
89
90 // s0_squared = s0**2 # S
91 fp_sqr(s0_squared, s0);
92 // v = -(r + s) # 2A
93 fp_add(v, r, s);
94 fp_neg1(&v);
95
96 fp_mul(tmp, v, s0_squared); // # M
97 fp_mul(u, u, s0); // # M
98 // s1 = setup['sqrt'](tmp + u) # A + E
99 fp_add(t, tmp, u);
100 fp_copy(s1, t);
101 fp_sqrt(&s1);
102 // s2 = setup['sqrt'](tmp - u) # A + E
103 fp_sub(s, tmp, u);
104 fp_copy(s2, s);
105 fp_sqrt(&s2);
106
107 // Test to know if s1 and s2 are square roots # 2S
108 fp_sqr(tmp, s1);
109 fp_sqr(aux, s2);
110 uint64_t test_s1 = fp_isequal(tmp, t);
111 uint64_t test_s2 = fp_isequal(aux, s);
112
113 // Compute z # 4Mc + 5A
114 fp_sub(t, s1, s0_squared);
115 fp_mul(t, t, ONE_HALF);
116 fp_neg1(&s1);
117 fp_sub(r, s1, s0_squared);
118 fp_mul(r, r, ONE_HALF);
119
120 fp_add(s, s2, s0_squared);
121 fp_mul(s, s, ONE_HALF);
122 fp_sub(u, s0_squared, s2);
123 fp_mul(u, u, ONE_HALF);
124
125 // Select z in constant time
126 fp_cmov(&output[0], (const fp*)t, test_s1);
127 fp_cmov(&output[1], (const fp*)r, test_s1);
128 fp_cmov(&output[0], (const fp*)s, test_s2);
129 fp_cmov(&output[1], (const fp*)u, test_s2);
130
131 // Compute num and den # 2M + 2A
132 fp_mul(output[2], s0, input_A.z);
133 fp_mul(aux, s0, A_times_one_third);
134 fp_sub(output[0], output[0], aux);
135 fp_sub(output[1], output[1], aux);
136
137 // # 2S + 7M + 2A
138 fp_sqr(r, output[0]); // x**2
139 fp_sqr(s, output[2]); // den**2
140 fp_mul(v, input_A.z, output[0]); // C*x
141 fp_mul(t, output[2], input_A.x); // A*den
142 fp_mul(u, v, s); // C*x*den**2
143 fp_mul(aux, s, output[2]); // den**3
144 fp_mul(aux, aux, input_A.z); // C*den**3
145 fp_add(t, t, v); // C*x + A*den
146 fp_mul(t, t, r); // x**2 * (C*x + A*den)
147 fp_add(t, t, u); // (x**2 * (C*x + A*den)) + C*x * den**2
148 fp_mul(t, t, aux);
149
150 uint64_t test_sqr = (uint64_t)!fp_issquare(t);// # E
151 fp_cswap(output[0], output[1], test_sqr);
152}
fp_sqr
#define fp_sqr
Definition fp-gmp.h:73
fp_sub
#define fp_sub
Definition fp-gmp.h:67
fp_mul
#define fp_mul
Definition fp-gmp.h:70
fp_issquare
#define fp_issquare
Definition fp-gmp.h:76
fp_add
#define fp_add
Definition fp-gmp.h:64
fp_cswap
#define fp_cswap
Definition fp-gmp.h:82
fp_curt
void fp_curt(fp_t output, const fp_t input)
Definition fp.c:189
fp_sqrt
void fp_sqrt(fp_t output, const fp_t input)
Definition fp.c:168
pip._vendor.six.u
u(s)
Definition six.py:646

References fp_add, fp_cmov, fp_copy, fp_cswap, fp_curt(), fp_issquare, fp_mul, fp_sqr, fp_sqrt(), fp_sub, proj::x, and proj::z.

Here is the call graph for this function:

◆ isogeny_walks_to_montgomery_model_3_fp()

void isogeny_walks_to_montgomery_model_3_fp ( fp *  output_A,
const fp *  input_t 
)

Definition at line 154 of file isogeny_walks_3_fp.c.

154 {
155 fp r_squared, s_squared, r_cubed;
156 fp aux, alpha_cubed, alpha, rd;
157
158 // input_t[0] is r
159 // input_t[1] is s
160 // r_squared = r**2
161 fp_sqr(r_squared, input_t[0]);
162 // s_squared = s**2
163 fp_sqr(s_squared, input_t[1]);
164 // r_cubed = r_squared * r
165 fp_mul(r_cubed, r_squared, input_t[0]);
166 // s_cubed = s_squared * s
167 fp_mul(output_A[1], s_squared, input_t[1]);
168 // aux = r * s_squared
169 fp_mul(aux, s_squared, input_t[0]);
170
171 // alpha_cubed = r * (r_squared - s_squared)
172 fp_sub(alpha_cubed, r_squared, s_squared);
173 fp_mul(alpha_cubed, alpha_cubed, input_t[0]);
174 // alpha = setup['curt'](alpha_cubed)
175 fp_curt(alpha, alpha_cubed);
176
177 // Goal rd = 3 * (r * alpha**2 + r_squared * alpha + r_cubed) - s_sqr * alpha - 2 * aux
178 //rd = (r * alpha**2 + r_squared * alpha + r_cubed)
179 fp_mul(rd, input_t[0], alpha);
180 fp_add(rd, rd, r_squared);
181 fp_mul(rd, rd, alpha);
182 fp_add(rd, rd, r_cubed);
183 // rd = 3 * (r * alpha**2 + r_squared * alpha + r_cubed)
184 fp_add(r_squared, rd, rd);
185 fp_add(rd, rd, r_squared);
186 // rd = 3 * (r * alpha**2 + r_squared * alpha + r_cubed) - s_sqr * alpha - 2 * aux
187 fp_sub(rd, rd, aux);
188 fp_sub(rd, rd, aux);
189 fp_mul(r_squared, s_squared, alpha);
190 fp_sub(output_A[0], rd, r_squared);
191}

References fp_add, fp_curt(), fp_mul, fp_sqr, and fp_sub.

Here is the call graph for this function: