Let us walk on the 3-isogeny graph
Loading...
Searching...
No Matches
isogeny_walks_2.c
Go to the documentation of this file.
1//
2// 2-isogeny walk calculations via radical computations
3//
4
5#include <string.h>
6#include "isogeny_walks.h"
7#include "utilities.h"
8// #include <stdio.h>
9
10// 2-isogenies
11void fp2_mul_by_1488(fp2_t *output, fp2_t input) {
12 fp2_t r, s, t;
13
14 fp2_add(&r, input, input); // 2 × input
15 fp2_add(&s, r, input); // 3 × input
16 fp2_add(&t, r, s); // 5 × input
17 fp2_add(&t, t, t); // 10 × input
18
19 fp2_add(&t, t, t); // 20 × input
20 fp2_add(&t, t, s); // 23 × input
21 fp2_add(&t, t, t); // 46 × input
22 fp2_add(&t, t, t); // 92 × input
23
24 fp2_add(&t, t, input); // 93 × input
25 fp2_add(&t, t, t); // 186 × input
26 fp2_add(&t, t, t); // 372 × input
27 fp2_add(&t, t, t); // 744 × input
28
29 fp2_add(output, t, t); // 1488 × input
30}
31
32void fp2_mul_by_2976(fp2_t *output, fp2_t input) {
33 fp2_mul_by_1488(output, input); // 1488 × input
34 fp2_add(output, *output, *output); // 2976 × input
35}
36
37void fp2_mul_by_162000(fp2_t *output, fp2_t input) {
38 fp2_t r, s, t;
39 fp2_add(&r, input, input); // 2 × input
40 fp2_add(&r, r, r); // 4 × input
41 fp2_add(&r, r, r); // 8 × input
42 fp2_add(&r, r, input); // 9 × input
43
44 fp2_add(&s, r, r); // 18 × input
45 fp2_add(&s, s, s); // 36 × input
46 fp2_add(&s, s, s); // 72 × input
47 fp2_add(&t, s, r); // 81 × input
48
49 fp2_add(&s, t, s); // 153 × input
50 fp2_add(&s, s, s); // 306 × input
51 fp2_add(&s, s, s); // 612 × input
52 fp2_add(&s, s, s); // 1224 × input
53
54 fp2_add(&s, s, s); // 2448 × input
55 fp2_add(&t, s, t); // 2529 × input
56 fp2_add(&t, t, t); // 5058 × input
57 fp2_add(&t, t, t); // 10116 × input
58
59 fp2_add(&t, t, r); // 10125 × input
60 fp2_add(&t, t, t); // 20250 × input
61 fp2_add(&t, t, t); // 40500 × input
62 fp2_add(&t, t, t); // 81000 × input
63
64 fp2_add(output, t, t); // 162000 × input
65}
66
67void fp2_mul_by_324000(fp2_t *output, fp2_t input) {
68 fp2_mul_by_162000(output, input); // 162000 × input
69 fp2_add(output, *output, *output); // 324000 × input
70}
71
72void fp2_mul_by_2532192(fp2_t *output, fp2_t input) {
73 fp2_t r, s, t, u, v;
74
75 fp2_add(&r, input, input); // 2 × input
76 fp2_add(&s, r, input); // 3 × input
77 fp2_add(&t, s, s); // 6 × input
78 fp2_add(&t, t, t); // 12 × input
79
80 fp2_add(&t, t, t); // 24 × input
81 fp2_add(&u, t, s); // 27 × input
82 fp2_add(&v, u, t); // 51 × input
83 fp2_add(&t, v, v); // 102 × input
84
85 fp2_add(&t, t, v); // 153 × input
86 fp2_add(&t, t, t); // 306 × input
87 fp2_add(&t, t, s); // 309 × input
88 fp2_add(&t, t, t); // 618 × input
89
90 fp2_add(&t, t, t); // 1236 × input
91 fp2_add(&t, t, t); // 2472 × input
92 fp2_add(&t, t, t); // 4944 × input
93 fp2_add(&t, t, t); // 9888 × input
94
95 fp2_add(&t, t, t); // 19776 × input
96 fp2_add(&t, t, t); // 39552 × input
97 fp2_add(&t, t, t); // 79104 × input
98 fp2_add(&t, t, u); // 79131 × input
99
100 fp2_add(&t, t, t); // 158262 × input
101 fp2_add(&t, t, t); // 316524 × input
102 fp2_add(&t, t, t); // 633048 × input
103 fp2_add(&t, t, t); // 1266096 × input
104
105 fp2_add(output, t, t); // 2532192 × input
106}
107
108void fp2_mul_by_645205500(fp2_t *output, fp2_t input) {
109
110 fp2_t r, s, t, u, v;
111 fp2_add(&r, input, input); // 2 × input
112 fp2_add(&r, r, r); // 4 × input
113 fp2_add(&s, r, input); // 5 × input
114 fp2_add(&t, s, s); // 10 × input
115
116 fp2_add(&t, t, t); // 20 × input
117 fp2_add(&r, t, t); // 40 × input
118 fp2_add(&t, r, r); // 80 × input
119 fp2_add(&u, t, s); // 85 × input
120
121 fp2_add(&v, t, u); // 165 × input
122 fp2_add(&v, v, r); // 205 × input
123 fp2_add(&t, v, v); // 410 × input
124 fp2_add(&t, t, t); // 820 × input
125
126 fp2_add(&t, t, t); // 1640 × input
127 fp2_add(&t, t, t); // 3280 × input
128 fp2_add(&t, t, t); // 6560 × input
129 fp2_add(&t, t, t); // 13120 × input
130
131 fp2_add(&t, t, t); // 26240 × input
132 fp2_add(&t, t, t); // 52480 × input
133 fp2_add(&t, t, t); // 104960 × input
134 fp2_add(&t, t, t); // 209920 × input
135
136 fp2_add(&t, t, t); // 419840 × input
137 fp2_add(&t, t, v); // 420045 × input
138 fp2_add(&t, t, t); // 840090 × input
139 fp2_add(&t, t, t); // 1680180 × input
140
141 fp2_add(&t, t, t); // 3360360 × input
142 fp2_add(&t, t, u); // 3360445 × input
143 fp2_add(&t, t, t); // 6720890 × input
144 fp2_add(&t, t, t); // 13441780 × input
145
146 fp2_add(&t, t, t); // 26883560 × input
147 fp2_add(&t, t, t); // 53767120 × input
148 fp2_add(&t, t, s); // 53767125 × input
149 fp2_add(&u, t, t); // 107534250 × input
150
151 fp2_add(&t, t, u); // 161301375 × input
152 fp2_add(&t, t, t); // 322602750 × input
153 fp2_add(output, t, t); // 645205500 × input
154}
155
156void fp2_mul_by_8748000000(fp2_t *output, fp2_t input) {
157 fp2_t r, s, t, u, v;
158 fp2_add(&r, input, input); // 2 × input
159 fp2_add(&r, r, r); // 4 × input
160 fp2_add(&r, r, r); // 8 × input
161 fp2_add(&r, r, r); // 16 × input
162
163 fp2_add(&r, r, r); // 32 × input
164 fp2_add(&r, r, r); // 64 × input
165 fp2_add(&r, r, r); // 128 × input
166 fp2_add(&s, r, input); // 129 × input
167
168 fp2_add(&r, s, r); // 257 × input
169 fp2_add(&r, r, r); // 514 × input
170 fp2_add(&r, r, r); // 1028 × input
171 fp2_add(&t, r, r); // 2056 × input
172
173 fp2_add(&t, t, t); // 4112 × input
174 fp2_add(&t, t, t); // 8224 × input
175 fp2_add(&u, t, s); // 8353 × input
176 fp2_add(&v, t, r); // 9252 × input
177
178 fp2_add(&t, u, v); // 17605 × input
179 fp2_add(&t, t, t); // 35210 × input
180 fp2_add(&t, t, v); // 44462 × input
181 fp2_add(&t, t, t); // 88924 × input
182
183 fp2_add(&t, t, t); // 177848 × input
184 fp2_add(&t, t, t); // 355696 × input
185 fp2_add(&t, t, t); // 711392 × input
186 fp2_add(&t, t, t); // 1422784 × input
187
188 fp2_add(&t, t, t); // 2845568 × input
189 fp2_add(&t, t, t); // 5691136 × input
190 fp2_add(&t, t, t); // 11382272 × input
191 fp2_add(&t, t, u); // 11390625 × input
192
193 fp2_add(&u, t, t); // 22781250 × input
194 fp2_add(&t, t, u); // 34171875 × input
195 fp2_add(&t, t, t); // 68343750 × input
196 fp2_add(&t, t, t); // 136687500 × input
197
198 fp2_add(&t, t, t); // 273375000 × input
199 fp2_add(&t, t, t); // 546750000 × input
200 fp2_add(&t, t, t); // 1093500000 × input
201 fp2_add(&t, t, t); // 2187000000 × input
202
203 fp2_add(&t, t, t); // 4374000000 × input
204 fp2_add(output, t, t); // 8748000000 × input
205}
206
207
208void isogeny_walks_2(fp2_t *output, fp2_t input_prev, fp2_t input, const uint8_t *input_path, size_t input_length) {
209 size_t i, j;
210 fp2_t t4, t3, t2, t1, t0, jk_next, jk, jk_prev, Dk, Dk_sqrt[2];
211 fp2_t constant_162000, constant_2532192, constant_645205500, constant_8748000000;
212 fp2_t jk_times_2976, jk_prev_times_2976, jk_prev_times_324000, jk_squared, jk_prev_squared;
213
214 fp2_set_to_one(&constant_162000);
215 fp2_set_to_one(&constant_2532192);
216 fp2_set_to_one(&constant_645205500);
217 fp2_set_to_one(&constant_8748000000);
218
219 fp2_mul_by_162000(&constant_162000, constant_162000);
220 fp2_mul_by_2532192(&constant_2532192, constant_2532192);
221 fp2_mul_by_645205500(&constant_645205500, constant_645205500);
222 fp2_mul_by_8748000000(&constant_8748000000, constant_8748000000);
223
224 fp2_copy(&jk, input);
225 fp2_copy(&jk_prev, input_prev);
226
227 for (i = 0; i < input_length; i++) {
228 uint8_t mask = 0x1;
229 for (j = 0; j < 8; j++) {
230 // jk⁴
231 fp2_sqr(&jk_squared, jk);
232 fp2_sqr(&t4, jk_squared);
233 // - 2976 × (jk³) [= - (2976 × jk) × (jk²) ]
234 fp2_mul_by_2976(&jk_times_2976, jk);
235 fp2_mul(&t3, jk_times_2976, jk_squared);
236 // + 2 × (jk²) × jk_prev + 2532192 × (jk²) [= + [2 × jk_prev + 2532192] × (jk²)]
237 fp2_add(&t2, jk_prev, jk_prev);
238 fp2_add(&t2, t2, constant_2532192);
239 fp2_mul(&t2, t2, jk_squared);
240 // - 2976 × jk × jk_prev - 645205500 × jk [= -(2976 × jk_prev + 645205500) × jk ]
241 fp2_mul_by_2976(&jk_prev_times_2976, jk_prev);
242 fp2_add(&t1, jk_prev_times_2976, constant_645205500);
243 fp2_mul(&t1, t1, jk);
244 // - 3 × (jk_prev²) + 324000 × jk_prev [= (-3 × jk_prev + 324000) × jk_prev]
245 fp2_mul_by_324000(&jk_prev_times_324000, jk_prev);
246 fp2_sqr(&jk_prev_squared, jk_prev);
247 fp2_add(&t0, jk_prev_squared, jk_prev_squared);
248 fp2_add(&t0, t0, jk_prev_squared);
249 fp2_sub(&t0, jk_prev_times_324000, t0);
250 // - 8748000000
251
252 // Dk = jk⁴ - 2976 × (jk³) + 2 × (jk²) × jk_prev + 2532192 × (jk²) - 2976 × jk × jk_prev - 645205500 × jk - 3 × (jk_prev²) + 324000 × jk_prev - 8748000000
253 fp2_sub(&Dk, t4, t3);
254 fp2_add(&Dk, Dk, t2);
255 fp2_sub(&Dk, Dk, t1);
256 fp2_add(&Dk, Dk, t0);
257 fp2_sub(&Dk, Dk, constant_8748000000);
258
259 fp2_sqrt_fast(&Dk_sqrt[0], Dk); // 1st square-root (deterministic)
260 fp2_neg(&Dk_sqrt[1], Dk_sqrt[0]); // 2nd square-root (negative)
261 fp2_linear_pass_in(&Dk, Dk_sqrt , 2, (input_path[i] & mask) >> j);
262
263 // jk_next = (jk² - 1488 × jk - jk_prev + 162000 + Dk_sqrt[path[k]]) / 2
264 fp2_half(&t0, jk_times_2976); // 2976 = 2 × 1488
265 fp2_sub(&t1, jk_squared, t0);
266 fp2_sub(&t1, t1, jk_prev);
267 fp2_add(&t1, t1, constant_162000);
268 fp2_add(&t1, t1, Dk);
269 fp2_half(&jk_next, t1);
270
271 fp2_copy(&jk_prev, jk);
272 fp2_copy(&jk, jk_next);
273
274 mask <<= 1;
275 }
276 }
277 fp2_copy(output, jk);
278}
279
280void isogeny_walks_from_montgomery_model_2(fp2_t *output_j, fp2_t input_A) {
281 // Computes the j-invariant of a Montgomery curve E : y² = x³ + Ax² + x
282 fp2_t r, s, t;
283
284 fp2_set_to_one(&t);
285
286 fp2_add(&r, t, t); // 2
287 fp2_add(&r, r, t); // 3
288 fp2_sqr(&s, input_A); // A²
289
290 fp2_sub(&s, s, r); // A² - 3
291 fp2_sub(&r, s, t); // A² - 4
292 fp2_add(&s, s, s); // 2(A² - 3)
293 fp2_add(&s, s, s); // 4(A² - 3)
294
295 fp2_sqr(&t, s); // 16(A² - 3)²
296 fp2_mul(&s, s, t); // 64(A² - 3)³
297 fp2_add(&s, s, s); // 128(A² - 3)³
298 fp2_add(&s, s, s); // 256(A² - 3)³
299 fp2_inv(&t, r); // 1 / (A² - 4)
300 fp2_mul(output_j, s, t);
301}
302
303void isogeny_walks_get_previous_step_2(fp2_t *output_j, fp2_t input_A) {
304 // Computes the j-invariant of a Montgomery curve E : y² = x³ + (A + 6)x² + (4[2 + A])x
305 fp2_t r, s, t;
306
307 fp2_set_to_one(&t);
308
309 fp2_add(&r, t, t); // 2
310 fp2_add(&t, r, r); // 4
311 fp2_add(&r, t, t); // 8
312 fp2_add(&r, t, r); // 12
313
314 fp2_sqr(&s, input_A); // A²
315 fp2_add(&s, s, r); // A² + 12
316 fp2_sub(&r, s, t); // A² - 4
317 fp2_add(&s, s, s); // 2(A² + 12)
318
319 fp2_sqr(&r, r); // (A² - 4)²
320 fp2_sqr(&t, s); // 4(A² + 12)²
321 fp2_mul(&s, s, t); // 8(A² + 12)³
322 fp2_add(&s, s, s); // 16(A² + 12)³
323
324 fp2_inv(&t, r); // 1 / (A² - 4)²
325 fp2_mul(output_j, s, t);
326}
327
328
329void isogeny_walks_sample_bit_string(uint8_t *output) {
330 randombytes(output, BIT_LENGTH_PATH / 8);
331}
332
333void isogeny_walks_2_slow(fp2_t *j0, fp2_t *j1, fp2_t input_prev, fp2_t input, const uint8_t *input_path, size_t input_length) {
334 size_t i, j;
335 fp2_t t4, t3, t2, t1, t0, jk_next, jk, jk_prev, Dk, Dk_sqrt[2];
336 fp2_t constant_162000, constant_2532192, constant_645205500, constant_8748000000;
337 fp2_t jk_times_2976, jk_prev_times_2976, jk_prev_times_324000, jk_squared, jk_prev_squared;
338
339 fp2_set_to_one(&constant_162000);
340 fp2_set_to_one(&constant_2532192);
341 fp2_set_to_one(&constant_645205500);
342 fp2_set_to_one(&constant_8748000000);
343
344 fp2_mul_by_162000(&constant_162000, constant_162000);
345 fp2_mul_by_2532192(&constant_2532192, constant_2532192);
346 fp2_mul_by_645205500(&constant_645205500, constant_645205500);
347 fp2_mul_by_8748000000(&constant_8748000000, constant_8748000000);
348
349 fp2_copy(&jk, input);
350 fp2_copy(&jk_prev, input_prev);
351
352 for (i = 0; i < input_length; i++) {
353 uint8_t mask = 0x1;
354 for (j = 0; j < 8; j++) {
355 // jk⁴
356 fp2_sqr(&jk_squared, jk);
357 fp2_sqr(&t4, jk_squared);
358 // - 2976 × (jk³) [= - (2976 × jk) × (jk²) ]
359 fp2_mul_by_2976(&jk_times_2976, jk);
360 fp2_mul(&t3, jk_times_2976, jk_squared);
361 // + 2 × (jk²) × jk_prev + 2532192 × (jk²) [= + [2 × jk_prev + 2532192] × (jk²)]
362 fp2_add(&t2, jk_prev, jk_prev);
363 fp2_add(&t2, t2, constant_2532192);
364 fp2_mul(&t2, t2, jk_squared);
365 // - 2976 × jk × jk_prev - 645205500 × jk [= -(2976 × jk_prev + 645205500) × jk ]
366 fp2_mul_by_2976(&jk_prev_times_2976, jk_prev);
367 fp2_add(&t1, jk_prev_times_2976, constant_645205500);
368 fp2_mul(&t1, t1, jk);
369 // - 3 × (jk_prev²) + 324000 × jk_prev [= (-3 × jk_prev + 324000) × jk_prev]
370 fp2_mul_by_324000(&jk_prev_times_324000, jk_prev);
371 fp2_sqr(&jk_prev_squared, jk_prev);
372 fp2_add(&t0, jk_prev_squared, jk_prev_squared);
373 fp2_add(&t0, t0, jk_prev_squared);
374 fp2_sub(&t0, jk_prev_times_324000, t0);
375 // - 8748000000
376
377 // Dk = jk⁴ - 2976 × (jk³) + 2 × (jk²) × jk_prev + 2532192 × (jk²) - 2976 × jk × jk_prev - 645205500 × jk - 3 × (jk_prev²) + 324000 × jk_prev - 8748000000
378 fp2_sub(&Dk, t4, t3);
379 fp2_add(&Dk, Dk, t2);
380 fp2_sub(&Dk, Dk, t1);
381 fp2_add(&Dk, Dk, t0);
382 fp2_sub(&Dk, Dk, constant_8748000000);
383
384 fp2_sqrt_slow(&Dk_sqrt[0], Dk); // 1st square-root (deterministic)
385 fp2_neg(&Dk_sqrt[1], Dk_sqrt[0]); // 2nd square-root (negative)
386 fp2_linear_pass_in(&Dk, Dk_sqrt , 2, (input_path[i] & mask) >> j);
387
388 // jk_next = (jk² - 1488 × jk - jk_prev + 162000 + Dk_sqrt[path[k]]) / 2
389 fp2_half(&t0, jk_times_2976); // 2976 = 2 × 1488
390 fp2_sub(&t1, jk_squared, t0);
391 fp2_sub(&t1, t1, jk_prev);
392 fp2_add(&t1, t1, constant_162000);
393 fp2_add(&t1, t1, Dk);
394 fp2_half(&jk_next, t1);
395
396 fp2_copy(&jk_prev, jk);
397 fp2_copy(&jk, jk_next);
398
399 mask <<= 1;
400 }
401 }
402 fp2_copy(j0, jk_prev);
403 fp2_copy(j1, jk);
404}
fp2_sqrt_slow
void fp2_sqrt_slow(fp2_t *output, fp2_t input)
Definition fp2.c:283
fp2_linear_pass_in
void fp2_linear_pass_in(fp2_t *output, const fp2_t *input, uint8_t input_length, uint8_t input_index)
Definition fp2.c:159
fp2_sqrt_fast
void fp2_sqrt_fast(fp2_t *output, fp2_t input)
Definition fp2.c:333
fp2_half
void fp2_half(fp2_t *output, fp2_t input)
Definition fp2.c:107
fp2_set_to_one
void fp2_set_to_one(fp2_t *output)
Definition fp2.c:49
isogeny_walks.h
randombytes
void randombytes(void *x, size_t l)
Definition rng.c:8
fp2_mul_by_2532192
void fp2_mul_by_2532192(fp2_t *output, fp2_t input)
Definition isogeny_walks_2.c:72
isogeny_walks_sample_bit_string
void isogeny_walks_sample_bit_string(uint8_t *output)
Definition isogeny_walks_2.c:329
isogeny_walks_2_slow
void isogeny_walks_2_slow(fp2_t *j0, fp2_t *j1, fp2_t input_prev, fp2_t input, const uint8_t *input_path, size_t input_length)
Definition isogeny_walks_2.c:333
fp2_mul_by_1488
void fp2_mul_by_1488(fp2_t *output, fp2_t input)
Definition isogeny_walks_2.c:11
isogeny_walks_2
void isogeny_walks_2(fp2_t *output, fp2_t input_prev, fp2_t input, const uint8_t *input_path, size_t input_length)
Definition isogeny_walks_2.c:208
isogeny_walks_get_previous_step_2
void isogeny_walks_get_previous_step_2(fp2_t *output_j, fp2_t input_A)
Definition isogeny_walks_2.c:303
isogeny_walks_from_montgomery_model_2
void isogeny_walks_from_montgomery_model_2(fp2_t *output_j, fp2_t input_A)
Definition isogeny_walks_2.c:280
fp2_mul_by_645205500
void fp2_mul_by_645205500(fp2_t *output, fp2_t input)
Definition isogeny_walks_2.c:108
fp2_mul_by_8748000000
void fp2_mul_by_8748000000(fp2_t *output, fp2_t input)
Definition isogeny_walks_2.c:156
fp2_mul_by_324000
void fp2_mul_by_324000(fp2_t *output, fp2_t input)
Definition isogeny_walks_2.c:67
fp2_mul_by_2976
void fp2_mul_by_2976(fp2_t *output, fp2_t input)
Definition isogeny_walks_2.c:32
fp2_mul_by_162000
void fp2_mul_by_162000(fp2_t *output, fp2_t input)
Definition isogeny_walks_2.c:37
BIT_LENGTH_PATH
#define BIT_LENGTH_PATH
Definition p254.h:14
i
for i
Definition prime_search.m:10
j
for j
Definition prime_search.m:12
fp2_t
Definition fp2.h:10