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