Line data Source code
1 : /* Copyright (C) 2012 The PARI group.
2 :
3 : This file is part of the PARI/GP package.
4 :
5 : PARI/GP is free software; you can redistribute it and/or modify it under the
6 : terms of the GNU General Public License as published by the Free Software
7 : Foundation; either version 2 of the License, or (at your option) any later
8 : version. It is distributed in the hope that it will be useful, but WITHOUT
9 : ANY WARRANTY WHATSOEVER.
10 :
11 : Check the License for details. You should have received a copy of it, along
12 : with the package; see the file 'COPYING'. If not, write to the Free Software
13 : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
14 :
15 : #include "pari.h"
16 : #include "paripriv.h"
17 :
18 : #define DEBUGLEVEL DEBUGLEVEL_ellcard
19 :
20 : /* Not so fast arithmetic with points over elliptic curves over F_2^n */
21 :
22 : /***********************************************************************/
23 : /** **/
24 : /** F2xqE **/
25 : /** **/
26 : /***********************************************************************/
27 : /* These functions deal with points over elliptic curves over F_2^n defined
28 : * by an equation of the form:
29 : * y^2+x*y = x^3+a_2*x^2+a_6 if the curve is ordinary.
30 : * y^2+a_3*y = x^3+a_4*x+a_6 if the curve is supersingular.
31 : * Most of the time a6 is omitted since it can be recovered from any point
32 : * on the curve.
33 : * For supersingular curves, the parameter a2 is replaced by [a3,a4,a3^-1]. */
34 :
35 : GEN
36 194544 : RgE_to_F2xqE(GEN x, GEN T)
37 : {
38 194544 : if (ell_is_inf(x)) return x;
39 194061 : retmkvec2(Rg_to_F2xq(gel(x,1),T),Rg_to_F2xq(gel(x,2),T));
40 : }
41 :
42 : GEN
43 355838 : F2xqE_changepoint(GEN x, GEN ch, GEN T)
44 : {
45 355838 : pari_sp av = avma;
46 : GEN p1,z,u,r,s,t,v,v2,v3;
47 355838 : if (ell_is_inf(x)) return x;
48 187215 : u = gel(ch,1); r = gel(ch,2);
49 187215 : s = gel(ch,3); t = gel(ch,4);
50 187215 : v = F2xq_inv(u, T); v2 = F2xq_sqr(v, T); v3 = F2xq_mul(v,v2, T);
51 187215 : p1 = F2x_add(gel(x,1),r);
52 187215 : z = cgetg(3,t_VEC);
53 187215 : gel(z,1) = F2xq_mul(v2, p1, T);
54 187215 : gel(z,2) = F2xq_mul(v3, F2x_add(gel(x,2), F2x_add(F2xq_mul(s, p1, T),t)), T);
55 187215 : return gerepileupto(av, z);
56 : }
57 :
58 : GEN
59 194544 : F2xqE_changepointinv(GEN x, GEN ch, GEN T)
60 : {
61 : GEN u, r, s, t, X, Y, u2, u3, u2X, z;
62 194544 : if (ell_is_inf(x)) return x;
63 194061 : X = gel(x,1); Y = gel(x,2);
64 194061 : u = gel(ch,1); r = gel(ch,2);
65 194061 : s = gel(ch,3); t = gel(ch,4);
66 194061 : u2 = F2xq_sqr(u, T); u3 = F2xq_mul(u,u2, T);
67 194061 : u2X = F2xq_mul(u2,X, T);
68 194061 : z = cgetg(3, t_VEC);
69 194061 : gel(z,1) = F2x_add(u2X,r);
70 194061 : gel(z,2) = F2x_add(F2xq_mul(u3,Y, T), F2x_add(F2xq_mul(s,u2X, T), t));
71 194061 : return z;
72 : }
73 :
74 : static GEN
75 3514 : nonzerotrace_F2xq(GEN T)
76 : {
77 3514 : pari_sp av = avma;
78 3514 : long n = F2x_degree(T), vs = T[1];
79 : GEN a;
80 3514 : if (odd(n))
81 1162 : return pol1_F2x(vs);
82 : do
83 : {
84 4515 : set_avma(av);
85 4515 : a = random_F2x(n, vs);
86 4515 : } while (F2xq_trace(a, T)==0);
87 2352 : return a;
88 : }
89 :
90 : void
91 3514 : F2xq_elltwist(GEN a, GEN a6, GEN T, GEN *pt_a, GEN *pt_a6)
92 : {
93 3514 : pari_sp av = avma;
94 3514 : GEN n = nonzerotrace_F2xq(T);
95 3514 : if (typ(a)==t_VECSMALL)
96 : {
97 3514 : *pt_a = gerepileuptoleaf(av, F2x_add(n, a));
98 3514 : *pt_a6 = vecsmall_copy(a6);
99 : } else
100 : {
101 0 : GEN a6t = F2x_add(a6, F2xq_mul(n, F2xq_sqr(gel(a,1), T), T));
102 0 : *pt_a6 = gerepileuptoleaf(av, a6t);
103 0 : *pt_a = vecsmall_copy(a);
104 : }
105 3514 : }
106 :
107 : static GEN
108 1060409 : F2xqE_dbl_slope(GEN P, GEN a, GEN T, GEN *slope)
109 : {
110 : GEN x, y, Q;
111 1060409 : if (ell_is_inf(P)) return ellinf();
112 1046864 : x = gel(P,1); y = gel(P,2);
113 1046864 : if (typ(a)==t_VECSMALL)
114 : {
115 193935 : GEN a2 = a;
116 193935 : if (!lgpol(gel(P,1))) { *slope = NULL; return ellinf(); }
117 177310 : *slope = F2x_add(x, F2xq_div(y, x, T));
118 177310 : Q = cgetg(3,t_VEC);
119 177310 : gel(Q, 1) = F2x_add(F2xq_sqr(*slope, T), F2x_add(*slope, a2));
120 177310 : gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, gel(Q, 1)));
121 : }
122 : else
123 : {
124 852929 : GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
125 852929 : *slope = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
126 852929 : Q = cgetg(3,t_VEC);
127 852929 : gel(Q, 1) = F2xq_sqr(*slope, T);
128 852929 : gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, a3));
129 : }
130 1030239 : return Q;
131 : }
132 :
133 : GEN
134 1041992 : F2xqE_dbl(GEN P, GEN a, GEN T)
135 : {
136 1041992 : pari_sp av = avma;
137 : GEN slope;
138 1041992 : return gerepileupto(av, F2xqE_dbl_slope(P, a, T,&slope));
139 : }
140 :
141 : static GEN
142 352597 : F2xqE_add_slope(GEN P, GEN Q, GEN a, GEN T, GEN *slope)
143 : {
144 : GEN Px, Py, Qx, Qy, R;
145 352597 : if (ell_is_inf(P)) { *slope = NULL; return Q; }
146 351015 : if (ell_is_inf(Q)) { *slope = NULL; return P; }
147 351008 : Px = gel(P,1); Py = gel(P,2);
148 351008 : Qx = gel(Q,1); Qy = gel(Q,2);
149 351008 : if (F2x_equal(Px, Qx))
150 : {
151 157437 : if (F2x_equal(Py, Qy))
152 1582 : return F2xqE_dbl_slope(P, a, T, slope);
153 : else
154 155855 : { *slope = NULL; return ellinf(); }
155 : }
156 193571 : *slope = F2xq_div(F2x_add(Py, Qy), F2x_add(Px, Qx), T);
157 193571 : R = cgetg(3,t_VEC);
158 193571 : if (typ(a)==t_VECSMALL)
159 : {
160 63224 : GEN a2 = a;
161 63224 : gel(R, 1) = F2x_add(F2x_add(F2x_add(F2x_add(F2xq_sqr(*slope, T), *slope), Px), Qx), a2);
162 63224 : gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, gel(R, 1)));
163 : }
164 : else
165 : {
166 130347 : GEN a3 = gel(a,1);
167 130347 : gel(R, 1) = F2x_add(F2x_add(F2xq_sqr(*slope, T), Px), Qx);
168 130347 : gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, a3));
169 : }
170 193571 : return R;
171 : }
172 :
173 : GEN
174 352562 : F2xqE_add(GEN P, GEN Q, GEN a, GEN T)
175 : {
176 352562 : pari_sp av = avma;
177 : GEN slope;
178 352562 : return gerepileupto(av, F2xqE_add_slope(P, Q, a, T, &slope));
179 : }
180 :
181 : static GEN
182 0 : F2xqE_neg_i(GEN P, GEN a)
183 : {
184 : GEN LHS;
185 0 : if (ell_is_inf(P)) return P;
186 0 : LHS = typ(a)==t_VECSMALL ? gel(P,1): gel(a,1);
187 0 : return mkvec2(gel(P,1), F2x_add(LHS, gel(P,2)));
188 : }
189 :
190 : GEN
191 84 : F2xqE_neg(GEN P, GEN a, GEN T)
192 : {
193 : GEN LHS;
194 : (void) T;
195 84 : if (ell_is_inf(P)) return ellinf();
196 84 : LHS = typ(a)==t_VECSMALL ? gel(P,1): gel(a,1);
197 84 : return mkvec2(gcopy(gel(P,1)), F2x_add(LHS, gel(P,2)));
198 : }
199 :
200 : GEN
201 0 : F2xqE_sub(GEN P, GEN Q, GEN a2, GEN T)
202 : {
203 0 : pari_sp av = avma;
204 : GEN slope;
205 0 : return gerepileupto(av, F2xqE_add_slope(P, F2xqE_neg_i(Q, a2), a2, T, &slope));
206 : }
207 :
208 : struct _F2xqE
209 : {
210 : GEN a2, a6;
211 : GEN T;
212 : };
213 :
214 : static GEN
215 1041992 : _F2xqE_dbl(void *E, GEN P)
216 : {
217 1041992 : struct _F2xqE *ell = (struct _F2xqE *) E;
218 1041992 : return F2xqE_dbl(P, ell->a2, ell->T);
219 : }
220 :
221 : static GEN
222 352562 : _F2xqE_add(void *E, GEN P, GEN Q)
223 : {
224 352562 : struct _F2xqE *ell=(struct _F2xqE *) E;
225 352562 : return F2xqE_add(P, Q, ell->a2, ell->T);
226 : }
227 :
228 : static GEN
229 214368 : _F2xqE_mul(void *E, GEN P, GEN n)
230 : {
231 214368 : pari_sp av = avma;
232 214368 : struct _F2xqE *e=(struct _F2xqE *) E;
233 214368 : long s = signe(n);
234 214368 : if (!s || ell_is_inf(P)) return ellinf();
235 210091 : if (s<0) P = F2xqE_neg(P, e->a2, e->T);
236 210091 : if (is_pm1(n)) return s>0? gcopy(P): P;
237 204519 : return gerepilecopy(av, gen_pow_i(P, n, e, &_F2xqE_dbl, &_F2xqE_add));
238 : }
239 :
240 : GEN
241 184184 : F2xqE_mul(GEN P, GEN n, GEN a2, GEN T)
242 : {
243 : struct _F2xqE E;
244 184184 : E.a2 = a2; E.T = T;
245 184184 : return _F2xqE_mul(&E, P, n);
246 : }
247 :
248 : /* Finds a random nonsingular point on E */
249 : GEN
250 181601 : random_F2xqE(GEN a, GEN a6, GEN T)
251 : {
252 181601 : pari_sp ltop = avma;
253 : GEN x, y, rhs, u;
254 : do
255 : {
256 376334 : set_avma(ltop);
257 376334 : x = random_F2x(F2x_degree(T),T[1]);
258 376334 : if (typ(a) == t_VECSMALL)
259 : {
260 63000 : GEN a2 = a, x2;
261 63000 : if (!lgpol(x))
262 735 : { set_avma(ltop); retmkvec2(pol0_Flx(T[1]), F2xq_sqrt(a6,T)); }
263 62265 : u = x; x2 = F2xq_sqr(x, T);
264 62265 : rhs = F2x_add(F2xq_mul(x2,F2x_add(x,a2),T),a6);
265 62265 : rhs = F2xq_div(rhs,x2,T);
266 : }
267 : else
268 : {
269 313334 : GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3), u2i;
270 313334 : u = a3; u2i = F2xq_sqr(a3i,T);
271 313334 : rhs = F2x_add(F2xq_mul(x,F2x_add(F2xq_sqr(x,T),a4),T),a6);
272 313334 : rhs = F2xq_mul(rhs,u2i,T);
273 : }
274 375599 : } while (F2xq_trace(rhs,T));
275 180866 : y = F2xq_mul(F2xq_Artin_Schreier(rhs, T), u, T);
276 180866 : return gerepilecopy(ltop, mkvec2(x, y));
277 : }
278 :
279 : static GEN
280 13769 : _F2xqE_rand(void *E)
281 : {
282 13769 : struct _F2xqE *ell=(struct _F2xqE *) E;
283 13769 : return random_F2xqE(ell->a2, ell->a6, ell->T);
284 : }
285 :
286 : static const struct bb_group F2xqE_group={_F2xqE_add,_F2xqE_mul,_F2xqE_rand,hash_GEN,zvV_equal,ell_is_inf, NULL};
287 :
288 : const struct bb_group *
289 0 : get_F2xqE_group(void ** pt_E, GEN a2, GEN a6, GEN T)
290 : {
291 0 : struct _F2xqE *e = (struct _F2xqE *) stack_malloc(sizeof(struct _F2xqE));
292 0 : e->a2 = a2; e->a6 = a6; e->T = T;
293 0 : *pt_E = (void *) e;
294 0 : return &F2xqE_group;
295 : }
296 :
297 : GEN
298 280 : F2xqE_order(GEN z, GEN o, GEN a2, GEN T)
299 : {
300 280 : pari_sp av = avma;
301 : struct _F2xqE e;
302 280 : e.a2=a2; e.T=T;
303 280 : return gerepileuptoint(av, gen_order(z, o, (void*)&e, &F2xqE_group));
304 : }
305 :
306 : GEN
307 42 : F2xqE_log(GEN a, GEN b, GEN o, GEN a2, GEN T)
308 : {
309 42 : pari_sp av = avma;
310 : struct _F2xqE e;
311 42 : e.a2=a2; e.T=T;
312 42 : return gerepileuptoint(av, gen_PH_log(a, b, o, (void*)&e, &F2xqE_group));
313 : }
314 :
315 : /***********************************************************************/
316 : /** **/
317 : /** Pairings **/
318 : /** **/
319 : /***********************************************************************/
320 :
321 : /* Derived from APIP from and by Jerome Milan, 2012 */
322 :
323 : static long
324 19187 : is_2_torsion(GEN Q, GEN a)
325 : {
326 19187 : return (typ(a)==t_VEC || lgpol(gel(Q, 1))) ? 0: 1;
327 : }
328 :
329 : static GEN
330 34916 : F2xqE_vert(GEN P, GEN Q, GEN a, GEN T)
331 : {
332 34916 : long vT = T[1];
333 34916 : if (ell_is_inf(P))
334 9023 : return pol1_F2x(T[1]);
335 25893 : if (!F2x_equal(gel(Q, 1), gel(P, 1)))
336 24255 : return F2x_add(gel(Q, 1), gel(P, 1));
337 1638 : if (is_2_torsion(Q, a))
338 0 : return F2xq_inv(gel(Q,2), T);
339 1638 : return pol1_F2x(vT);
340 : }
341 :
342 : static GEN
343 16870 : F2xqE_Miller_line(GEN R, GEN Q, GEN slope, GEN a, GEN T)
344 : {
345 16870 : long vT = T[1];
346 16870 : GEN x = gel(Q, 1), y = gel(Q, 2);
347 16870 : GEN tmp1 = F2x_add(x, gel(R, 1));
348 16870 : GEN tmp2 = F2x_add(F2xq_mul(tmp1, slope, T), gel(R, 2));
349 : GEN s1, s2, ix;
350 16870 : if (!F2x_equal(y, tmp2))
351 16156 : return F2x_add(y, tmp2);
352 714 : if (is_2_torsion(Q, a)) return pol1_F2x(vT);
353 714 : if (typ(a)==t_VEC)
354 : {
355 700 : GEN a4 = gel(a,2), a3i = gel(a,3);
356 700 : s1 = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
357 700 : if (!F2x_equal(s1, slope))
358 350 : return F2x_add(s1, slope);
359 350 : s2 = F2xq_mul(F2x_add(x, F2xq_sqr(s1, T)), a3i, T);
360 350 : if (lgpol(s2)) return s2;
361 0 : return zv_copy(a3i);
362 : } else
363 : {
364 14 : GEN a2 = a ;
365 14 : ix = F2xq_inv(x, T);
366 14 : s1 = F2x_add(x, F2xq_mul(y, ix, T));
367 14 : if (!F2x_equal(s1, slope))
368 7 : return F2x_add(s1, slope);
369 7 : s2 =F2x_add(a2, F2x_add(F2xq_sqr(s1,T), s1));
370 7 : if (!F2x_equal(s2, x))
371 7 : return F2x_add(pol1_F2x(vT), F2xq_mul(s2, ix, T));
372 0 : return ix;
373 : }
374 : }
375 :
376 : /* Computes the equation of the line tangent to R and returns its
377 : evaluation at the point Q. Also doubles the point R.
378 : */
379 :
380 : static GEN
381 16835 : F2xqE_tangent_update(GEN R, GEN Q, GEN a2, GEN T, GEN *pt_R)
382 : {
383 16835 : if (ell_is_inf(R))
384 : {
385 0 : *pt_R = ellinf();
386 0 : return pol1_F2x(T[1]);
387 : }
388 16835 : else if (is_2_torsion(R, a2))
389 : {
390 0 : *pt_R = ellinf();
391 0 : return F2xqE_vert(R, Q, a2, T);
392 : } else {
393 : GEN slope;
394 16835 : *pt_R = F2xqE_dbl_slope(R, a2, T, &slope);
395 16835 : return F2xqE_Miller_line(R, Q, slope, a2, T);
396 : }
397 : }
398 :
399 : /* Computes the equation of the line through R and P, and returns its
400 : evaluation at the point Q. Also adds P to the point R.
401 : */
402 :
403 : static GEN
404 9058 : F2xqE_chord_update(GEN R, GEN P, GEN Q, GEN a2, GEN T, GEN *pt_R)
405 : {
406 9058 : if (ell_is_inf(R))
407 : {
408 0 : *pt_R = gcopy(P);
409 0 : return F2xqE_vert(P, Q, a2, T);
410 : }
411 9058 : else if (ell_is_inf(P))
412 : {
413 0 : *pt_R = gcopy(R);
414 0 : return F2xqE_vert(R, Q, a2, T);
415 : }
416 9058 : else if (F2x_equal(gel(P, 1), gel(R, 1)))
417 : {
418 9023 : if (F2x_equal(gel(P, 2), gel(R, 2)))
419 0 : return F2xqE_tangent_update(R, Q, a2, T, pt_R);
420 : else
421 : {
422 9023 : *pt_R = ellinf();
423 9023 : return F2xqE_vert(R, Q, a2, T);
424 : }
425 : } else {
426 : GEN slope;
427 35 : *pt_R = F2xqE_add_slope(P, R, a2, T, &slope);
428 35 : return F2xqE_Miller_line(R, Q, slope, a2, T);
429 : }
430 : }
431 :
432 : struct _F2xqE_miller { GEN T, a2, P; };
433 :
434 : static GEN
435 16835 : F2xqE_Miller_dbl(void* E, GEN d)
436 : {
437 16835 : struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
438 16835 : GEN T = m->T, a2 = m->a2, P = m->P;
439 16835 : GEN v, line, point = gel(d,3);
440 16835 : GEN N = F2xq_sqr(gel(d,1), T);
441 16835 : GEN D = F2xq_sqr(gel(d,2), T);
442 16835 : line = F2xqE_tangent_update(point, P, a2, T, &point);
443 16835 : N = F2xq_mul(N, line, T);
444 16835 : v = F2xqE_vert(point, P, a2, T);
445 16835 : D = F2xq_mul(D, v, T); return mkvec3(N, D, point);
446 : }
447 : static GEN
448 9058 : F2xqE_Miller_add(void* E, GEN va, GEN vb)
449 : {
450 9058 : struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
451 9058 : GEN T = m->T, a2 = m->a2, P = m->P;
452 : GEN v, line, point;
453 9058 : GEN na = gel(va,1), da = gel(va,2), pa = gel(va,3);
454 9058 : GEN nb = gel(vb,1), db = gel(vb,2), pb = gel(vb,3);
455 9058 : GEN N = F2xq_mul(na, nb, T);
456 9058 : GEN D = F2xq_mul(da, db, T);
457 9058 : line = F2xqE_chord_update(pa, pb, P, a2, T, &point);
458 9058 : N = F2xq_mul(N, line, T);
459 9058 : v = F2xqE_vert(point, P, a2, T);
460 9058 : D = F2xq_mul(D, v, T); return mkvec3(N, D, point);
461 : }
462 : /* Returns the Miller function f_{m, Q} evaluated at the point P using
463 : * the standard Miller algorithm. */
464 : static GEN
465 9058 : F2xqE_Miller(GEN Q, GEN P, GEN m, GEN a2, GEN T)
466 : {
467 9058 : pari_sp av = avma;
468 : struct _F2xqE_miller d;
469 : GEN v, N, D, g1;
470 :
471 9058 : d.a2 = a2; d.T = T; d.P = P;
472 9058 : g1 = pol1_F2x(T[1]);
473 9058 : v = gen_pow_i(mkvec3(g1,g1,Q), m, (void*)&d, F2xqE_Miller_dbl, F2xqE_Miller_add);
474 9058 : N = gel(v,1); D = gel(v,2);
475 9058 : return gerepileupto(av, F2xq_div(N, D, T));
476 : }
477 :
478 : GEN
479 5341 : F2xqE_weilpairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
480 : {
481 5341 : pari_sp av = avma;
482 : GEN N, D;
483 5341 : if (ell_is_inf(P) || ell_is_inf(Q)
484 4802 : || (F2x_equal(gel(P,1),gel(Q,1)) && F2x_equal(gel(P,2),gel(Q,2))))
485 826 : return pol1_F2x(T[1]);
486 4515 : N = F2xqE_Miller(P, Q, m, a2, T);
487 4515 : D = F2xqE_Miller(Q, P, m, a2, T);
488 4515 : return gerepileupto(av, F2xq_div(N, D, T));
489 : }
490 :
491 : GEN
492 28 : F2xqE_tatepairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
493 : {
494 28 : if (ell_is_inf(P) || ell_is_inf(Q))
495 0 : return pol1_F2x(T[1]);
496 28 : return F2xqE_Miller(P, Q, m, a2, T);
497 : }
498 :
499 : /***********************************************************************/
500 : /** **/
501 : /** Point counting **/
502 : /** **/
503 : /***********************************************************************/
504 :
505 : static GEN
506 68635 : Z2x_rshift(GEN y, long x)
507 : {
508 : GEN z;
509 : long i, l;
510 68635 : if (!x) return pol0_Flx(y[1]);
511 68635 : z = cgetg_copy(y, &l); z[1] = y[1];
512 7641129 : for(i=2; i<l; i++) z[i] = y[i]>>x;
513 68635 : return Flx_renormalize(z, l);
514 : }
515 :
516 : /* Solve the linear equation approximation in the Newton algorithm */
517 :
518 : static GEN
519 170280 : gen_Z2x_Dixon(GEN F, GEN V, long N, void *E, GEN lin(void *E, GEN F, GEN d, long N), GEN invl(void *E, GEN d))
520 : {
521 170280 : pari_sp av = avma;
522 : long N2, M;
523 : GEN VN2, V2, VM, bil;
524 170280 : ulong q = 1UL<<N;
525 170280 : if (N == 1) return invl(E, V);
526 68595 : V = Flx_red(V, q);
527 68639 : N2 = (N + 1)>>1; M = N - N2;
528 68639 : F = FlxT_red(F, q);
529 68632 : VN2 = gen_Z2x_Dixon(F, V, N2, E, lin, invl);
530 68648 : bil = lin(E, F, VN2, N);
531 68642 : V2 = Z2x_rshift(Flx_sub(V, bil, q), N2);
532 68647 : VM = gen_Z2x_Dixon(F, V2, M, E, lin, invl);
533 68649 : return gerepileupto(av, Flx_add(VN2, Flx_Fl_mul(VM, 1UL<<N2, q), q));
534 : }
535 :
536 : /* Solve F(X) = V mod 2^N
537 : F(Xn) = V [mod 2^n]
538 : Vm = (V-F(Xn))/(2^n)
539 : F(Xm) = Vm
540 : X = Xn + 2^n*Xm
541 : */
542 :
543 : static GEN
544 33078 : gen_Z2X_Dixon(GEN F, GEN V, long N, void *E,
545 : GEN lin(void *E, GEN F, GEN d, long N),
546 : GEN lins(void *E, GEN F, GEN d, long N),
547 : GEN invls(void *E, GEN d))
548 : {
549 33078 : pari_sp av = avma;
550 : long n, m;
551 : GEN Xn, Xm, FXn, Vm;
552 33078 : if (N<BITS_IN_LONG)
553 : {
554 33058 : ulong q = 1UL<<N;
555 33058 : return Flx_to_ZX(gen_Z2x_Dixon(ZXT_to_FlxT(F,q), ZX_to_Flx(V,q),N,E,lins,invls));
556 : }
557 20 : V = ZX_remi2n(V, N);
558 20 : n = (N + 1)>>1; m = N - n;
559 20 : F = ZXT_remi2n(F, N);
560 20 : Xn = gen_Z2X_Dixon(F, V, n, E, lin, lins, invls);
561 20 : FXn = lin(E, F, Xn, N);
562 20 : Vm = ZX_shifti(ZX_sub(V, FXn), -n);
563 20 : Xm = gen_Z2X_Dixon(F, Vm, m, E, lin, lins, invls);
564 20 : return gerepileupto(av, ZX_remi2n(ZX_add(Xn, ZX_shifti(Xm, n)), N));
565 : }
566 :
567 : /* H -> H mod 2*/
568 :
569 50584 : static GEN _can_invls(void *E, GEN V) {(void) E; return V; }
570 :
571 : /* H -> H-(f0*H0-f1*H1) */
572 :
573 10 : static GEN _can_lin(void *E, GEN F, GEN V, long N)
574 : {
575 10 : pari_sp av=avma;
576 : GEN d0, d1, z;
577 : (void) E;
578 10 : RgX_even_odd(V, &d0, &d1);
579 10 : z = ZX_sub(V, ZX_sub(ZX_mul(gel(F,1), d0), ZX_mul(gel(F,2), d1)));
580 10 : return gerepileupto(av, ZX_remi2n(z, N));
581 : }
582 :
583 34187 : static GEN _can_lins(void *E, GEN F, GEN V, long N)
584 : {
585 34187 : GEN D=Flx_splitting(V, 2), z;
586 34183 : ulong q = 1UL<<N;
587 : (void) E;
588 34183 : z = Flx_sub(Flx_mul(gel(F,1), gel(D,1), q), Flx_mul(gel(F,2), gel(D,2), q), q);
589 34177 : return Flx_sub(V, z, q);
590 : }
591 :
592 : /* P -> P-(P0^2-X*P1^2) */
593 :
594 : static GEN
595 16395 : _can_iter(void *E, GEN f2, GEN q)
596 : {
597 : GEN f0, f1, z;
598 : (void) E;
599 16395 : RgX_even_odd(f2, &f0, &f1);
600 16397 : z = ZX_add(ZX_sub(f2, FpX_sqr(f0, q)), RgX_shift_shallow(FpX_sqr(f1, q), 1));
601 16397 : return mkvec3(z,f0,f1);
602 : }
603 :
604 : /* H -> H-(2*P0*H0-2*X*P1*H1) */
605 :
606 : static GEN
607 16394 : _can_invd(void *E, GEN V, GEN v, GEN q, long M)
608 : {
609 : GEN F;
610 : (void)E; (void)q;
611 16394 : F = mkvec2(ZX_shifti(gel(v,2),1), ZX_shifti(RgX_shift_shallow(gel(v,3),1),1));
612 16396 : return gen_Z2X_Dixon(F, V, M, NULL, _can_lin, _can_lins, _can_invls);
613 : }
614 :
615 : /* Lift P to Q such that Q(x^2)=Q(x)*Q(-x) mod 2^n
616 : if Q = Q0(X^2)+X*Q1(X^2), solve Q(X^2) = Q0^2-X*Q1^2
617 : */
618 : GEN
619 7186 : F2x_Teichmuller(GEN P, long n)
620 7186 : { return gen_ZpX_Newton(F2x_to_ZX(P),gen_2, n, NULL, _can_iter, _can_invd); }
621 :
622 : static GEN
623 16652 : Z2XQ_frob(GEN x, GEN T, GEN q)
624 : {
625 16652 : return FpX_rem(RgX_inflate(x, 2), T, q);
626 : }
627 :
628 : static GEN
629 34461 : Z2xq_frob(GEN x, GEN T, ulong q)
630 : {
631 34461 : return Flx_rem(Flx_inflate(x, 2), T, q);
632 : }
633 :
634 : struct _frob_lift
635 : {
636 : GEN T, sqx;
637 : };
638 :
639 : /* H -> S^-1(H) mod 2 */
640 :
641 51110 : static GEN _frob_invls(void *E, GEN V)
642 : {
643 51110 : struct _frob_lift *F = (struct _frob_lift*) E;
644 51110 : GEN sqx = F->sqx;
645 51110 : return F2x_to_Flx(F2xq_sqrt_fast(Flx_to_F2x(V), gel(sqx,1), gel(sqx,2)));
646 : }
647 :
648 : /* H -> f1*S(H) + f2*H */
649 :
650 10 : static GEN _frob_lin(void *E, GEN F, GEN x2, long N)
651 : {
652 10 : GEN T = gel(F,3);
653 10 : GEN q = int2n(N);
654 10 : GEN y2 = Z2XQ_frob(x2, T, q);
655 10 : GEN lin = ZX_add(ZX_mul(gel(F,1), y2), ZX_mul(gel(F,2), x2));
656 : (void) E;
657 10 : return FpX_rem(ZX_remi2n(lin, N), T, q);
658 : }
659 :
660 34462 : static GEN _frob_lins(void *E, GEN F, GEN x2, long N)
661 : {
662 34462 : GEN T = gel(F,3);
663 34462 : ulong q = 1UL<<N;
664 34462 : GEN y2 = Z2xq_frob(x2, T, q);
665 34461 : GEN lin = Flx_add(Flx_mul(gel(F,1), y2,q), Flx_mul(gel(F,2), x2,q),q);
666 : (void) E;
667 34460 : return Flx_rem(lin, T, q);
668 : }
669 :
670 : /* X -> P(X,S(X)) */
671 :
672 : static GEN
673 16642 : _lift_iter(void *E, GEN x2, GEN q)
674 : {
675 16642 : struct _frob_lift *F = (struct _frob_lift*) E;
676 16642 : long N = expi(q);
677 16642 : GEN TN = ZXT_remi2n(F->T, N);
678 16642 : GEN y2 = Z2XQ_frob(x2, TN, q);
679 16642 : GEN x2y2 = FpX_rem(ZX_remi2n(ZX_mul(x2, y2), N), TN, q);
680 16642 : GEN s = ZX_add(ZX_add(x2, ZX_shifti(y2, 1)), ZX_shifti(x2y2, 3));
681 16642 : GEN V = ZX_add(ZX_add(ZX_sqr(s), y2), ZX_shifti(x2y2, 2));
682 16641 : return mkvec4(FpX_rem(ZX_remi2n(V, N), TN, q),x2,y2,s);
683 : }
684 :
685 : /* H -> Dx*H+Dy*S(H) */
686 : static GEN
687 16642 : _lift_invd(void *E, GEN V, GEN v, GEN qM, long M)
688 : {
689 16642 : struct _frob_lift *F = (struct _frob_lift*) E;
690 16642 : GEN TM = ZXT_remi2n(F->T, M);
691 16642 : GEN x2 = gel(v,2), y2 = gel(v,3), s = gel(v,4), r;
692 16642 : GEN Dx = ZX_add(ZX_mul(ZX_Z_add(ZX_shifti(y2, 4), gen_2), s),
693 : ZX_shifti(y2, 2));
694 16642 : GEN Dy = ZX_add(ZX_Z_add(ZX_mul(ZX_Z_add(ZX_shifti(x2, 4), utoi(4)), s),
695 : gen_1), ZX_shifti(x2, 2));
696 16642 : Dx = FpX_rem(ZX_remi2n(Dx, M), TM, qM);
697 16640 : Dy = FpX_rem(ZX_remi2n(Dy, M), TM, qM);
698 16641 : r = mkvec3(Dy, Dx, TM);
699 16642 : return gen_Z2X_Dixon(r, V, M, E, _frob_lin, _frob_lins, _frob_invls);
700 : }
701 :
702 : /* Let P(X,Y)=(X+2*Y+8*X*Y)^2+Y+4*X*Y
703 : * Solve P(x,S(x))=0 [mod 2^n,T]
704 : * assuming x = x0 [mod 2,T]
705 : *
706 : * we set s = X+2*Y+8*X*Y, P = s^2+Y+4*X*Y
707 : * Dx = dP/dx = (16*s+4)*x+(4*s+1)
708 : * Dy = dP/dy = (16*y+2)*s+4*y */
709 : static GEN
710 7417 : solve_AGM_eqn(GEN x0, long n, GEN T, GEN sqx)
711 : {
712 : struct _frob_lift F;
713 7417 : F.T=T; F.sqx=sqx;
714 7417 : return gen_ZpX_Newton(x0, gen_2, n, &F, _lift_iter, _lift_invd);
715 : }
716 :
717 : static GEN
718 238 : Z2XQ_invnorm_pcyc(GEN a, GEN T, long e)
719 : {
720 238 : GEN q = int2n(e);
721 238 : GEN z = ZpXQ_norm_pcyc(a, T, q, gen_2);
722 238 : return Zp_inv(z, gen_2, e);
723 : }
724 :
725 : /* Assume a = 1 [4] */
726 : static GEN
727 7179 : Z2XQ_invnorm(GEN a, GEN T, long e)
728 : {
729 : pari_timer ti;
730 7179 : GEN pe = int2n(e), s;
731 7179 : if (degpol(a)==0)
732 56 : return Zp_inv(Fp_powu(gel(a,2), get_FpX_degree(T), pe), gen_2, e);
733 7123 : if (DEBUGLEVEL>=3) timer_start(&ti);
734 7123 : s = ZpXQ_log(a, T, gen_2, e);
735 7123 : if (DEBUGLEVEL>=3) timer_printf(&ti,"Z2XQ_log");
736 7123 : s = Fp_neg(FpXQ_trace(s, T, pe), pe);
737 7123 : if (DEBUGLEVEL>=3) timer_printf(&ti,"FpXQ_trace");
738 7123 : s = modii(gel(Qp_exp(cvtop(s, gen_2, e-2)),4),pe);
739 7123 : if (DEBUGLEVEL>=3) timer_printf(&ti,"Qp_exp");
740 7123 : return s;
741 : }
742 :
743 : /* Assume a2==0, so 4|E(F_p): if t^4 = a6 then (t,t^2) is of order 4
744 : 8|E(F_p) <=> trace(a6)==0
745 : */
746 :
747 : static GEN
748 7655 : F2xq_elltrace_Harley(GEN a6, GEN T2)
749 : {
750 7655 : pari_sp ltop = avma;
751 : pari_timer ti;
752 : GEN T, sqx;
753 : GEN x, x2, t;
754 7655 : long n = F2x_degree(T2), N = ((n + 1)>>1) + 2;
755 : long ispcyc;
756 7655 : if (n==1) return gen_m1;
757 7571 : if (n==2) return F2x_degree(a6) ? gen_1 : stoi(-3);
758 7620 : if (n==3) return F2x_degree(a6) ? (F2xq_trace(a6,T2) ? stoi(-3): gen_1)
759 203 : : stoi(5);
760 7417 : timer_start(&ti);
761 7417 : sqx = mkvec2(F2xq_sqrt(polx_F2x(T2[1]),T2), T2);
762 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Sqrtx");
763 7417 : ispcyc = zx_is_pcyc(F2x_to_Flx(T2));
764 7417 : T = ispcyc? F2x_to_ZX(T2): F2x_Teichmuller(T2, N-2);
765 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Teich");
766 7417 : T = FpX_get_red(T, int2n(N));
767 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Barrett");
768 7417 : x = solve_AGM_eqn(F2x_to_ZX(a6), N-2, T, sqx);
769 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Lift");
770 7417 : x2 = ZX_Z_add_shallow(ZX_shifti(x,2), gen_1);
771 7417 : t = (ispcyc? Z2XQ_invnorm_pcyc: Z2XQ_invnorm)(x2, T, N);
772 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Norm");
773 7417 : if (cmpii(sqri(t), int2n(n + 2)) > 0)
774 3499 : t = subii(t, int2n(N));
775 7417 : return gerepileuptoint(ltop, t);
776 : }
777 :
778 : static GEN
779 23737 : get_v(GEN u, GEN a, GEN T)
780 : {
781 23737 : GEN a4 = gel(a,2), a3i = gel(a,3);
782 23737 : GEN ui2 = F2xq_mul(u, a3i, T), ui4 = F2xq_sqr(ui2, T);
783 23737 : return F2xq_mul(a4, ui4, T);
784 : }
785 :
786 : static GEN
787 10493 : get_r(GEN w, GEN u, GEN T)
788 : {
789 10493 : return F2xq_sqr(F2xq_mul(F2xq_Artin_Schreier(w, T), u, T), T);
790 : }
791 :
792 : static GEN
793 37695 : F2xq_elltracej(GEN a, GEN a6, GEN T, GEN q, long n)
794 : {
795 37695 : GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
796 : GEN r, pi, rhs;
797 37695 : long t, s, m = n >> 1;
798 37695 : if (odd(n))
799 : {
800 : GEN u, v, w;
801 16856 : u = F2xq_pow(a3,diviuexact(subiu(shifti(q,1), 1), 3),T);
802 16856 : v = get_v(u, a, T);
803 16856 : if (F2xq_trace(v, T)==0) return gen_0;
804 8757 : w = F2xq_Artin_Schreier(F2x_1_add(v), T);
805 8757 : if (F2xq_trace(w, T)) w = F2x_1_add(w);
806 8757 : r = get_r(w, u, T);
807 8757 : pi = int2n(m+1);
808 8757 : s = (((m+3)&3L) <= 1) ? -1: 1;
809 : }
810 : else
811 : {
812 20839 : if (F2x_degree(F2xq_pow(a3,diviuexact(subiu(q, 1), 3),T))==0)
813 : {
814 : GEN u, v, w;
815 6881 : u = F2xq_sqrtn(a3, utoi(3), T, NULL);
816 6881 : v = get_v(u, a, T);
817 6881 : if (F2xq_trace(v, T)==1) return gen_0;
818 3507 : w = F2xq_Artin_Schreier(v, T);
819 3507 : if (F2xq_trace(w, T)==1) return gen_0;
820 1736 : r = get_r(w, u, T);
821 1736 : pi = int2n(m+1);
822 1736 : s = odd(m+1) ? -1: 1;
823 : }
824 : else
825 : {
826 13958 : long sv = T[1];
827 13958 : GEN P = mkpoln(5, pol1_F2x(sv), pol0_F2x(sv), pol0_F2x(sv), a3, a4);
828 13958 : r = F2xq_sqr(gel(F2xqX_roots(P,T), 1), T);
829 13958 : pi = int2n(m);
830 13958 : s = odd(m) ? -1: 1;
831 : }
832 : }
833 24451 : rhs = F2x_add(F2xq_mul(F2x_add(F2xq_sqr(r, T), a4), r, T), a6);
834 24451 : t = F2xq_trace(F2xq_mul(rhs, F2xq_sqr(a3i, T), T), T);
835 24451 : return (t==0)^(s==1)? pi: negi(pi);
836 : }
837 :
838 : GEN
839 45504 : F2xq_ellcard(GEN a, GEN a6, GEN T)
840 : {
841 45504 : pari_sp av = avma;
842 45504 : long n = F2x_degree(T);
843 : GEN c;
844 45504 : if (typ(a)==t_VECSMALL)
845 : {
846 7655 : GEN t = F2xq_elltrace_Harley(a6, T);
847 7655 : c = addii(int2u(n), F2xq_trace(a,T) ? addui(1,t): subui(1,t));
848 37849 : } else if (n==1)
849 : {
850 154 : long a4i = lgpol(gel(a,2)), a6i = lgpol(a6);
851 154 : return utoi(a4i? (a6i? 1: 5): 3);
852 : }
853 : else
854 : {
855 37695 : GEN q = int2u(n);
856 37695 : c = subii(addiu(q,1), F2xq_elltracej(a, a6, T, q, n));
857 : }
858 45350 : return gerepileuptoint(av, c);
859 : }
860 :
861 : /***********************************************************************/
862 : /** **/
863 : /** Group structure **/
864 : /** **/
865 : /***********************************************************************/
866 :
867 : static GEN
868 371 : _F2xqE_pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)
869 : {
870 371 : struct _F2xqE *e = (struct _F2xqE *) E;
871 371 : return F2xq_order(F2xqE_weilpairing(P,Q,m,e->a2,e->T), F, e->T);
872 : }
873 :
874 : GEN
875 3808 : F2xq_ellgroup(GEN a2, GEN a6, GEN N, GEN T, GEN *pt_m)
876 : {
877 : struct _F2xqE e;
878 3808 : GEN q = int2u(F2x_degree(T));
879 3808 : e.a2=a2; e.a6=a6; e.T=T;
880 3808 : return gen_ellgroup(N, subiu(q,1), pt_m, (void*)&e, &F2xqE_group,
881 : _F2xqE_pairorder);
882 : }
883 :
884 : GEN
885 3738 : F2xq_ellgens(GEN a2, GEN a6, GEN ch, GEN D, GEN m, GEN T)
886 : {
887 : GEN P;
888 3738 : pari_sp av = avma;
889 : struct _F2xqE e;
890 3738 : e.a2=a2; e.a6=a6; e.T=T;
891 3738 : switch(lg(D)-1)
892 : {
893 28 : case 0:
894 28 : return cgetg(1,t_VEC);
895 3598 : case 1:
896 3598 : P = gen_gener(gel(D,1), (void*)&e, &F2xqE_group);
897 3598 : P = mkvec(F2xqE_changepoint(P, ch, T));
898 3598 : break;
899 112 : default:
900 112 : P = gen_ellgens(gel(D,1), gel(D,2), m, (void*)&e, &F2xqE_group,
901 : _F2xqE_pairorder);
902 112 : gel(P,1) = F2xqE_changepoint(gel(P,1), ch, T);
903 112 : gel(P,2) = F2xqE_changepoint(gel(P,2), ch, T);
904 112 : break;
905 : }
906 3710 : return gerepilecopy(av, P);
907 : }
|
