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 194432 : RgE_to_F2xqE(GEN x, GEN T)
37 : {
38 194432 : if (ell_is_inf(x)) return x;
39 193949 : retmkvec2(Rg_to_F2xq(gel(x,1),T),Rg_to_F2xq(gel(x,2),T));
40 : }
41 :
42 : GEN
43 355614 : F2xqE_changepoint(GEN x, GEN ch, GEN T)
44 : {
45 355614 : pari_sp av = avma;
46 : GEN p1,z,u,r,s,t,v,v2,v3;
47 355614 : if (ell_is_inf(x)) return x;
48 187103 : u = gel(ch,1); r = gel(ch,2);
49 187103 : s = gel(ch,3); t = gel(ch,4);
50 187103 : v = F2xq_inv(u, T); v2 = F2xq_sqr(v, T); v3 = F2xq_mul(v,v2, T);
51 187103 : p1 = F2x_add(gel(x,1),r);
52 187103 : z = cgetg(3,t_VEC);
53 187103 : gel(z,1) = F2xq_mul(v2, p1, T);
54 187103 : gel(z,2) = F2xq_mul(v3, F2x_add(gel(x,2), F2x_add(F2xq_mul(s, p1, T),t)), T);
55 187103 : return gc_upto(av, z);
56 : }
57 :
58 : GEN
59 194432 : F2xqE_changepointinv(GEN x, GEN ch, GEN T)
60 : {
61 : GEN u, r, s, t, X, Y, u2, u3, u2X, z;
62 194432 : if (ell_is_inf(x)) return x;
63 193949 : X = gel(x,1); Y = gel(x,2);
64 193949 : u = gel(ch,1); r = gel(ch,2);
65 193949 : s = gel(ch,3); t = gel(ch,4);
66 193949 : u2 = F2xq_sqr(u, T); u3 = F2xq_mul(u,u2, T);
67 193949 : u2X = F2xq_mul(u2,X, T);
68 193949 : z = cgetg(3, t_VEC);
69 193949 : gel(z,1) = F2x_add(u2X,r);
70 193949 : gel(z,2) = F2x_add(F2xq_mul(u3,Y, T), F2x_add(F2xq_mul(s,u2X, T), t));
71 193949 : 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 4774 : set_avma(av);
85 4774 : a = random_F2x(n, vs);
86 4774 : } 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 = gc_uptoleaf(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 = gc_uptoleaf(av, a6t);
103 0 : *pt_a = vecsmall_copy(a);
104 : }
105 3514 : }
106 :
107 : static GEN
108 1060325 : F2xqE_dbl_slope(GEN P, GEN a, GEN T, GEN *slope)
109 : {
110 : GEN x, y, Q;
111 1060325 : if (ell_is_inf(P)) return ellinf();
112 1047438 : x = gel(P,1); y = gel(P,2);
113 1047438 : if (typ(a)==t_VECSMALL)
114 : {
115 193242 : GEN a2 = a;
116 193242 : if (!lgpol(gel(P,1))) { *slope = NULL; return ellinf(); }
117 176806 : *slope = F2x_add(x, F2xq_div(y, x, T));
118 176806 : Q = cgetg(3,t_VEC);
119 176806 : gel(Q, 1) = F2x_add(F2xq_sqr(*slope, T), F2x_add(*slope, a2));
120 176806 : 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 854196 : GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
125 854196 : *slope = F2xq_mul(F2x_add(a4, F2xq_sqr(x, T)), a3i, T);
126 854196 : Q = cgetg(3,t_VEC);
127 854196 : gel(Q, 1) = F2xq_sqr(*slope, T);
128 854196 : gel(Q, 2) = F2x_add(F2xq_mul(*slope, F2x_add(x, gel(Q, 1)), T), F2x_add(y, a3));
129 : }
130 1031002 : return Q;
131 : }
132 :
133 : GEN
134 1042041 : F2xqE_dbl(GEN P, GEN a, GEN T)
135 : {
136 1042041 : pari_sp av = avma;
137 : GEN slope;
138 1042041 : return gc_upto(av, F2xqE_dbl_slope(P, a, T,&slope));
139 : }
140 :
141 : static GEN
142 350994 : F2xqE_add_slope(GEN P, GEN Q, GEN a, GEN T, GEN *slope)
143 : {
144 : GEN Px, Py, Qx, Qy, R;
145 350994 : if (ell_is_inf(P)) { *slope = NULL; return Q; }
146 349398 : if (ell_is_inf(Q)) { *slope = NULL; return P; }
147 349391 : Px = gel(P,1); Py = gel(P,2);
148 349391 : Qx = gel(Q,1); Qy = gel(Q,2);
149 349391 : if (F2x_equal(Px, Qx))
150 : {
151 157080 : if (F2x_equal(Py, Qy))
152 1421 : return F2xqE_dbl_slope(P, a, T, slope);
153 : else
154 155659 : { *slope = NULL; return ellinf(); }
155 : }
156 192311 : *slope = F2xq_div(F2x_add(Py, Qy), F2x_add(Px, Qx), T);
157 192311 : R = cgetg(3,t_VEC);
158 192311 : if (typ(a)==t_VECSMALL)
159 : {
160 62776 : GEN a2 = a;
161 62776 : gel(R, 1) = F2x_add(F2x_add(F2x_add(F2x_add(F2xq_sqr(*slope, T), *slope), Px), Qx), a2);
162 62776 : 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 129535 : GEN a3 = gel(a,1);
167 129535 : gel(R, 1) = F2x_add(F2x_add(F2xq_sqr(*slope, T), Px), Qx);
168 129535 : gel(R, 2) = F2x_add(F2xq_mul(*slope, F2x_add(Px, gel(R, 1)), T), F2x_add(Py, a3));
169 : }
170 192311 : return R;
171 : }
172 :
173 : GEN
174 350959 : F2xqE_add(GEN P, GEN Q, GEN a, GEN T)
175 : {
176 350959 : pari_sp av = avma;
177 : GEN slope;
178 350959 : return gc_upto(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 gc_upto(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 1042041 : _F2xqE_dbl(void *E, GEN P)
216 : {
217 1042041 : struct _F2xqE *ell = (struct _F2xqE *) E;
218 1042041 : return F2xqE_dbl(P, ell->a2, ell->T);
219 : }
220 :
221 : static GEN
222 350959 : _F2xqE_add(void *E, GEN P, GEN Q)
223 : {
224 350959 : struct _F2xqE *ell=(struct _F2xqE *) E;
225 350959 : return F2xqE_add(P, Q, ell->a2, ell->T);
226 : }
227 :
228 : static GEN
229 213101 : _F2xqE_mul(void *E, GEN P, GEN n)
230 : {
231 213101 : pari_sp av = avma;
232 213101 : struct _F2xqE *e=(struct _F2xqE *) E;
233 213101 : long s = signe(n);
234 213101 : if (!s || ell_is_inf(P)) return ellinf();
235 208824 : if (s<0) P = F2xqE_neg(P, e->a2, e->T);
236 208824 : if (is_pm1(n)) return s>0? gcopy(P): P;
237 203350 : return gc_GEN(av, gen_pow_i(P, n, e, &_F2xqE_dbl, &_F2xqE_add));
238 : }
239 :
240 : GEN
241 184072 : F2xqE_mul(GEN P, GEN n, GEN a2, GEN T)
242 : {
243 : struct _F2xqE E;
244 184072 : E.a2 = a2; E.T = T;
245 184072 : return _F2xqE_mul(&E, P, n);
246 : }
247 :
248 : /* Finds a random nonsingular point on E */
249 : GEN
250 181153 : random_F2xqE(GEN a, GEN a6, GEN T)
251 : {
252 181153 : pari_sp ltop = avma;
253 : GEN x, y, rhs, u;
254 : do
255 : {
256 375095 : set_avma(ltop);
257 375095 : x = random_F2x(F2x_degree(T),T[1]);
258 375095 : if (typ(a) == t_VECSMALL)
259 : {
260 61712 : GEN a2 = a, x2;
261 61712 : if (!lgpol(x))
262 721 : { set_avma(ltop); retmkvec2(pol0_Flx(T[1]), F2xq_sqrt(a6,T)); }
263 60991 : u = x; x2 = F2xq_sqr(x, T);
264 60991 : rhs = F2x_add(F2xq_mul(x2,F2x_add(x,a2),T),a6);
265 60991 : rhs = F2xq_div(rhs,x2,T);
266 : }
267 : else
268 : {
269 313383 : GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3), u2i;
270 313383 : u = a3; u2i = F2xq_sqr(a3i,T);
271 313383 : rhs = F2x_add(F2xq_mul(x,F2x_add(F2xq_sqr(x,T),a4),T),a6);
272 313383 : rhs = F2xq_mul(rhs,u2i,T);
273 : }
274 374374 : } while (F2xq_trace(rhs,T));
275 180432 : y = F2xq_mul(F2xq_Artin_Schreier(rhs, T), u, T);
276 180432 : return gc_GEN(ltop, mkvec2(x, y));
277 : }
278 :
279 : static GEN
280 13433 : _F2xqE_rand(void *E)
281 : {
282 13433 : struct _F2xqE *ell=(struct _F2xqE *) E;
283 13433 : 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 gc_INT(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 gc_INT(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 19271 : is_2_torsion(GEN Q, GEN a)
325 : {
326 19271 : return (typ(a)==t_VEC || lgpol(gel(Q, 1))) ? 0: 1;
327 : }
328 :
329 : static GEN
330 35000 : F2xqE_vert(GEN P, GEN Q, GEN a, GEN T)
331 : {
332 35000 : long vT = T[1];
333 35000 : if (ell_is_inf(P))
334 9051 : return pol1_F2x(T[1]);
335 25949 : if (!F2x_equal(gel(Q, 1), gel(P, 1)))
336 24255 : return F2x_add(gel(Q, 1), gel(P, 1));
337 1694 : if (is_2_torsion(Q, a))
338 0 : return F2xq_inv(gel(Q,2), T);
339 1694 : return pol1_F2x(vT);
340 : }
341 :
342 : static GEN
343 16898 : F2xqE_Miller_line(GEN R, GEN Q, GEN slope, GEN a, GEN T)
344 : {
345 16898 : long vT = T[1];
346 16898 : GEN x = gel(Q, 1), y = gel(Q, 2);
347 16898 : GEN tmp1 = F2x_add(x, gel(R, 1));
348 16898 : GEN tmp2 = F2x_add(F2xq_mul(tmp1, slope, T), gel(R, 2));
349 : GEN s1, s2, ix;
350 16898 : if (!F2x_equal(y, tmp2))
351 16184 : 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 16863 : F2xqE_tangent_update(GEN R, GEN Q, GEN a2, GEN T, GEN *pt_R)
382 : {
383 16863 : if (ell_is_inf(R))
384 : {
385 0 : *pt_R = ellinf();
386 0 : return pol1_F2x(T[1]);
387 : }
388 16863 : 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 16863 : *pt_R = F2xqE_dbl_slope(R, a2, T, &slope);
395 16863 : 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 9086 : F2xqE_chord_update(GEN R, GEN P, GEN Q, GEN a2, GEN T, GEN *pt_R)
405 : {
406 9086 : if (ell_is_inf(R))
407 : {
408 0 : *pt_R = gcopy(P);
409 0 : return F2xqE_vert(P, Q, a2, T);
410 : }
411 9086 : else if (ell_is_inf(P))
412 : {
413 0 : *pt_R = gcopy(R);
414 0 : return F2xqE_vert(R, Q, a2, T);
415 : }
416 9086 : else if (F2x_equal(gel(P, 1), gel(R, 1)))
417 : {
418 9051 : 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 9051 : *pt_R = ellinf();
423 9051 : 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 16863 : F2xqE_Miller_dbl(void* E, GEN d)
436 : {
437 16863 : struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
438 16863 : GEN T = m->T, a2 = m->a2, P = m->P;
439 16863 : GEN v, line, point = gel(d,3);
440 16863 : GEN N = F2xq_sqr(gel(d,1), T);
441 16863 : GEN D = F2xq_sqr(gel(d,2), T);
442 16863 : line = F2xqE_tangent_update(point, P, a2, T, &point);
443 16863 : N = F2xq_mul(N, line, T);
444 16863 : v = F2xqE_vert(point, P, a2, T);
445 16863 : D = F2xq_mul(D, v, T); return mkvec3(N, D, point);
446 : }
447 : static GEN
448 9086 : F2xqE_Miller_add(void* E, GEN va, GEN vb)
449 : {
450 9086 : struct _F2xqE_miller *m = (struct _F2xqE_miller *)E;
451 9086 : GEN T = m->T, a2 = m->a2, P = m->P;
452 : GEN v, line, point;
453 9086 : GEN na = gel(va,1), da = gel(va,2), pa = gel(va,3);
454 9086 : GEN nb = gel(vb,1), db = gel(vb,2), pb = gel(vb,3);
455 9086 : GEN N = F2xq_mul(na, nb, T);
456 9086 : GEN D = F2xq_mul(da, db, T);
457 9086 : line = F2xqE_chord_update(pa, pb, P, a2, T, &point);
458 9086 : N = F2xq_mul(N, line, T);
459 9086 : v = F2xqE_vert(point, P, a2, T);
460 9086 : 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 9086 : F2xqE_Miller(GEN Q, GEN P, GEN m, GEN a2, GEN T)
466 : {
467 9086 : pari_sp av = avma;
468 : struct _F2xqE_miller d;
469 : GEN v, N, D, g1;
470 :
471 9086 : d.a2 = a2; d.T = T; d.P = P;
472 9086 : g1 = pol1_F2x(T[1]);
473 9086 : v = gen_pow_i(mkvec3(g1,g1,Q), m, (void*)&d, F2xqE_Miller_dbl, F2xqE_Miller_add);
474 9086 : N = gel(v,1); D = gel(v,2);
475 9086 : return gc_upto(av, F2xq_div(N, D, T));
476 : }
477 :
478 : GEN
479 5355 : F2xqE_weilpairing(GEN P, GEN Q, GEN m, GEN a2, GEN T)
480 : {
481 5355 : pari_sp av = avma;
482 : GEN N, D;
483 5355 : if (ell_is_inf(P) || ell_is_inf(Q)
484 4795 : || (F2x_equal(gel(P,1),gel(Q,1)) && F2x_equal(gel(P,2),gel(Q,2))))
485 826 : return pol1_F2x(T[1]);
486 4529 : N = F2xqE_Miller(P, Q, m, a2, T);
487 4529 : D = F2xqE_Miller(Q, P, m, a2, T);
488 4529 : return gc_upto(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 68638 : Z2x_rshift(GEN y, long x)
507 : {
508 : GEN z;
509 : long i, l;
510 68638 : if (!x) return pol0_Flx(y[1]);
511 68638 : z = cgetg_copy(y, &l); z[1] = y[1];
512 7641861 : for(i=2; i<l; i++) z[i] = y[i]>>x;
513 68637 : return Flx_renormalize(z, l);
514 : }
515 :
516 : /* Solve the linear equation approximation in the Newton algorithm */
517 :
518 : static GEN
519 170302 : 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 170302 : pari_sp av = avma;
522 : long N2, M;
523 : GEN VN2, V2, VM, bil;
524 170302 : ulong q = 1UL<<N;
525 170302 : if (N == 1) return invl(E, V);
526 68605 : V = Flx_red(V, q);
527 68639 : N2 = (N + 1)>>1; M = N - N2;
528 68639 : F = FlxT_red(F, q);
529 68640 : 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 68648 : VM = gen_Z2x_Dixon(F, V2, M, E, lin, invl);
533 68645 : return gc_upto(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 33079 : 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 33079 : pari_sp av = avma;
550 : long n, m;
551 : GEN Xn, Xm, FXn, Vm;
552 33079 : if (N<BITS_IN_LONG)
553 : {
554 33059 : ulong q = 1UL<<N;
555 33059 : 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 gc_upto(av, ZX_remi2n(ZX_add(Xn, ZX_shifti(Xm, n)), N));
565 : }
566 :
567 : /* H -> H mod 2*/
568 :
569 50593 : 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 gc_upto(av, ZX_remi2n(z, N));
581 : }
582 :
583 34189 : static GEN _can_lins(void *E, GEN F, GEN V, long N)
584 : {
585 34189 : GEN D=Flx_splitting(V, 2), z;
586 34187 : ulong q = 1UL<<N;
587 : (void) E;
588 34187 : z = Flx_sub(Flx_mul(gel(F,1), gel(D,1), q), Flx_mul(gel(F,2), gel(D,2), q), q);
589 34186 : return Flx_sub(V, z, q);
590 : }
591 :
592 : /* P -> P-(P0^2-X*P1^2) */
593 :
594 : static GEN
595 16396 : _can_iter(void *E, GEN f2, GEN q)
596 : {
597 : GEN f0, f1, z;
598 : (void) E;
599 16396 : 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 16395 : return mkvec3(z,f0,f1);
602 : }
603 :
604 : /* H -> H-(2*P0*H0-2*X*P1*H1) */
605 :
606 : static GEN
607 16397 : _can_invd(void *E, GEN V, GEN v, GEN q, long M)
608 : {
609 : GEN F;
610 : (void)E; (void)q;
611 16397 : F = mkvec2(ZX_shifti(gel(v,2),1), ZX_shifti(RgX_shift_shallow(gel(v,3),1),1));
612 16397 : 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 34460 : Z2xq_frob(GEN x, GEN T, ulong q)
630 : {
631 34460 : 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 51108 : static GEN _frob_invls(void *E, GEN V)
642 : {
643 51108 : struct _frob_lift *F = (struct _frob_lift*) E;
644 51108 : GEN sqx = F->sqx;
645 51108 : 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 34461 : static GEN _frob_lins(void *E, GEN F, GEN x2, long N)
661 : {
662 34461 : GEN T = gel(F,3);
663 34461 : ulong q = 1UL<<N;
664 34461 : 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 34458 : return Flx_rem(lin, T, q);
668 : }
669 :
670 : /* X -> P(X,S(X)) */
671 :
672 : static GEN
673 16641 : _lift_iter(void *E, GEN x2, GEN q)
674 : {
675 16641 : struct _frob_lift *F = (struct _frob_lift*) E;
676 16641 : long N = expi(q);
677 16641 : 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 16642 : 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 16641 : _lift_invd(void *E, GEN V, GEN v, GEN qM, long M)
688 : {
689 16641 : struct _frob_lift *F = (struct _frob_lift*) E;
690 16641 : 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 16641 : Dy = FpX_rem(ZX_remi2n(Dy, M), TM, qM);
698 16642 : 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 = Qp_exp(cvtop(s, gen_2, e-2));
739 7123 : s = modii(padic_u(s), pe);
740 7123 : if (DEBUGLEVEL>=3) timer_printf(&ti,"Qp_exp");
741 7123 : return s;
742 : }
743 :
744 : /* Assume a2==0, so 4|E(F_p): if t^4 = a6 then (t,t^2) is of order 4
745 : 8|E(F_p) <=> trace(a6)==0
746 : */
747 :
748 : static GEN
749 7655 : F2xq_elltrace_Harley(GEN a6, GEN T2)
750 : {
751 7655 : pari_sp ltop = avma;
752 : pari_timer ti;
753 : GEN T, sqx;
754 : GEN x, x2, t;
755 7655 : long n = F2x_degree(T2), N = ((n + 1)>>1) + 2;
756 : long ispcyc;
757 7655 : if (n==1) return gen_m1;
758 7571 : if (n==2) return F2x_degree(a6) ? gen_1 : stoi(-3);
759 7620 : if (n==3) return F2x_degree(a6) ? (F2xq_trace(a6,T2) ? stoi(-3): gen_1)
760 203 : : stoi(5);
761 7417 : timer_start(&ti);
762 7417 : sqx = mkvec2(F2xq_sqrt(polx_F2x(T2[1]),T2), T2);
763 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Sqrtx");
764 7417 : ispcyc = zx_is_pcyc(F2x_to_Flx(T2));
765 7417 : T = ispcyc? F2x_to_ZX(T2): F2x_Teichmuller(T2, N-2);
766 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Teich");
767 7417 : T = FpX_get_red(T, int2n(N));
768 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Barrett");
769 7417 : x = solve_AGM_eqn(F2x_to_ZX(a6), N-2, T, sqx);
770 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Lift");
771 7417 : x2 = ZX_Z_add_shallow(ZX_shifti(x,2), gen_1);
772 7417 : t = (ispcyc? Z2XQ_invnorm_pcyc: Z2XQ_invnorm)(x2, T, N);
773 7417 : if (DEBUGLEVEL>1) timer_printf(&ti,"Norm");
774 7417 : if (cmpii(sqri(t), int2n(n + 2)) > 0)
775 3499 : t = subii(t, int2n(N));
776 7417 : return gc_INT(ltop, t);
777 : }
778 :
779 : static GEN
780 23870 : get_v(GEN u, GEN a, GEN T)
781 : {
782 23870 : GEN a4 = gel(a,2), a3i = gel(a,3);
783 23870 : GEN ui2 = F2xq_mul(u, a3i, T), ui4 = F2xq_sqr(ui2, T);
784 23870 : return F2xq_mul(a4, ui4, T);
785 : }
786 :
787 : static GEN
788 10073 : get_r(GEN w, GEN u, GEN T)
789 : {
790 10073 : return F2xq_sqr(F2xq_mul(F2xq_Artin_Schreier(w, T), u, T), T);
791 : }
792 :
793 : static GEN
794 37653 : F2xq_elltracej(GEN a, GEN a6, GEN T, GEN q, long n)
795 : {
796 37653 : GEN a3 = gel(a,1), a4 = gel(a,2), a3i = gel(a,3);
797 : GEN r, pi, rhs;
798 37653 : long t, s, m = n >> 1;
799 37653 : if (odd(n))
800 : {
801 : GEN u, v, w;
802 16849 : u = F2xq_pow(a3,diviuexact(subiu(shifti(q,1), 1), 3),T);
803 16849 : v = get_v(u, a, T);
804 16849 : if (F2xq_trace(v, T)==0) return gen_0;
805 8288 : w = F2xq_Artin_Schreier(F2x_1_add(v), T);
806 8288 : if (F2xq_trace(w, T)) w = F2x_1_add(w);
807 8288 : r = get_r(w, u, T);
808 8288 : pi = int2n(m+1);
809 8288 : s = (((m+3)&3L) <= 1) ? -1: 1;
810 : }
811 : else
812 : {
813 20804 : if (F2x_degree(F2xq_pow(a3,diviuexact(subiu(q, 1), 3),T))==0)
814 : {
815 : GEN u, v, w;
816 7021 : u = F2xq_sqrtn(a3, utoi(3), T, NULL);
817 7021 : v = get_v(u, a, T);
818 7021 : if (F2xq_trace(v, T)==1) return gen_0;
819 3591 : w = F2xq_Artin_Schreier(v, T);
820 3591 : if (F2xq_trace(w, T)==1) return gen_0;
821 1785 : r = get_r(w, u, T);
822 1785 : pi = int2n(m+1);
823 1785 : s = odd(m+1) ? -1: 1;
824 : }
825 : else
826 : {
827 13783 : long sv = T[1];
828 13783 : GEN P = mkpoln(5, pol1_F2x(sv), pol0_F2x(sv), pol0_F2x(sv), a3, a4);
829 13783 : r = F2xq_sqr(gel(F2xqX_roots(P,T), 1), T);
830 13783 : pi = int2n(m);
831 13783 : s = odd(m) ? -1: 1;
832 : }
833 : }
834 23856 : rhs = F2x_add(F2xq_mul(F2x_add(F2xq_sqr(r, T), a4), r, T), a6);
835 23856 : t = F2xq_trace(F2xq_mul(rhs, F2xq_sqr(a3i, T), T), T);
836 23856 : return (t==0)^(s==1)? pi: negi(pi);
837 : }
838 :
839 : GEN
840 45462 : F2xq_ellcard(GEN a, GEN a6, GEN T)
841 : {
842 45462 : pari_sp av = avma;
843 45462 : long n = F2x_degree(T);
844 : GEN c;
845 45462 : if (typ(a)==t_VECSMALL)
846 : {
847 7655 : GEN t = F2xq_elltrace_Harley(a6, T);
848 7655 : c = addii(int2u(n), F2xq_trace(a,T) ? addui(1,t): subui(1,t));
849 37807 : } else if (n==1)
850 : {
851 154 : long a4i = lgpol(gel(a,2)), a6i = lgpol(a6);
852 154 : return utoi(a4i? (a6i? 1: 5): 3);
853 : }
854 : else
855 : {
856 37653 : GEN q = int2u(n);
857 37653 : c = subii(addiu(q,1), F2xq_elltracej(a, a6, T, q, n));
858 : }
859 45308 : return gc_INT(av, c);
860 : }
861 :
862 : /***********************************************************************/
863 : /** **/
864 : /** Group structure **/
865 : /** **/
866 : /***********************************************************************/
867 :
868 : static GEN
869 385 : _F2xqE_pairorder(void *E, GEN P, GEN Q, GEN m, GEN F)
870 : {
871 385 : struct _F2xqE *e = (struct _F2xqE *) E;
872 385 : return F2xq_order(F2xqE_weilpairing(P,Q,m,e->a2,e->T), F, e->T);
873 : }
874 :
875 : GEN
876 3808 : F2xq_ellgroup(GEN a2, GEN a6, GEN N, GEN T, GEN *pt_m)
877 : {
878 : struct _F2xqE e;
879 3808 : GEN q = int2u(F2x_degree(T));
880 3808 : e.a2=a2; e.a6=a6; e.T=T;
881 3808 : return gen_ellgroup(N, subiu(q,1), pt_m, (void*)&e, &F2xqE_group,
882 : _F2xqE_pairorder);
883 : }
884 :
885 : GEN
886 3738 : F2xq_ellgens(GEN a2, GEN a6, GEN ch, GEN D, GEN m, GEN T)
887 : {
888 : GEN P;
889 3738 : pari_sp av = avma;
890 : struct _F2xqE e;
891 3738 : e.a2=a2; e.a6=a6; e.T=T;
892 3738 : switch(lg(D)-1)
893 : {
894 28 : case 0:
895 28 : return cgetg(1,t_VEC);
896 3598 : case 1:
897 3598 : P = gen_gener(gel(D,1), (void*)&e, &F2xqE_group);
898 3598 : P = mkvec(F2xqE_changepoint(P, ch, T));
899 3598 : break;
900 112 : default:
901 112 : P = gen_ellgens(gel(D,1), gel(D,2), m, (void*)&e, &F2xqE_group,
902 : _F2xqE_pairorder);
903 112 : gel(P,1) = F2xqE_changepoint(gel(P,1), ch, T);
904 112 : gel(P,2) = F2xqE_changepoint(gel(P,2), ch, T);
905 112 : break;
906 : }
907 3710 : return gc_GEN(av, P);
908 : }
|
