1 /* Copyright (C) 2000-2003 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 /*************************************************************************/
19 /** **/
20 /** Routines for handling FFELT **/
21 /** **/
22 /*************************************************************************/
23
24 /*************************************************************************/
25 /** **/
26 /** Low-level constructors **/
27 /** **/
28 /*************************************************************************/
29
30 INLINE void
_getFF(GEN x,GEN * T,GEN * p,ulong * pp)31 _getFF(GEN x, GEN *T, GEN *p, ulong *pp)
32 {
33 *T=gel(x,3);
34 *p=gel(x,4);
35 *pp=(*p)[2];
36 }
37
38 INLINE GEN
_initFF(GEN x,GEN * T,GEN * p,ulong * pp)39 _initFF(GEN x, GEN *T, GEN *p, ulong *pp)
40 {
41 _getFF(x,T,p,pp);
42 return cgetg(5,t_FFELT);
43 }
44
45 INLINE void
_checkFF(GEN x,GEN y,const char * s)46 _checkFF(GEN x, GEN y, const char *s)
47 { if (!FF_samefield(x,y)) pari_err_OP(s,x,y); }
48
49 INLINE GEN
_mkFF(GEN x,GEN z,GEN r)50 _mkFF(GEN x, GEN z, GEN r)
51 {
52 z[1]=x[1];
53 gel(z,2)=r;
54 gel(z,3)=gcopy(gel(x,3));
55 gel(z,4)=icopy(gel(x,4));
56 return z;
57 }
58
59 INLINE GEN
_mkFF_i(GEN x,GEN z,GEN r)60 _mkFF_i(GEN x, GEN z, GEN r)
61 {
62 z[1]=x[1];
63 gel(z,2)=r;
64 gel(z,3)=gel(x,3);
65 gel(z,4)=gel(x,4);
66 return z;
67 }
68
69 INLINE GEN
mkFF_i(GEN x,GEN r)70 mkFF_i(GEN x, GEN r)
71 {
72 GEN z = cgetg(5,t_FFELT);
73 return _mkFF_i(x,z,r);
74 }
75
76 /*************************************************************************/
77 /** **/
78 /** medium-level constructors **/
79 /** **/
80 /*************************************************************************/
81
82 static GEN
Z_to_raw(GEN x,GEN ff)83 Z_to_raw(GEN x, GEN ff)
84 {
85 ulong pp;
86 GEN T, p;
87 _getFF(ff,&T,&p,&pp);
88 switch(ff[1])
89 {
90 case t_FF_FpXQ:
91 return scalarpol(x, varn(T));
92 case t_FF_F2xq:
93 return Z_to_F2x(x, T[1]);
94 default:
95 return Z_to_Flx(x, pp, T[1]);
96 }
97 }
98
99 static GEN
Rg_to_raw(GEN x,GEN ff)100 Rg_to_raw(GEN x, GEN ff)
101 {
102 long tx = typ(x);
103 switch(tx)
104 {
105 case t_INT: case t_FRAC: case t_PADIC: case t_INTMOD:
106 return Z_to_raw(Rg_to_Fp(x, FF_p_i(ff)), ff);
107 case t_FFELT:
108 if (!FF_samefield(x,ff))
109 pari_err_MODULUS("Rg_to_raw",x,ff);
110 return gel(x,2);
111 }
112 pari_err_TYPE("Rg_to_raw",x);
113 return NULL;/* LCOV_EXCL_LINE */
114 }
115
116 static GEN
FFX_to_raw(GEN x,GEN ff)117 FFX_to_raw(GEN x, GEN ff)
118 {
119 long i, lx;
120 GEN y = cgetg_copy(x,&lx);
121 y[1] = x[1];
122 for(i=2; i<lx; i++)
123 gel(y, i) = Rg_to_raw(gel(x, i), ff);
124 switch (ff[1])
125 {
126 case t_FF_FpXQ:
127 return FpXX_renormalize(y, lx);
128 case t_FF_F2xq:
129 return F2xX_renormalize(y, lx);
130 default:
131 return FlxX_renormalize(y, lx);
132 }
133 }
134
135 static GEN
FFC_to_raw(GEN x,GEN ff)136 FFC_to_raw(GEN x, GEN ff) { pari_APPLY_same(Rg_to_raw(gel(x, i), ff)) }
137 static GEN
FFM_to_raw(GEN x,GEN ff)138 FFM_to_raw(GEN x, GEN ff) { pari_APPLY_same(FFC_to_raw(gel(x, i), ff)) }
139
140 /* in place */
141 static GEN
rawFq_to_FF(GEN x,GEN ff)142 rawFq_to_FF(GEN x, GEN ff)
143 {
144 return mkFF_i(ff, typ(x)==t_INT ? scalarpol(x, varn(gel(ff,3))): x);
145 }
146
147 /* in place */
148 static GEN
raw_to_FFX(GEN x,GEN ff)149 raw_to_FFX(GEN x, GEN ff)
150 {
151 long i, lx = lg(x);
152 for (i=2; i<lx; i++) gel(x,i) = rawFq_to_FF(gel(x,i), ff);
153 return x;
154 }
155
156 /* in place */
157 static GEN
raw_to_FFC(GEN x,GEN ff)158 raw_to_FFC(GEN x, GEN ff)
159 {
160 long i, lx = lg(x);
161 for (i=1; i<lx; i++) gel(x,i) = mkFF_i(ff, gel(x,i));
162 return x;
163 }
164
165 /* in place */
166 static GEN
raw_to_FFM(GEN x,GEN ff)167 raw_to_FFM(GEN x, GEN ff)
168 {
169 long i, lx = lg(x);
170 for (i=1; i<lx; i++) gel(x,i) = raw_to_FFC(gel(x,i), ff);
171 return x;
172 }
173
174 GEN
Fq_to_FF(GEN x,GEN ff)175 Fq_to_FF(GEN x, GEN ff)
176 {
177 ulong pp;
178 GEN r, T, p, z=_initFF(ff,&T,&p,&pp);
179 int is_int = typ(x)==t_INT;
180 switch(ff[1])
181 {
182 case t_FF_FpXQ:
183 r= is_int ? scalarpol(x, varn(T)): ZX_copy(x);
184 break;
185 case t_FF_F2xq:
186 r= is_int ? Z_to_F2x(x,T[1]): ZX_to_F2x(x);
187 break;
188 default:
189 r= is_int ? Z_to_Flx(x,pp,T[1]): ZX_to_Flx(x,pp);
190 }
191 setvarn(r, varn(T)); /* paranoia */
192 return _mkFF_i(ff,z,r);
193 }
194
195 /*************************************************************************/
196 /** **/
197 /** Public functions **/
198 /** **/
199 /*************************************************************************/
200
201 /* Return true if x and y are defined in the same field */
202
203 static int
FF_samechar(GEN x,GEN y)204 FF_samechar(GEN x, GEN y)
205 { return x[1] == y[1] && equalii(gel(x,4),gel(y,4)); }
206
207 int
FF_samefield(GEN x,GEN y)208 FF_samefield(GEN x, GEN y)
209 { return FF_samechar(x, y) && gidentical(gel(x,3),gel(y,3)); }
210
211 int
FF_equal(GEN x,GEN y)212 FF_equal(GEN x, GEN y)
213 { return FF_samefield(x,y) && gidentical(gel(x,2),gel(y,2)); }
214
215 int
FF_equal0(GEN x)216 FF_equal0(GEN x)
217 {
218 return lgpol(gel(x,2))==0;
219 }
220
221 int
FF_equal1(GEN x)222 FF_equal1(GEN x)
223 {
224 GEN A = gel(x,2);
225 switch(x[1])
226 {
227 case t_FF_FpXQ:
228 return degpol(A)==0 && gequal1(gel(A,2));
229 default:
230 return degpol(A)==0 && A[2]==1;
231 }
232 }
233
234 static int
Fp_cmp_1(GEN x,GEN p)235 Fp_cmp_1(GEN x, GEN p)
236 { pari_sp av = avma; return gc_bool(av, equalii(x, addis(p,-1))); }
237
238 int
FF_equalm1(GEN x)239 FF_equalm1(GEN x)
240 {
241 ulong pp;
242 GEN T, p, y = gel(x,2);
243 _getFF(x,&T,&p,&pp);
244 switch(x[1])
245 {
246 case t_FF_FpXQ:
247 return (degpol(y) == 0 && Fp_cmp_1(gel(y,2), p));
248 default:
249 return (degpol(y) == 0 && uel(y,2) == pp-1);
250 }
251 }
252
253 GEN
FF_zero(GEN x)254 FF_zero(GEN x)
255 {
256 ulong pp;
257 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
258 switch(x[1])
259 {
260 case t_FF_FpXQ:
261 r=zeropol(varn(T));
262 break;
263 case t_FF_F2xq:
264 r=zero_F2x(T[1]);
265 break;
266 default:
267 r=zero_Flx(T[1]);
268 }
269 return _mkFF(x,z,r);
270 }
271
272 GEN
FF_1(GEN x)273 FF_1(GEN x)
274 {
275 ulong pp;
276 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
277 switch(x[1])
278 {
279 case t_FF_FpXQ:
280 r=pol_1(varn(T));
281 break;
282 case t_FF_F2xq:
283 r=pol1_F2x(T[1]);
284 break;
285 default:
286 r=pol1_Flx(T[1]);
287 }
288 return _mkFF(x,z,r);
289 }
290
291 GEN
FF_gen(GEN x)292 FF_gen(GEN x)
293 {
294 ulong pp;
295 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
296 switch(x[1])
297 {
298 case t_FF_FpXQ:
299 r = pol_x(varn(T));
300 if (degpol(T)==1) r = FpX_rem(r, T, p);
301 break;
302 case t_FF_F2xq:
303 r = polx_F2x(T[1]);
304 if (F2x_degree(T)==1) r = F2x_rem(r, T);
305 break;
306 default:
307 r = polx_Flx(T[1]);
308 if (degpol(T)==1) r = Flx_rem(r, T, pp);
309 }
310 return _mkFF(x,z,r);
311 }
312 GEN
FF_q(GEN x)313 FF_q(GEN x)
314 {
315 ulong pp;
316 GEN T, p;
317 _getFF(x,&T,&p,&pp);
318 switch(x[1])
319 {
320 case t_FF_FpXQ:
321 return powiu(p, degpol(T));
322 break;
323 case t_FF_F2xq:
324 return int2n(F2x_degree(T));
325 break;
326 default:
327 return powuu(pp,degpol(T));
328 }
329 }
330
331 GEN
FF_p(GEN x)332 FF_p(GEN x)
333 {
334 return icopy(gel(x,4));
335 }
336
337 GEN
FF_p_i(GEN x)338 FF_p_i(GEN x)
339 {
340 return gel(x,4);
341 }
342
343 GEN
FF_mod(GEN x)344 FF_mod(GEN x)
345 {
346 switch(x[1])
347 {
348 case t_FF_FpXQ:
349 return ZX_copy(gel(x,3));
350 case t_FF_F2xq:
351 return F2x_to_ZX(gel(x,3));
352 default:
353 return Flx_to_ZX(gel(x,3));
354 }
355 }
356
357 long
FF_var(GEN x)358 FF_var(GEN x)
359 {
360 switch(x[1])
361 {
362 case t_FF_FpXQ:
363 return varn(gel(x,3));
364 case t_FF_F2xq:
365 default:
366 return gel(x,3)[1]>>VARNSHIFT;
367 }
368 }
369
370 long
FF_f(GEN x)371 FF_f(GEN x)
372 {
373 switch(x[1])
374 {
375 case t_FF_F2xq:
376 return F2x_degree(gel(x,3));
377 default:
378 return degpol(gel(x,3));
379 }
380 }
381
382 GEN
FF_to_F2xq(GEN x)383 FF_to_F2xq(GEN x)
384 {
385 switch(x[1])
386 {
387 case t_FF_FpXQ:
388 return ZX_to_F2x(gel(x,2));
389 case t_FF_F2xq:
390 return zv_copy(gel(x,2));
391 default:
392 return Flx_to_F2x(gel(x,2));
393 }
394 }
395
396 GEN
FF_to_F2xq_i(GEN x)397 FF_to_F2xq_i(GEN x)
398 {
399 switch(x[1])
400 {
401 case t_FF_FpXQ:
402 return ZX_to_F2x(gel(x,2));
403 case t_FF_F2xq:
404 return gel(x,2);
405 default:
406 return Flx_to_F2x(gel(x,2));
407 }
408 }
409
410 GEN
FF_to_Flxq(GEN x)411 FF_to_Flxq(GEN x)
412 {
413 switch(x[1])
414 {
415 case t_FF_FpXQ:
416 return ZX_to_Flx(gel(x,2),itou(gel(x,4)));
417 case t_FF_F2xq:
418 return F2x_to_Flx(gel(x,2));
419 default:
420 return zv_copy(gel(x,2));
421 }
422 }
423
424 GEN
FF_to_Flxq_i(GEN x)425 FF_to_Flxq_i(GEN x)
426 {
427 switch(x[1])
428 {
429 case t_FF_FpXQ:
430 return ZX_to_Flx(gel(x,2),itou(gel(x,4)));
431 case t_FF_F2xq:
432 return F2x_to_Flx(gel(x,2));
433 default:
434 return gel(x,2);
435 }
436 }
437
438 GEN
FF_to_FpXQ(GEN x)439 FF_to_FpXQ(GEN x)
440 {
441 switch(x[1])
442 {
443 case t_FF_FpXQ:
444 return ZX_copy(gel(x,2));
445 case t_FF_F2xq:
446 return F2x_to_ZX(gel(x,2));
447 default:
448 return Flx_to_ZX(gel(x,2));
449 }
450 }
451
452 GEN
FF_to_FpXQ_i(GEN x)453 FF_to_FpXQ_i(GEN x)
454 {
455 switch(x[1])
456 {
457 case t_FF_FpXQ:
458 return gel(x,2);
459 case t_FF_F2xq:
460 return F2x_to_ZX(gel(x,2));
461 default:
462 return Flx_to_ZX(gel(x,2));
463 }
464 }
465
466 GEN
FF_add(GEN x,GEN y)467 FF_add(GEN x, GEN y)
468 {
469 ulong pp;
470 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
471 _checkFF(x,y,"+");
472 switch(x[1])
473 {
474 case t_FF_FpXQ:
475 r=FpX_add(gel(x,2),gel(y,2),p);
476 break;
477 case t_FF_F2xq:
478 r=F2x_add(gel(x,2),gel(y,2));
479 break;
480 default:
481 r=Flx_add(gel(x,2),gel(y,2),pp);
482 }
483 return _mkFF(x,z,r);
484 }
485 GEN
FF_sub(GEN x,GEN y)486 FF_sub(GEN x, GEN y)
487 {
488 ulong pp;
489 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
490 _checkFF(x,y,"+");
491 switch(x[1])
492 {
493 case t_FF_FpXQ:
494 r=FpX_sub(gel(x,2),gel(y,2),p);
495 break;
496 case t_FF_F2xq:
497 r=F2x_add(gel(x,2),gel(y,2));
498 break;
499 default:
500 r=Flx_sub(gel(x,2),gel(y,2),pp);
501 }
502 return _mkFF(x,z,r);
503 }
504
505 GEN
FF_Z_add(GEN x,GEN y)506 FF_Z_add(GEN x, GEN y)
507 {
508 ulong pp;
509 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
510 switch(x[1])
511 {
512 case t_FF_FpXQ:
513 {
514 pari_sp av=avma;
515 r=gerepileupto(av,FpX_Fp_add(gel(x,2),modii(y,p),p));
516 break;
517 }
518 case t_FF_F2xq:
519 r=mpodd(y)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
520 break;
521 default:
522 r=Flx_Fl_add(gel(x,2),umodiu(y,pp),pp);
523 }
524 return _mkFF(x,z,r);
525 }
526
527 GEN
FF_Q_add(GEN x,GEN y)528 FF_Q_add(GEN x, GEN y)
529 {
530 ulong pp;
531 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
532 switch(x[1])
533 {
534 case t_FF_FpXQ:
535 {
536 pari_sp av=avma;
537 r=gerepileupto(av,FpX_Fp_add(gel(x,2),Rg_to_Fp(y,p),p));
538 break;
539 }
540 case t_FF_F2xq:
541 r=Rg_to_Fl(y,pp)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
542 break;
543 default:
544 r=Flx_Fl_add(gel(x,2),Rg_to_Fl(y,pp),pp);
545 }
546 return _mkFF(x,z,r);
547 }
548
549 GEN
FF_neg(GEN x)550 FF_neg(GEN x)
551 {
552 ulong pp;
553 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
554 switch(x[1])
555 {
556 case t_FF_FpXQ:
557 r=FpX_neg(gel(x,2),p);
558 break;
559 case t_FF_F2xq:
560 r=vecsmall_copy(gel(x,2));
561 break;
562 default:
563 r=Flx_neg(gel(x,2),pp);
564 }
565 return _mkFF(x,z,r);
566 }
567
568 GEN
FF_neg_i(GEN x)569 FF_neg_i(GEN x)
570 {
571 ulong pp;
572 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
573 switch(x[1])
574 {
575 case t_FF_FpXQ:
576 r=FpX_neg(gel(x,2),p);
577 break;
578 case t_FF_F2xq:
579 r=gel(x,2);
580 break;
581 default:
582 r=Flx_neg(gel(x,2),pp);
583 }
584 return _mkFF_i(x,z,r);
585 }
586
587 GEN
FF_map(GEN m,GEN x)588 FF_map(GEN m, GEN x)
589 {
590 ulong pp;
591 GEN r, T, p, z=_initFF(m,&T,&p,&pp);
592 switch(m[1])
593 {
594 case t_FF_FpXQ:
595 r=FpX_FpXQ_eval(gel(x,2),gel(m,2),T,p);
596 break;
597 case t_FF_F2xq:
598 r=F2x_F2xq_eval(gel(x,2),gel(m,2),T);
599 break;
600 default:
601 r=Flx_Flxq_eval(gel(x,2),gel(m,2),T,pp);
602 }
603 return _mkFF(m,z,r);
604 }
605
606 GEN
FF_Frobenius(GEN x,long e)607 FF_Frobenius(GEN x, long e)
608 {
609 ulong pp;
610 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
611 ulong n = umodsu(e, FF_f(x));
612 pari_sp av = avma;
613 if (n==0) return gcopy(x);
614 switch(x[1])
615 {
616 case t_FF_FpXQ:
617 r=FpX_Frobenius(T,p);
618 if (n>1) r=FpXQ_autpow(r,n,T,p);
619 break;
620 case t_FF_F2xq:
621 r=F2x_Frobenius(T);
622 if (n>1) r=F2xq_autpow(r,n,T);
623 break;
624 default:
625 r=Flx_Frobenius(T,pp);
626 if (n>1) r=Flxq_autpow(r,n,T,pp);
627 }
628 r = gerepileupto(av, r);
629 return _mkFF(x,z,r);
630 }
631
632 static GEN
FFX_preimage_i(GEN x,GEN y,GEN F,GEN T,GEN p,long pp)633 FFX_preimage_i(GEN x, GEN y, GEN F, GEN T, GEN p, long pp)
634 {
635 GEN r;
636 F = FFX_to_raw(F, y);
637 switch(y[1])
638 {
639 case t_FF_FpXQ:
640 r = FpXQX_rem(gel(x,2), F, T, p);
641 break;
642 case t_FF_F2xq:
643 r = F2xqX_rem(F2x_to_F2xX(gel(x,2),T[1]), F, T);
644 break;
645 default:
646 r = FlxqX_rem(Flx_to_FlxX(gel(x,2),T[1]), F, T, pp);
647 }
648 return r;
649 }
650
651 GEN
FFX_preimage(GEN x,GEN F,GEN y)652 FFX_preimage(GEN x, GEN F, GEN y)
653 {
654 GEN r, T, p, z;
655 ulong pp;
656 if (FF_equal0(x)) return FF_zero(y);
657 z = _initFF(y,&T,&p,&pp);
658 r = FFX_preimage_i(x, y, F, T, p, pp);
659 if (degpol(r) > 0) return NULL;
660 r = (y[1] == t_FF_FpXQ)? Fq_to_FpXQ(gel(r,2),T, p): gel(r,2);
661 return _mkFF(y,z,r);
662 }
663
664 GEN
FFX_preimagerel(GEN x,GEN F,GEN y)665 FFX_preimagerel(GEN x, GEN F, GEN y)
666 {
667 pari_sp av = avma;
668 GEN r, T, p;
669 ulong pp;
670 if (FF_equal0(x)) return FF_zero(y);
671 _getFF(y,&T,&p,&pp);
672 r = FFX_preimage_i(x, y, F, T, p, pp);
673 return gerepilecopy(av, raw_to_FFX(r, y));
674 }
675
676 GEN
FF_mul(GEN x,GEN y)677 FF_mul(GEN x, GEN y)
678 {
679 ulong pp;
680 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
681 pari_sp av=avma;
682 _checkFF(x,y,"*");
683 switch(x[1])
684 {
685 case t_FF_FpXQ:
686 r=FpXQ_mul(gel(x,2),gel(y,2),T,p);
687 break;
688 case t_FF_F2xq:
689 r=F2xq_mul(gel(x,2),gel(y,2),T);
690 break;
691 default:
692 r=Flxq_mul(gel(x,2),gel(y,2),T,pp);
693 }
694 return _mkFF(x,z,gerepileupto(av, r));
695 }
696
697 GEN
FF_Z_mul(GEN x,GEN y)698 FF_Z_mul(GEN x, GEN y)
699 {
700 ulong pp;
701 GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
702 switch(x[1])
703 {
704 case t_FF_FpXQ: /* modii(y,p) left on stack for efficiency */
705 r = FpX_Fp_mul(A, modii(y,p),p);
706 break;
707 case t_FF_F2xq:
708 r = mpodd(y)? vecsmall_copy(A): zero_Flx(A[1]);
709 break;
710 default:
711 r = Flx_Fl_mul(A, umodiu(y,pp), pp);
712 }
713 return _mkFF(x,z,r);
714 }
715
716 GEN
FF_Z_Z_muldiv(GEN x,GEN a,GEN b)717 FF_Z_Z_muldiv(GEN x, GEN a, GEN b)
718 {
719 ulong pp;
720 GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
721 switch(x[1])
722 {
723 case t_FF_FpXQ: /* Fp_div(a,b,p) left on stack for efficiency */
724 r = FpX_Fp_mul(A, Fp_div(a,b,p), p);
725 break;
726 case t_FF_F2xq:
727 if (!mpodd(b)) pari_err_INV("FF_Z_Z_muldiv", b);
728 r = mpodd(a)? vecsmall_copy(A): zero_Flx(A[1]);
729 break;
730 default:
731 r = Flx_Fl_mul(A, Fl_div(umodiu(a,pp),umodiu(b,pp),pp),pp);
732 }
733 return _mkFF(x,z,r);
734 }
735
736 GEN
FF_sqr(GEN x)737 FF_sqr(GEN x)
738 {
739 ulong pp;
740 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
741 switch(x[1])
742 {
743 case t_FF_FpXQ:
744 {
745 pari_sp av=avma;
746 r=gerepileupto(av,FpXQ_sqr(gel(x,2),T,p));
747 break;
748 }
749 case t_FF_F2xq:
750 r=F2xq_sqr(gel(x,2),T);
751 break;
752 default:
753 r=Flxq_sqr(gel(x,2),T,pp);
754 }
755 return _mkFF(x,z,r);
756 }
757
758 GEN
FF_mul2n(GEN x,long n)759 FF_mul2n(GEN x, long n)
760 {
761 ulong pp;
762 GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
763 switch(x[1])
764 {
765 case t_FF_FpXQ:
766 {
767 GEN p1; /* left on stack for efficiency */
768 if (n>0) p1=remii(int2n(n),p);
769 else p1=Fp_inv(remii(int2n(-n),p),p);
770 r = FpX_Fp_mul(A, p1, p);
771 }
772 break;
773 case t_FF_F2xq:
774 if (n<0) pari_err_INV("FF_mul2n", gen_2);
775 r = n==0? vecsmall_copy(A): zero_Flx(A[1]);
776 break;
777 default:
778 {
779 ulong l1;
780 if (n>0) l1 = umodiu(int2n(n),pp);
781 else l1 = Fl_inv(umodiu(int2n(-n),pp),pp);
782 r = Flx_Fl_mul(A,l1,pp);
783 }
784 }
785 return _mkFF(x,z,r);
786 }
787
788 GEN
FF_inv(GEN x)789 FF_inv(GEN x)
790 {
791 ulong pp;
792 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
793 pari_sp av=avma;
794 switch(x[1])
795 {
796 case t_FF_FpXQ:
797 r=gerepileupto(av,FpXQ_inv(gel(x,2),T,p));
798 break;
799 case t_FF_F2xq:
800 r=F2xq_inv(gel(x,2),T);
801 break;
802 default:
803 r=Flxq_inv(gel(x,2),T,pp);
804 }
805 return _mkFF(x,z,r);
806 }
807
808 GEN
FF_div(GEN x,GEN y)809 FF_div(GEN x, GEN y)
810 {
811 ulong pp;
812 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
813 pari_sp av=avma;
814 _checkFF(x,y,"/");
815 switch(x[1])
816 {
817 case t_FF_FpXQ:
818 r=gerepileupto(av,FpXQ_div(gel(x,2),gel(y,2),T,p));
819 break;
820 case t_FF_F2xq:
821 r=gerepileupto(av,F2xq_div(gel(x,2),gel(y,2),T));
822 break;
823 default:
824 r=gerepileupto(av,Flxq_div(gel(x,2),gel(y,2),T,pp));
825 }
826 return _mkFF(x,z,r);
827 }
828
829 GEN
Z_FF_div(GEN n,GEN x)830 Z_FF_div(GEN n, GEN x)
831 {
832 ulong pp;
833 GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
834 pari_sp av=avma;
835 switch(x[1])
836 {
837 case t_FF_FpXQ:
838 r = gerepileupto(av,FpX_Fp_mul(FpXQ_inv(A,T,p),modii(n,p),p));
839 break;
840 case t_FF_F2xq:
841 r = F2xq_inv(A,T); /*Check for division by 0*/
842 if(!mpodd(n)) { set_avma(av); r = zero_Flx(A[1]); }
843 break;
844 default:
845 r = gerepileupto(av, Flx_Fl_mul(Flxq_inv(A,T,pp),umodiu(n,pp),pp));
846 }
847 return _mkFF(x,z,r);
848 }
849
850 GEN
FF_sqrtn(GEN x,GEN n,GEN * zetan)851 FF_sqrtn(GEN x, GEN n, GEN *zetan)
852 {
853 ulong pp;
854 GEN r, T, p, y=_initFF(x,&T,&p,&pp);
855 switch (x[1])
856 {
857 case t_FF_FpXQ:
858 r=FpXQ_sqrtn(gel(x,2),n,T,p,zetan);
859 break;
860 case t_FF_F2xq:
861 r=F2xq_sqrtn(gel(x,2),n,T,zetan);
862 break;
863 default:
864 r=Flxq_sqrtn(gel(x,2),n,T,pp,zetan);
865 }
866 if (!r) pari_err_SQRTN("FF_sqrtn",x);
867 (void)_mkFF(x, y, r);
868 if (zetan)
869 {
870 GEN z = cgetg(lg(y),t_FFELT);
871 *zetan=_mkFF(x, z, *zetan);
872 }
873 return y;
874 }
875
876 GEN
FF_sqrt(GEN x)877 FF_sqrt(GEN x)
878 {
879 ulong pp;
880 GEN r, T, p, y=_initFF(x,&T,&p,&pp);
881 switch (x[1])
882 {
883 case t_FF_FpXQ:
884 r = FpXQ_sqrt(gel(x,2),T,p);
885 break;
886 case t_FF_F2xq:
887 r = F2xq_sqrt(gel(x,2),T);
888 break;
889 default:
890 r = Flxq_sqrt(gel(x,2),T,pp);
891 }
892 if (!r) pari_err_SQRTN("FF_sqrt",x);
893 return _mkFF(x, y, r);
894 }
895
896 long
FF_issquare(GEN x)897 FF_issquare(GEN x)
898 {
899 GEN T, p;
900 ulong pp;
901 _getFF(x, &T, &p, &pp);
902 switch(x[1])
903 {
904 case t_FF_FpXQ:
905 return FpXQ_issquare(gel(x,2), T, p);
906 case t_FF_F2xq:
907 return 1;
908 default: /* case t_FF_Flxq: */
909 return Flxq_issquare(gel(x,2), T, pp);
910 }
911 }
912
913 long
FF_issquareall(GEN x,GEN * pt)914 FF_issquareall(GEN x, GEN *pt)
915 {
916 if (!pt) return FF_issquare(x);
917 return FF_ispower(x, gen_2, pt);
918 }
919
920 long
FF_ispower(GEN x,GEN K,GEN * pt)921 FF_ispower(GEN x, GEN K, GEN *pt)
922 {
923 ulong pp;
924 GEN z, r, T, p;
925 pari_sp av = avma;
926
927 if (FF_equal0(x)) { if (pt) *pt = gcopy(x); return 1; }
928 _getFF(x, &T, &p, &pp);
929 z = pt? cgetg(5,t_FFELT): NULL;
930 switch(x[1])
931 {
932 case t_FF_FpXQ:
933 r = FpXQ_sqrtn(gel(x,2),K,T,p,NULL);
934 break;
935 case t_FF_F2xq:
936 r = F2xq_sqrtn(gel(x,2),K,T,NULL);
937 break;
938 default: /* case t_FF_Flxq: */
939 r = Flxq_sqrtn(gel(x,2),K,T,pp,NULL);
940 break;
941 }
942 if (!r) return gc_long(av,0);
943 if (pt) { *pt = z; (void)_mkFF(x,z,r); }
944 return 1;
945 }
946
947 GEN
FF_pow(GEN x,GEN n)948 FF_pow(GEN x, GEN n)
949 {
950 ulong pp;
951 GEN r, T, p, z=_initFF(x,&T,&p,&pp);
952 switch(x[1])
953 {
954 case t_FF_FpXQ:
955 r = FpXQ_pow(gel(x,2), n, T, p);
956 break;
957 case t_FF_F2xq:
958 r = F2xq_pow(gel(x,2), n, T);
959 break;
960 default:
961 r = Flxq_pow(gel(x,2), n, T, pp);
962 }
963 return _mkFF(x,z,r);
964 }
965
966 GEN
FF_norm(GEN x)967 FF_norm(GEN x)
968 {
969 ulong pp;
970 GEN T,p;
971 _getFF(x,&T,&p,&pp);
972 switch (x[1])
973 {
974 case t_FF_FpXQ:
975 return FpXQ_norm(gel(x,2),T,p);
976 case t_FF_F2xq:
977 return lgpol(gel(x,2))?gen_1:gen_0;
978 default:
979 return utoi(Flxq_norm(gel(x,2),T,pp));
980 }
981 }
982
983 GEN
FF_trace(GEN x)984 FF_trace(GEN x)
985 {
986 ulong pp;
987 GEN T,p;
988 _getFF(x,&T,&p,&pp);
989 switch(x[1])
990 {
991 case t_FF_FpXQ:
992 return FpXQ_trace(gel(x,2),T,p);
993 case t_FF_F2xq:
994 return F2xq_trace(gel(x,2),T)?gen_1:gen_0;
995 default:
996 return utoi(Flxq_trace(gel(x,2),T,pp));
997 }
998 }
999
1000 GEN
FF_conjvec(GEN x)1001 FF_conjvec(GEN x)
1002 {
1003 ulong pp;
1004 GEN r,T,p,v;
1005 long i,l;
1006 pari_sp av;
1007 _getFF(x,&T,&p,&pp);
1008 av = avma;
1009 switch(x[1])
1010 {
1011 case t_FF_FpXQ:
1012 v = FpXQ_conjvec(gel(x,2), T, p);
1013 break;
1014 case t_FF_F2xq:
1015 v = F2xq_conjvec(gel(x,2), T);
1016 break;
1017 default:
1018 v = Flxq_conjvec(gel(x,2), T, pp);
1019 }
1020 l = lg(v); r = cgetg(l, t_COL);
1021 for(i=1; i<l; i++)
1022 gel(r,i) = mkFF_i(x, gel(v,i));
1023 return gerepilecopy(av, r);
1024 }
1025
1026 GEN
FF_charpoly(GEN x)1027 FF_charpoly(GEN x)
1028 {
1029 ulong pp;
1030 GEN T,p;
1031 pari_sp av=avma;
1032 _getFF(x,&T,&p,&pp);
1033 switch(x[1])
1034 {
1035 case t_FF_FpXQ:
1036 return gerepileupto(av,FpXQ_charpoly(gel(x,2), T, p));
1037 case t_FF_F2xq:
1038 return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(F2x_to_Flx(gel(x,2)),
1039 F2x_to_Flx(T), 2UL)));
1040 default:
1041 return gerepileupto(av,Flx_to_ZX(Flxq_charpoly(gel(x,2), T, pp)));
1042 }
1043 }
1044
1045 GEN
FF_minpoly(GEN x)1046 FF_minpoly(GEN x)
1047 {
1048 ulong pp;
1049 GEN T,p;
1050 pari_sp av=avma;
1051 _getFF(x,&T,&p,&pp);
1052 switch(x[1])
1053 {
1054 case t_FF_FpXQ:
1055 return gerepileupto(av,FpXQ_minpoly(gel(x,2), T, p));
1056 case t_FF_F2xq:
1057 return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(F2x_to_Flx(gel(x,2)),
1058 F2x_to_Flx(T), 2UL)));
1059 default:
1060 return gerepileupto(av,Flx_to_ZX(Flxq_minpoly(gel(x,2), T, pp)));
1061 }
1062 }
1063
1064 GEN
FF_log(GEN x,GEN g,GEN ord)1065 FF_log(GEN x, GEN g, GEN ord)
1066 {
1067 pari_sp av=avma;
1068 ulong pp;
1069 GEN r, T, p;
1070 _getFF(x,&T,&p,&pp);
1071 _checkFF(x,g,"log");
1072 switch(x[1])
1073 {
1074 case t_FF_FpXQ:
1075 if (!ord) ord = factor_pn_1(p,degpol(T));
1076 r = FpXQ_log(gel(x,2), gel(g,2), ord, T, p);
1077 break;
1078 case t_FF_F2xq:
1079 if (!ord) ord = factor_pn_1(gen_2,F2x_degree(T));
1080 r = F2xq_log(gel(x,2), gel(g,2), ord, T);
1081 break;
1082 default:
1083 if (!ord) ord = factor_pn_1(p,degpol(T));
1084 r = Flxq_log(gel(x,2), gel(g,2), ord, T, pp);
1085 }
1086 return gerepileupto(av, r);
1087 }
1088
1089 GEN
FF_order(GEN x,GEN o)1090 FF_order(GEN x, GEN o)
1091 {
1092 pari_sp av=avma;
1093 ulong pp;
1094 GEN r, T,p;
1095 _getFF(x,&T,&p,&pp);
1096 switch(x[1])
1097 {
1098 case t_FF_FpXQ:
1099 if (!o) o = factor_pn_1(p,degpol(T));
1100 r = FpXQ_order(gel(x,2), o, T, p);
1101 break;
1102 case t_FF_F2xq:
1103 if (!o) o = factor_pn_1(gen_2,F2x_degree(T));
1104 r = F2xq_order(gel(x,2), o, T);
1105 break;
1106 default:
1107 if (!o) o = factor_pn_1(p,degpol(T));
1108 r = Flxq_order(gel(x,2), o, T, pp);
1109 }
1110 if (!o) r = gerepileuptoint(av,r);
1111 return r;
1112 }
1113
1114 GEN
FF_primroot(GEN x,GEN * o)1115 FF_primroot(GEN x, GEN *o)
1116 {
1117 ulong pp;
1118 GEN r,T,p,z=_initFF(x,&T,&p,&pp);
1119 switch(x[1])
1120 {
1121 case t_FF_FpXQ:
1122 r = gener_FpXQ(T, p, o);
1123 break;
1124 case t_FF_F2xq:
1125 r = gener_F2xq(T, o);
1126 break;
1127 default:
1128 r = gener_Flxq(T, pp, o);
1129 }
1130 return _mkFF(x,z,r);
1131 }
1132
1133 static GEN
to_FFE(GEN P,GEN fg)1134 to_FFE(GEN P, GEN fg)
1135 {
1136 if(ell_is_inf(P))
1137 return ellinf();
1138 else
1139 retmkvec2(mkFF_i(fg,gel(P,1)), mkFF_i(fg,gel(P,2)));
1140 }
1141
1142 static GEN
to_FFE_vec(GEN x,GEN ff)1143 to_FFE_vec(GEN x, GEN ff)
1144 {
1145 long i, lx = lg(x);
1146 for (i=1; i<lx; i++) gel(x,i) = to_FFE(gel(x,i), ff);
1147 return x;
1148 }
1149
1150 static GEN
FpXQ_ell_to_a4a6(GEN E,GEN T,GEN p)1151 FpXQ_ell_to_a4a6(GEN E, GEN T, GEN p)
1152 {
1153 GEN a1, a3, b2, c4, c6;
1154 a1 = Rg_to_FpXQ(ell_get_a1(E),T,p);
1155 a3 = Rg_to_FpXQ(ell_get_a3(E),T,p);
1156 b2 = Rg_to_FpXQ(ell_get_b2(E),T,p);
1157 c4 = Rg_to_FpXQ(ell_get_c4(E),T,p);
1158 c6 = Rg_to_FpXQ(ell_get_c6(E),T,p);
1159 retmkvec3(FpX_neg(FpX_mulu(c4, 27, p), p), FpX_neg(FpX_mulu(c6, 54, p), p),
1160 mkvec4(Z_to_FpX(utoi(6),p,varn(T)),FpX_mulu(b2,3,p),
1161 FpX_mulu(a1,3,p),FpX_mulu(a3,108,p)));
1162 }
1163
1164 static GEN
F3xq_ell_to_a4a6(GEN E,GEN T)1165 F3xq_ell_to_a4a6(GEN E, GEN T)
1166 {
1167 GEN a1, a3, b2, b4, b6;
1168 a1 = Rg_to_Flxq(ell_get_a1(E),T,3);
1169 a3 = Rg_to_Flxq(ell_get_a3(E),T,3);
1170 b2 = Rg_to_Flxq(ell_get_b2(E),T,3);
1171 b4 = Rg_to_Flxq(ell_get_b4(E),T,3);
1172 b6 = Rg_to_Flxq(ell_get_b6(E),T,3);
1173 if(lgpol(b2)) /* ordinary case */
1174 {
1175 GEN b4b2 = Flxq_div(b4,b2,T,3);
1176 GEN a6 = Flx_sub(b6,Flxq_mul(b4b2,Flx_add(b4,Flxq_sqr(b4b2,T,3),3),T,3),3);
1177 retmkvec3(mkvec(b2), a6,
1178 mkvec4(Fl_to_Flx(1,T[1]),b4b2,Flx_neg(a1,3),Flx_neg(a3,3)));
1179 }
1180 else /* super-singular case */
1181 retmkvec3(Flx_neg(b4, 3), b6,
1182 mkvec4(Fl_to_Flx(1,T[1]),zero_Flx(T[1]), Flx_neg(a1,3), Flx_neg(a3,3)));
1183 }
1184
1185 static GEN
Flxq_ell_to_a4a6(GEN E,GEN T,ulong p)1186 Flxq_ell_to_a4a6(GEN E, GEN T, ulong p)
1187 {
1188 GEN a1, a3, b2, c4, c6;
1189 if(p==3) return F3xq_ell_to_a4a6(E, T);
1190 a1 = Rg_to_Flxq(ell_get_a1(E),T,p);
1191 a3 = Rg_to_Flxq(ell_get_a3(E),T,p);
1192 b2 = Rg_to_Flxq(ell_get_b2(E),T,p);
1193 c4 = Rg_to_Flxq(ell_get_c4(E),T,p);
1194 c6 = Rg_to_Flxq(ell_get_c6(E),T,p);
1195 retmkvec3(Flx_neg(Flx_mulu(c4, 27, p), p), Flx_neg(Flx_mulu(c6, 54, p), p),
1196 mkvec4(Fl_to_Flx(6%p,T[1]),Flx_mulu(b2,3,p),
1197 Flx_mulu(a1,3,p),Flx_mulu(a3,108,p)));
1198 }
1199
1200 static GEN
F2xq_ell_to_a4a6(GEN E,GEN T)1201 F2xq_ell_to_a4a6(GEN E, GEN T)
1202 {
1203 long v = T[1];
1204 GEN a1 = Rg_to_F2xq(ell_get_a1(E),T);
1205 GEN a2 = Rg_to_F2xq(ell_get_a2(E),T);
1206 GEN a3 = Rg_to_F2xq(ell_get_a3(E),T);
1207 GEN a4 = Rg_to_F2xq(ell_get_a4(E),T);
1208 GEN a6 = Rg_to_F2xq(ell_get_a6(E),T);
1209 if (lgpol(a1))
1210 {
1211 GEN a1i = F2xq_inv(a1,T);
1212 GEN a1i2 = F2xq_sqr(a1i,T);
1213 GEN a1i3 = F2xq_mul(a1i,a1i2,T);
1214 GEN a1i6 = F2xq_sqr(a1i3,T);
1215 GEN d = F2xq_mul(a3,a1i,T);
1216 GEN dd = F2xq_mul(d,a1i2,T);
1217 GEN e = F2xq_mul(F2x_add(a4,F2xq_sqr(d,T)),a1i,T);
1218 GEN ee = F2xq_mul(e,a1i3,T);
1219 GEN da2 = F2x_add(a2,d);
1220 GEN d2 = F2xq_mul(da2,a1i2,T);
1221 GEN d6 = F2xq_mul(F2x_add(F2x_add(F2xq_mul(F2x_add(F2xq_mul(da2,d,T),a4),d,T),a6),F2xq_sqr(e,T)),a1i6,T);
1222 retmkvec3(d2, d6, mkvec4(a1i,dd,pol0_F2x(v),ee));
1223 }
1224 else
1225 { /* allow a1 = a3 = 0: singular curve */
1226 GEN d4 = F2x_add(F2xq_sqr(a2,T),a4);
1227 GEN d6 = F2x_add(F2xq_mul(a2,a4,T),a6);
1228 GEN a3i = lgpol(a3)? F2xq_inv(a3,T): a3;
1229 retmkvec3(mkvec3(a3,d4,a3i), d6, mkvec4(pol1_F2x(v),a2,pol0_F2x(T[1]),pol0_F2x(T[1])));
1230 }
1231 }
1232
1233 static GEN
FqV_to_FpXQV(GEN x,GEN T)1234 FqV_to_FpXQV(GEN x, GEN T)
1235 {
1236 pari_sp av = avma;
1237 long v = varn(T), i, s=0, l = lg(x);
1238 GEN y = shallowcopy(x);
1239 for(i=1; i<l; i++)
1240 if (typ(gel(x,i))==t_INT)
1241 {
1242 gel(y,i) = scalarpol(gel(x,i), v);
1243 s = 1;
1244 }
1245 if (!s) { set_avma(av); return x; }
1246 return y;
1247 }
1248
1249 GEN
FF_ellcard(GEN E)1250 FF_ellcard(GEN E)
1251 {
1252 GEN T,p;
1253 ulong pp;
1254 GEN e = ellff_get_a4a6(E);
1255 GEN fg = ellff_get_field(E);
1256 _getFF(fg,&T,&p,&pp);
1257 switch(fg[1])
1258 {
1259 case t_FF_FpXQ:
1260 return FpXQ_ellcard(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p),T,p);
1261 case t_FF_F2xq:
1262 return F2xq_ellcard(gel(e,1),gel(e,2),T);
1263 default:
1264 return Flxq_ellcard(gel(e,1),gel(e,2),T,pp);
1265 }
1266 }
1267
1268 GEN
FF_ellcard_SEA(GEN E,long smallfact)1269 FF_ellcard_SEA(GEN E, long smallfact)
1270 {
1271 pari_sp av = avma;
1272 GEN T,p;
1273 ulong pp;
1274 GEN e = ellff_get_a4a6(E), a4, a6, card;
1275 GEN fg = ellff_get_field(E);
1276 _getFF(fg,&T,&p,&pp);
1277 switch(fg[1])
1278 {
1279 case t_FF_FpXQ:
1280 a4 = Fq_to_FpXQ(gel(e,1), T, p);
1281 a6 = Fq_to_FpXQ(gel(e,2), T, p);
1282 card = Fq_ellcard_SEA(a4, a6, powiu(p,degpol(T)), T,p, smallfact);
1283 break;
1284 case t_FF_F2xq:
1285 pari_err_IMPL("SEA for char 2");
1286 default:
1287 a4 = Flx_to_ZX(gel(e,1));
1288 a6 = Flx_to_ZX(gel(e,2));
1289 card = Fq_ellcard_SEA(a4, a6, powuu(pp,degpol(T)), Flx_to_ZX(T), p, smallfact);
1290 }
1291 return gerepileuptoint(av, card);
1292 }
1293
1294 /* return G, set m */
1295 GEN
FF_ellgroup(GEN E,GEN * pm)1296 FF_ellgroup(GEN E, GEN *pm)
1297 {
1298 GEN T, p, e, fg, N;
1299 ulong pp;
1300
1301 N = ellff_get_card(E);
1302 e = ellff_get_a4a6(E);
1303 fg = ellff_get_field(E);
1304 _getFF(fg,&T,&p,&pp);
1305 switch(fg[1])
1306 {
1307 case t_FF_FpXQ:
1308 return FpXQ_ellgroup(Fq_to_FpXQ(gel(e,1),T,p),
1309 Fq_to_FpXQ(gel(e,2),T,p),N,T,p,pm);
1310 case t_FF_F2xq:
1311 return F2xq_ellgroup(gel(e,1),gel(e,2),N,T,pm);
1312 default:
1313 return Flxq_ellgroup(gel(e,1),gel(e,2),N,T,pp,pm);
1314 }
1315 }
1316
1317 GEN
FF_ellgens(GEN E)1318 FF_ellgens(GEN E)
1319 {
1320 GEN D, fg, e, m, T, p, F, e3;
1321 ulong pp;
1322
1323 fg = ellff_get_field(E);
1324 e = ellff_get_a4a6(E);
1325 m = ellff_get_m(E);
1326 D = ellff_get_D(E);
1327 _getFF(fg,&T,&p,&pp);
1328 switch(fg[1])
1329 {
1330 case t_FF_FpXQ:
1331 e3 = FqV_to_FpXQV(gel(e,3),T);
1332 F = FpXQ_ellgens(Fq_to_FpXQ(gel(e,1),T,p),Fq_to_FpXQ(gel(e,2),T,p),e3,D,m,T,p);
1333 break;
1334 case t_FF_F2xq:
1335 F = F2xq_ellgens(gel(e,1),gel(e,2),gel(e,3),D,m,T);
1336 break;
1337 default:
1338 F = Flxq_ellgens(gel(e,1),gel(e,2),gel(e,3),D,m,T, pp);
1339 break;
1340 }
1341 return to_FFE_vec(F,fg);
1342 }
1343
1344 GEN
FF_elldata(GEN E,GEN fg)1345 FF_elldata(GEN E, GEN fg)
1346 {
1347 GEN T,p,e;
1348 ulong pp;
1349 _getFF(fg,&T,&p,&pp);
1350 switch(fg[1])
1351 {
1352 case t_FF_FpXQ:
1353 e = FpXQ_ell_to_a4a6(E,T,p); break;
1354 case t_FF_F2xq:
1355 e = F2xq_ell_to_a4a6(E,T); break;
1356 default:
1357 e = Flxq_ell_to_a4a6(E,T,pp); break;
1358 }
1359 return mkvec2(fg,e);
1360 }
1361
1362 /* allow singular E, set E.j = 0 in this case */
1363 GEN
FF_ellinit(GEN E,GEN fg)1364 FF_ellinit(GEN E, GEN fg)
1365 {
1366 GEN T,p,e, D, c4, y = E;
1367 ulong pp;
1368 long i;
1369 _getFF(fg,&T,&p,&pp);
1370 switch(fg[1])
1371 {
1372 case t_FF_FpXQ:
1373 e = FpXQ_ell_to_a4a6(E,T,p);
1374 for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_FpXQ(gel(E,i),T,p));
1375 break;
1376 case t_FF_F2xq:
1377 e = F2xq_ell_to_a4a6(E,T);
1378 for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_F2xq(gel(E,i),T));
1379 break;
1380 default:
1381 e = Flxq_ell_to_a4a6(E,T,pp);
1382 for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_Flxq(gel(E,i),T,pp));
1383 break;
1384 }
1385 D = ell_get_disc(y);
1386 c4 = ell_get_c4(y);
1387 gel(y,13) = FF_equal0(D)? D: gdiv(gpowgs(c4,3), D);
1388 gel(y,14) = mkvecsmall(t_ELL_Fq);
1389 gel(y,15) = mkvec2(fg,e);
1390 return y;
1391 }
1392
1393 GEN
FF_elltwist(GEN E)1394 FF_elltwist(GEN E)
1395 {
1396 pari_sp av = avma;
1397 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1398 GEN T, p, a, a6, V;
1399 ulong pp;
1400 _getFF(fg,&T,&p,&pp);
1401 switch (fg[1])
1402 {
1403 case t_FF_FpXQ:
1404 FpXQ_elltwist(gel(e,1), gel(e,2), T, p, &a, &a6);
1405 V = mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6));
1406 break;
1407 case t_FF_F2xq:
1408 F2xq_elltwist(gel(e,1), gel(e,2), T, &a, &a6);
1409 V = typ(a)==t_VECSMALL ?
1410 mkvec5(gen_1, mkFF_i(fg, a), gen_0, gen_0, mkFF_i(fg, a6)):
1411 mkvec5(gen_0, gen_0, mkFF_i(fg, gel(a,1)), mkFF_i(fg, gel(a,2)), mkFF_i(fg, a6));
1412 break;
1413 default:
1414 Flxq_elltwist(gel(e,1), gel(e,2), T, pp, &a, &a6);
1415 V = typ(a)==t_VECSMALL ?
1416 mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6)):
1417 mkvec5(gen_0, mkFF_i(fg, gel(a,1)), gen_0, gen_0, mkFF_i(fg, a6));
1418 }
1419 return gerepilecopy(av, V);
1420 }
1421
1422 static long
F3x_equalm1(GEN x)1423 F3x_equalm1(GEN x) { return degpol(x)==0 && x[2] == 2; }
1424 GEN
FF_ellrandom(GEN E)1425 FF_ellrandom(GEN E)
1426 {
1427 pari_sp av = avma;
1428 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
1429 GEN T,p;
1430 ulong pp;
1431 _getFF(fg,&T,&p,&pp);
1432 switch (fg[1])
1433 {
1434 case t_FF_FpXQ:
1435 Q = random_FpXQE(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p), T, p);
1436 Q = FpXQE_changepoint(Q, FqV_to_FpXQV(gel(e,3), T) , T, p);
1437 break;
1438 case t_FF_F2xq:
1439 {
1440 long d = F2x_degree(T);
1441 /* if #E(Fq) = 1 return [0] */
1442 if (d<=2 && typ(gel(e,1)) == t_VEC)
1443 { /* over F2 or F4, supersingular */
1444 GEN v = gel(e,1), A6 = gel(e,2), a3 = gel(v,1), A4 = gel(v,2);
1445 if (F2x_equal1(a3) &&
1446 ((d==1 && F2x_equal1(A4) && F2x_equal1(A6))
1447 || (d==2 && !lgpol(A4) && F2x_degree(A6)==1))) return ellinf();
1448 }
1449 Q = random_F2xqE(gel(e,1), gel(e,2), T);
1450 Q = F2xqE_changepoint(Q, gel(e,3), T);
1451 break;
1452 }
1453 default:
1454 /* if #E(Fq) = 1 return [0] */
1455 if (pp==3 && degpol(T)==1 && typ(gel(e,1))==t_VECSMALL)
1456 { /* over F3, supersingular */
1457 GEN mb4 = gel(e,1), b6 = gel(e,2);
1458 if (F3x_equalm1(mb4) && F3x_equalm1(b6)) return ellinf();
1459 }
1460 Q = random_FlxqE(gel(e,1), gel(e,2), T, pp);
1461 Q = FlxqE_changepoint(Q, gel(e,3), T, pp);
1462 }
1463 return gerepilecopy(av, to_FFE(Q, fg));
1464 }
1465
1466 GEN
FF_ellmul(GEN E,GEN P,GEN n)1467 FF_ellmul(GEN E, GEN P, GEN n)
1468 {
1469 pari_sp av = avma;
1470 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
1471 GEN T,p, Pp, Qp, e3;
1472 ulong pp;
1473 _getFF(fg,&T,&p,&pp);
1474 switch (fg[1])
1475 {
1476 case t_FF_FpXQ:
1477 e3 = FqV_to_FpXQV(gel(e,3),T);
1478 Pp = FpXQE_changepointinv(RgE_to_FpXQE(P, T, p), e3, T, p);
1479 Qp = FpXQE_mul(Pp, n, gel(e,1), T, p);
1480 Q = FpXQE_changepoint(Qp, gel(e,3), T, p);
1481 break;
1482 case t_FF_F2xq:
1483 Pp = F2xqE_changepointinv(RgE_to_F2xqE(P, T), gel(e,3), T);
1484 Qp = F2xqE_mul(Pp, n, gel(e,1), T);
1485 Q = F2xqE_changepoint(Qp, gel(e,3), T);
1486 break;
1487 default:
1488 Pp = FlxqE_changepointinv(RgE_to_FlxqE(P, T, pp), gel(e,3), T, pp);
1489 Qp = FlxqE_mul(Pp, n, gel(e,1), T, pp);
1490 Q = FlxqE_changepoint(Qp, gel(e,3), T, pp);
1491 }
1492 return gerepilecopy(av, to_FFE(Q, fg));
1493 }
1494
1495 GEN
FF_ellorder(GEN E,GEN P,GEN o)1496 FF_ellorder(GEN E, GEN P, GEN o)
1497 {
1498 pari_sp av = avma;
1499 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1500 GEN r,T,p,Pp,e3;
1501 ulong pp;
1502 _getFF(fg,&T,&p,&pp);
1503 switch (fg[1])
1504 {
1505 case t_FF_FpXQ:
1506 e3 = FqV_to_FpXQV(gel(e,3),T);
1507 Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1508 r = FpXQE_order(Pp, o, gel(e,1), T, p);
1509 break;
1510 case t_FF_F2xq:
1511 Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1512 r = F2xqE_order(Pp, o, gel(e,1), T);
1513 break;
1514 default:
1515 Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1516 r = FlxqE_order(Pp, o, gel(e,1), T, pp);
1517 }
1518 return gerepileupto(av, r);
1519 }
1520
1521 GEN
FF_elllog(GEN E,GEN P,GEN Q,GEN o)1522 FF_elllog(GEN E, GEN P, GEN Q, GEN o)
1523 {
1524 pari_sp av = avma;
1525 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1526 GEN r,T,p, Pp,Qp, e3;
1527 ulong pp;
1528 _getFF(fg,&T,&p,&pp);
1529 switch(fg[1])
1530 {
1531 case t_FF_FpXQ:
1532 e3 = FqV_to_FpXQV(gel(e,3),T);
1533 Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1534 Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1535 r = FpXQE_log(Pp, Qp, o, gel(e,1), T, p);
1536 break;
1537 case t_FF_F2xq:
1538 Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1539 Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1540 r = F2xqE_log(Pp, Qp, o, gel(e,1), T);
1541 break;
1542 default:
1543 Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1544 Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1545 r = FlxqE_log(Pp, Qp, o, gel(e,1), T, pp);
1546 }
1547 return gerepileupto(av, r);
1548 }
1549
1550 GEN
FF_ellweilpairing(GEN E,GEN P,GEN Q,GEN m)1551 FF_ellweilpairing(GEN E, GEN P, GEN Q, GEN m)
1552 {
1553 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1554 GEN r,T,p, Pp,Qp, e3;
1555 ulong pp;
1556 GEN z=_initFF(fg,&T,&p,&pp);
1557 pari_sp av = avma;
1558 switch(fg[1])
1559 {
1560 case t_FF_FpXQ:
1561 e3 = FqV_to_FpXQV(gel(e,3),T);
1562 Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1563 Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1564 r = FpXQE_weilpairing(Pp, Qp, m, gel(e,1), T, p);
1565 break;
1566 case t_FF_F2xq:
1567 Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1568 Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1569 r = F2xqE_weilpairing(Pp, Qp, m, gel(e,1), T);
1570 break;
1571 default:
1572 Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1573 Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1574 r = FlxqE_weilpairing(Pp, Qp, m, gel(e,1), T, pp);
1575 }
1576 r = gerepileupto(av, r);
1577 return _mkFF(fg,z,r);
1578 }
1579
1580 GEN
FF_elltatepairing(GEN E,GEN P,GEN Q,GEN m)1581 FF_elltatepairing(GEN E, GEN P, GEN Q, GEN m)
1582 {
1583 GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1584 GEN r,T,p, Pp,Qp, e3;
1585 ulong pp;
1586 GEN z=_initFF(fg,&T,&p,&pp);
1587 pari_sp av = avma;
1588 switch(fg[1])
1589 {
1590 case t_FF_FpXQ:
1591 e3 = FqV_to_FpXQV(gel(e,3),T);
1592 Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1593 Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1594 r = FpXQE_tatepairing(Pp, Qp, m, gel(e,1), T, p);
1595 break;
1596 case t_FF_F2xq:
1597 Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1598 Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1599 r = F2xqE_tatepairing(Pp, Qp, m, gel(e,1), T);
1600 break;
1601 default:
1602 Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1603 Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1604 r = FlxqE_tatepairing(Pp, Qp, m, gel(e,1), T, pp);
1605 }
1606 r = gerepileupto(av, r);
1607 return _mkFF(fg,z,r);
1608 }
1609
1610 GEN
FFX_roots(GEN Pf,GEN ff)1611 FFX_roots(GEN Pf, GEN ff)
1612 {
1613 pari_sp av = avma;
1614 GEN r,T,p;
1615 ulong pp;
1616 GEN P = FFX_to_raw(Pf, ff);
1617 _getFF(ff,&T,&p,&pp);
1618 switch(ff[1])
1619 {
1620 case t_FF_FpXQ:
1621 r = FpXQX_roots(P, T, p);
1622 break;
1623 case t_FF_F2xq:
1624 r = F2xqX_roots(P, T);
1625 break;
1626 default:
1627 r = FlxqX_roots(P, T, pp);
1628 }
1629 return gerepilecopy(av, raw_to_FFC(r, ff));
1630 }
1631
1632 static GEN
raw_to_FFXC(GEN x,GEN ff)1633 raw_to_FFXC(GEN x, GEN ff) { pari_APPLY_type(t_COL, raw_to_FFX(gel(x,i), ff)); }
1634 static GEN
raw_to_FFXM(GEN x,GEN ff)1635 raw_to_FFXM(GEN x, GEN ff) { pari_APPLY_same(raw_to_FFXC(gel(x,i), ff)); }
1636 static GEN
raw_to_FFX_fact(GEN F,GEN ff)1637 raw_to_FFX_fact(GEN F, GEN ff)
1638 {
1639 GEN y, u, v;
1640 GEN P = gel(F,1), E = gel(F,2);
1641 long j, l = lg(P);
1642 y = cgetg(3,t_MAT);
1643 u = cgetg(l,t_COL); gel(y,1) = u;
1644 v = cgetg(l,t_COL); gel(y,2) = v;
1645 for (j=1; j<l; j++)
1646 {
1647 gel(u,j) = raw_to_FFX(gel(P,j), ff);
1648 gel(v,j) = utoi(uel(E,j));
1649 }
1650 return y;
1651 }
1652
1653 static GEN
FFX_zero(GEN ff,long v)1654 FFX_zero(GEN ff, long v)
1655 {
1656 GEN r = cgetg(3,t_POL);
1657 r[1] = evalvarn(v);
1658 gel(r,2) = FF_zero(ff);
1659 return r;
1660 }
1661
1662 GEN
FFX_add(GEN Pf,GEN Qf,GEN ff)1663 FFX_add(GEN Pf, GEN Qf, GEN ff)
1664 {
1665 pari_sp av = avma;
1666 GEN r,T,p;
1667 ulong pp;
1668 GEN P = FFX_to_raw(Pf, ff);
1669 GEN Q = FFX_to_raw(Qf, ff);
1670 _getFF(ff,&T,&p,&pp);
1671 switch(ff[1])
1672 {
1673 case t_FF_FpXQ:
1674 r = FpXX_add(P, Q, p);
1675 break;
1676 case t_FF_F2xq:
1677 r = F2xX_add(P, Q);
1678 break;
1679 default:
1680 r = FlxX_add(P, Q, pp);
1681 }
1682 if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1683 return gerepilecopy(av, raw_to_FFX(r, ff));
1684 }
1685
1686 static GEN
FFX_wrap2(GEN Pf,GEN Qf,GEN ff,GEN FpXQX (GEN,GEN,GEN,GEN),GEN F2xqX (GEN,GEN,GEN),GEN FlxqX (GEN,GEN,GEN,ulong))1687 FFX_wrap2(GEN Pf, GEN Qf, GEN ff, GEN FpXQX(GEN, GEN, GEN, GEN),
1688 GEN F2xqX(GEN, GEN, GEN), GEN FlxqX(GEN, GEN, GEN, ulong))
1689 {
1690 pari_sp av = avma;
1691 GEN r,T,p;
1692 ulong pp;
1693 GEN P = FFX_to_raw(Pf, ff);
1694 GEN Q = FFX_to_raw(Qf, ff);
1695 _getFF(ff,&T,&p,&pp);
1696 switch(ff[1])
1697 {
1698 case t_FF_FpXQ:
1699 r = FpXQX(P, Q, T, p);
1700 break;
1701 case t_FF_F2xq:
1702 r = F2xqX(P, Q, T);
1703 break;
1704 default:
1705 r = FlxqX(P, Q, T, pp);
1706 }
1707 if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1708 return gerepilecopy(av, raw_to_FFX(r, ff));
1709 }
1710
1711 GEN
FFX_mul(GEN Pf,GEN Qf,GEN ff)1712 FFX_mul(GEN Pf, GEN Qf, GEN ff)
1713 { return FFX_wrap2(Pf, Qf, ff, FpXQX_mul, F2xqX_mul, FlxqX_mul); }
1714
1715 GEN
FFX_gcd(GEN Pf,GEN Qf,GEN ff)1716 FFX_gcd(GEN Pf, GEN Qf, GEN ff)
1717 { return FFX_wrap2(Pf, Qf, ff, FpXQX_gcd, F2xqX_gcd, FlxqX_gcd); }
1718
1719 GEN
FFX_sqr(GEN Pf,GEN ff)1720 FFX_sqr(GEN Pf, GEN ff)
1721 {
1722 pari_sp av = avma;
1723 GEN r,T,p;
1724 ulong pp;
1725 GEN P = FFX_to_raw(Pf, ff);
1726 _getFF(ff,&T,&p,&pp);
1727 switch(ff[1])
1728 {
1729 case t_FF_FpXQ:
1730 r = FpXQX_sqr(P, T, p);
1731 break;
1732 case t_FF_F2xq:
1733 r = F2xqX_sqr(P, T);
1734 break;
1735 default:
1736 r = FlxqX_sqr(P, T, pp);
1737 }
1738 if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1739 return gerepilecopy(av, raw_to_FFX(r, ff));
1740 }
1741
1742 GEN
FFX_rem(GEN Pf,GEN Qf,GEN ff)1743 FFX_rem(GEN Pf, GEN Qf, GEN ff)
1744 { return FFX_wrap2(Pf, Qf, ff, FpXQX_rem, F2xqX_rem, FlxqX_rem); }
1745
1746 GEN
FFX_resultant(GEN Pf,GEN Qf,GEN ff)1747 FFX_resultant(GEN Pf, GEN Qf, GEN ff)
1748 {
1749 pari_sp av = avma;
1750 GEN r,T,p;
1751 ulong pp;
1752 GEN P = FFX_to_raw(Pf, ff);
1753 GEN Q = FFX_to_raw(Qf, ff);
1754 GEN z = _initFF(ff,&T,&p,&pp);
1755 switch(ff[1])
1756 {
1757 case t_FF_FpXQ:
1758 r = FpXQX_resultant(P, Q, T, p);
1759 break;
1760 case t_FF_F2xq:
1761 r = F2xqX_resultant(P, Q, T);
1762 break;
1763 default:
1764 r = FlxqX_resultant(P, Q, T, pp);
1765 }
1766 return gerepileupto(av, _mkFF(ff,z,r));
1767 }
1768
1769 GEN
FFX_disc(GEN Pf,GEN ff)1770 FFX_disc(GEN Pf, GEN ff)
1771 {
1772 pari_sp av = avma;
1773 GEN r,T,p;
1774 ulong pp;
1775 GEN P = FFX_to_raw(Pf, ff);
1776 GEN z = _initFF(ff,&T,&p,&pp);
1777 switch(ff[1])
1778 {
1779 case t_FF_FpXQ:
1780 r = FpXQX_disc(P, T, p);
1781 break;
1782 case t_FF_F2xq:
1783 r = F2xqX_disc(P, T);
1784 break;
1785 default:
1786 r = FlxqX_disc(P, T, pp);
1787 }
1788 return gerepileupto(av, _mkFF(ff,z,r));
1789 }
1790
1791 static GEN
gc_gcdext(pari_sp av,GEN r,GEN * u,GEN * v)1792 gc_gcdext(pari_sp av, GEN r, GEN *u, GEN *v)
1793 {
1794 if (!u && !v) return gerepilecopy(av, r);
1795 if (u && v) gerepileall(av, 3, &r, u, v);
1796 else gerepileall(av, 2, &r, u ? u: v);
1797 return r;
1798 }
1799
1800 GEN
FFX_extgcd(GEN Pf,GEN Qf,GEN ff,GEN * pt_Uf,GEN * pt_Vf)1801 FFX_extgcd(GEN Pf, GEN Qf, GEN ff, GEN *pt_Uf, GEN *pt_Vf)
1802 {
1803 pari_sp av = avma;
1804 GEN r,T,p;
1805 ulong pp;
1806 GEN P = FFX_to_raw(Pf, ff);
1807 GEN Q = FFX_to_raw(Qf, ff);
1808 _getFF(ff,&T,&p,&pp);
1809 switch(ff[1])
1810 {
1811 case t_FF_FpXQ:
1812 r = FpXQX_extgcd(P, Q, T, p, pt_Uf, pt_Vf);
1813 break;
1814 case t_FF_F2xq:
1815 r = F2xqX_extgcd(P, Q, T, pt_Uf, pt_Vf);
1816 break;
1817 default:
1818 r = FlxqX_extgcd(P, Q, T, pp, pt_Uf, pt_Vf);
1819 }
1820 if (pt_Uf) *pt_Uf = raw_to_FFX(*pt_Uf, ff);
1821 if (pt_Vf) *pt_Vf = raw_to_FFX(*pt_Vf, ff);
1822 return gc_gcdext(av, raw_to_FFX(r, ff), pt_Uf, pt_Vf);
1823 }
1824
1825 GEN
FFX_halfgcd(GEN Pf,GEN Qf,GEN ff)1826 FFX_halfgcd(GEN Pf, GEN Qf, GEN ff)
1827 {
1828 pari_sp av = avma;
1829 GEN r,T,p;
1830 ulong pp;
1831 GEN P = FFX_to_raw(Pf, ff);
1832 GEN Q = FFX_to_raw(Qf, ff);
1833 _getFF(ff,&T,&p,&pp);
1834 switch(ff[1])
1835 {
1836 case t_FF_FpXQ:
1837 r = FpXQX_halfgcd(P, Q, T, p);
1838 break;
1839 case t_FF_F2xq:
1840 r = F2xqX_halfgcd(P, Q, T);
1841 break;
1842 default:
1843 r = FlxqX_halfgcd(P, Q, T, pp);
1844 }
1845 return gerepilecopy(av, raw_to_FFXM(r, ff));
1846 }
1847
1848 GEN
FFXQ_sqr(GEN Pf,GEN Qf,GEN ff)1849 FFXQ_sqr(GEN Pf, GEN Qf, GEN ff)
1850 { return FFX_wrap2(Pf, Qf, ff, FpXQXQ_sqr, F2xqXQ_sqr, FlxqXQ_sqr); }
1851
1852 GEN
FFXQ_inv(GEN Pf,GEN Qf,GEN ff)1853 FFXQ_inv(GEN Pf, GEN Qf, GEN ff)
1854 { return FFX_wrap2(Pf, Qf, ff, FpXQXQ_inv, F2xqXQ_inv, FlxqXQ_inv); }
1855
1856 GEN
FFXQ_mul(GEN Pf,GEN Qf,GEN Sf,GEN ff)1857 FFXQ_mul(GEN Pf, GEN Qf, GEN Sf, GEN ff)
1858 {
1859 pari_sp av = avma;
1860 GEN r,T,p;
1861 ulong pp;
1862 GEN P = FFX_to_raw(Pf, ff);
1863 GEN Q = FFX_to_raw(Qf, ff);
1864 GEN S = FFX_to_raw(Sf, ff);
1865 _getFF(ff,&T,&p,&pp);
1866 switch(ff[1])
1867 {
1868 case t_FF_FpXQ:
1869 r = FpXQXQ_mul(P, Q, S, T, p);
1870 break;
1871 case t_FF_F2xq:
1872 r = F2xqXQ_mul(P, Q, S, T);
1873 break;
1874 default:
1875 r = FlxqXQ_mul(P, Q, S, T, pp);
1876 }
1877 if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1878 return gerepilecopy(av, raw_to_FFX(r, ff));
1879 }
1880
1881 GEN
FFXQ_minpoly(GEN Pf,GEN Qf,GEN ff)1882 FFXQ_minpoly(GEN Pf, GEN Qf, GEN ff)
1883 {
1884 pari_sp av = avma;
1885 GEN r,T,p;
1886 ulong pp;
1887 GEN P = FFX_to_raw(Pf, ff);
1888 GEN Q = FFX_to_raw(Qf, ff);
1889 _getFF(ff,&T,&p,&pp);
1890 switch(ff[1])
1891 {
1892 case t_FF_FpXQ:
1893 r = FpXQXQ_minpoly(P, Q, T, p);
1894 break;
1895 case t_FF_F2xq:
1896 r = FlxX_to_F2xX(FlxqXQ_minpoly(F2xX_to_FlxX(P), F2xX_to_FlxX(Q), F2x_to_Flx(T), 2UL));
1897 break;
1898 default:
1899 r = FlxqXQ_minpoly(P, Q, T, pp);
1900 }
1901 return gerepilecopy(av, raw_to_FFX(r, ff));
1902 }
1903
1904 long
FFX_ispower(GEN Pf,long k,GEN ff,GEN * pt_r)1905 FFX_ispower(GEN Pf, long k, GEN ff, GEN *pt_r)
1906 {
1907 pari_sp av = avma;
1908 GEN P,T,p;
1909 ulong pp;
1910 long s;
1911 if (degpol(Pf) % k) return 0;
1912 P = FFX_to_raw(Pf, ff);
1913 _getFF(ff,&T,&p,&pp);
1914 switch(ff[1])
1915 {
1916 case t_FF_FpXQ:
1917 s = FpXQX_ispower(P, k, T, p, pt_r);
1918 break;
1919 case t_FF_F2xq:
1920 s = F2xqX_ispower(P, k, T, pt_r);
1921 break;
1922 default:
1923 s = FlxqX_ispower(P, k, T, pp, pt_r);
1924 }
1925 if (s==0) return gc_long(av,0);
1926 if (pt_r)
1927 *pt_r = gerepilecopy(av, raw_to_FFX(*pt_r, ff));
1928 else set_avma(av);
1929 return 1;
1930 }
1931
1932 GEN
FFX_factor(GEN Pf,GEN ff)1933 FFX_factor(GEN Pf, GEN ff)
1934 {
1935 pari_sp av = avma;
1936 GEN r,T,p;
1937 ulong pp;
1938 GEN P = FFX_to_raw(Pf, ff);
1939 _getFF(ff,&T,&p,&pp);
1940 switch(ff[1])
1941 {
1942 case t_FF_FpXQ:
1943 r = FpXQX_factor(P, T, p);
1944 break;
1945 case t_FF_F2xq:
1946 r = F2xqX_factor(P, T);
1947 break;
1948 default:
1949 r = FlxqX_factor(P, T, pp);
1950 }
1951 return gerepilecopy(av, raw_to_FFX_fact(r, ff));
1952 }
1953
1954 GEN
FFX_factor_squarefree(GEN Pf,GEN ff)1955 FFX_factor_squarefree(GEN Pf, GEN ff)
1956 {
1957 pari_sp av = avma;
1958 GEN r,T,p;
1959 ulong pp;
1960 GEN P = FFX_to_raw(Pf, ff);
1961 _getFF(ff,&T,&p,&pp);
1962 switch(ff[1])
1963 {
1964 case t_FF_FpXQ:
1965 r = FpXQX_factor_squarefree(P, T, p);
1966 break;
1967 case t_FF_F2xq:
1968 r = F2xqX_factor_squarefree(P, T);
1969 break;
1970 default:
1971 r = FlxqX_factor_squarefree(P, T, pp);
1972 }
1973 return gerepilecopy(av, raw_to_FFXC(r, ff));
1974 }
1975
1976 GEN
FFX_ddf(GEN Pf,GEN ff)1977 FFX_ddf(GEN Pf, GEN ff)
1978 {
1979 pari_sp av = avma;
1980 GEN r,T,p;
1981 ulong pp;
1982 GEN P = FFX_to_raw(Pf, ff);
1983 _getFF(ff,&T,&p,&pp);
1984 switch(ff[1])
1985 {
1986 case t_FF_FpXQ:
1987 r = FpXQX_ddf(P, T, p);
1988 break;
1989 case t_FF_F2xq:
1990 r = F2xqX_ddf(P, T);
1991 break;
1992 default:
1993 r = FlxqX_ddf(P, T, pp);
1994 }
1995 return gerepilecopy(av, raw_to_FFX_fact(r, ff));
1996 }
1997
1998 GEN
FFX_degfact(GEN Pf,GEN ff)1999 FFX_degfact(GEN Pf, GEN ff)
2000 {
2001 pari_sp av = avma;
2002 GEN r,T,p;
2003 ulong pp;
2004 GEN P = FFX_to_raw(Pf, ff);
2005 _getFF(ff, &T, &p, &pp);
2006 switch(ff[1])
2007 {
2008 case t_FF_FpXQ:
2009 r = FpXQX_degfact(P, T, p);
2010 break;
2011 case t_FF_F2xq:
2012 r = F2xqX_degfact(P, T);
2013 break;
2014 default:
2015 r = FlxqX_degfact(P, T, pp);
2016 }
2017 return gerepilecopy(av, r);
2018 }
2019
2020 GEN
FqX_to_FFX(GEN x,GEN ff)2021 FqX_to_FFX(GEN x, GEN ff)
2022 {
2023 long i, lx;
2024 GEN y = cgetg_copy(x,&lx);
2025 y[1] = x[1];
2026 for (i=2; i<lx; i++) gel(y,i) = Fq_to_FF(gel(x,i), ff);
2027 return y;
2028 }
2029
2030 GEN
ffgen(GEN T,long v)2031 ffgen(GEN T, long v)
2032 {
2033 GEN A, p = NULL, ff = cgetg(5,t_FFELT);
2034 long d;
2035 switch(typ(T))
2036 {
2037 case t_FFELT:
2038 p = FF_p_i(T); T = FF_mod(T); d = degpol(T);
2039 break;
2040 case t_POL:
2041 d = degpol(T); p = NULL;
2042 if (d < 1 || !RgX_is_FpX(T, &p) || !p) pari_err_TYPE("ffgen",T);
2043 T = RgX_to_FpX(T, p);
2044 /* testing for irreducibility is too costly */
2045 if (!FpX_is_squarefree(T,p)) pari_err_IRREDPOL("ffgen",T);
2046 break;
2047 case t_INT:
2048 d = ispseudoprimepower(T,&p);
2049 if (!d) pari_err_PRIME("ffgen",T);
2050 T = init_Fq(p, d, v);
2051 break;
2052 case t_VEC: case t_COL:
2053 if (lg(T) == 3) {
2054 p = gel(T,1);
2055 A = gel(T,2);
2056 if (typ(p) == t_INT && typ(A) == t_INT)
2057 {
2058 d = itos(A);
2059 T = init_Fq(p, d, v);
2060 break;
2061 }
2062 }
2063 default:
2064 pari_err_TYPE("ffgen",T);
2065 return NULL;/* LCOV_EXCL_LINE */
2066 }
2067 if (v < 0) v = varn(T);
2068 if (lgefint(p)==3)
2069 {
2070 ulong pp = p[2];
2071 long sv = evalvarn(v);
2072 if (pp==2)
2073 {
2074 ff[1] = t_FF_F2xq;
2075 T = ZX_to_F2x(T); T[1] = sv;
2076 A = polx_F2x(sv); if (d == 1) A = F2x_rem(A, T);
2077 p = gen_2;
2078 }
2079 else
2080 {
2081 ff[1] = t_FF_Flxq;
2082 T = ZX_to_Flx(T,pp); T[1] = sv;
2083 A = polx_Flx(sv); if (d == 1) A = Flx_rem(A, T, pp);
2084 p = icopy(p);
2085 }
2086 }
2087 else
2088 {
2089 ff[1] = t_FF_FpXQ;
2090 setvarn(T,v);
2091 A = pol_x(v); if (d == 1) A = FpX_rem(A, T, p);
2092 p = icopy(p);
2093 }
2094 gel(ff,2) = A;
2095 gel(ff,3) = T;
2096 gel(ff,4) = p; return ff;
2097 }
2098
2099 GEN
p_to_FF(GEN p,long v)2100 p_to_FF(GEN p, long v)
2101 {
2102 GEN A, T;
2103 GEN ff = cgetg(5,t_FFELT);
2104 if (lgefint(p)==3)
2105 {
2106 ulong pp = p[2];
2107 long sv = evalvarn(v);
2108 if (pp==2)
2109 {
2110 ff[1] = t_FF_F2xq;
2111 T = polx_F2x(sv);
2112 A = pol1_F2x(sv);
2113 p = gen_2;
2114 }
2115 else
2116 {
2117 ff[1] = t_FF_Flxq;
2118 T = polx_Flx(sv);
2119 A = pol1_Flx(sv);
2120 p = icopy(p);
2121 }
2122 }
2123 else
2124 {
2125 ff[1] = t_FF_FpXQ;
2126 T = pol_x(v);
2127 A = pol_1(v);
2128 p = icopy(p);
2129 }
2130 gel(ff,2) = A;
2131 gel(ff,3) = T;
2132 gel(ff,4) = p; return ff;
2133 }
2134 GEN
Tp_to_FF(GEN T,GEN p)2135 Tp_to_FF(GEN T, GEN p)
2136 {
2137 GEN A, ff;
2138 long v;
2139 if (!T) return p_to_FF(p,0);
2140 ff = cgetg(5,t_FFELT);
2141 v = varn(T);
2142 if (lgefint(p)==3)
2143 {
2144 ulong pp = p[2];
2145 long sv = evalvarn(v);
2146 if (pp==2)
2147 {
2148 ff[1] = t_FF_F2xq;
2149 T = ZX_to_F2x(T);
2150 A = pol1_F2x(sv);
2151 p = gen_2;
2152 }
2153 else
2154 {
2155 ff[1] = t_FF_Flxq;
2156 T = ZX_to_Flx(T, pp);
2157 A = pol1_Flx(sv);
2158 p = icopy(p);
2159 }
2160 }
2161 else
2162 {
2163 ff[1] = t_FF_FpXQ;
2164 T = ZX_copy(T);
2165 A = pol_1(v);
2166 p = icopy(p);
2167 }
2168 gel(ff,2) = A;
2169 gel(ff,3) = T;
2170 gel(ff,4) = p; return ff;
2171 }
2172
2173 GEN
fforder(GEN x,GEN o)2174 fforder(GEN x, GEN o)
2175 {
2176 if (typ(x)!=t_FFELT) pari_err_TYPE("fforder",x);
2177 return FF_order(x,o);
2178 }
2179
2180 GEN
ffprimroot(GEN x,GEN * o)2181 ffprimroot(GEN x, GEN *o)
2182 {
2183 if (typ(x)!=t_FFELT) pari_err_TYPE("ffprimroot",x);
2184 return FF_primroot(x,o);
2185 }
2186
2187 GEN
fflog(GEN x,GEN g,GEN o)2188 fflog(GEN x, GEN g, GEN o)
2189 {
2190 if (typ(x)!=t_FFELT) pari_err_TYPE("fflog",x);
2191 if (typ(g)!=t_FFELT) pari_err_TYPE("fflog",g);
2192 return FF_log(x,g,o);
2193 }
2194
2195 GEN
ffrandom(GEN ff)2196 ffrandom(GEN ff)
2197 {
2198 ulong pp;
2199 GEN r, T, p, z = _initFF(ff,&T,&p,&pp);
2200 switch(ff[1])
2201 {
2202 case t_FF_FpXQ:
2203 r = random_FpX(degpol(T), varn(T), p);
2204 break;
2205 case t_FF_F2xq:
2206 r = random_F2x(F2x_degree(T), T[1]);
2207 break;
2208 default:
2209 r = random_Flx(degpol(T), T[1], pp);
2210 }
2211 return _mkFF(ff,z,r);
2212 }
2213
2214 int
Rg_is_FF(GEN c,GEN * ff)2215 Rg_is_FF(GEN c, GEN *ff)
2216 {
2217 switch(typ(c))
2218 {
2219 case t_FFELT:
2220 if (!*ff) *ff = c;
2221 else if (!FF_samefield(*ff, c)) return 0;
2222 break;
2223 default:
2224 return 0;
2225 }
2226 return 1;
2227 }
2228
2229 int
RgC_is_FFC(GEN x,GEN * ff)2230 RgC_is_FFC(GEN x, GEN *ff)
2231 {
2232 long i, lx = lg(x);
2233 for (i=lx-1; i>0; i--)
2234 if (!Rg_is_FF(gel(x,i), ff)) return 0;
2235 return (*ff != NULL);
2236 }
2237
2238 int
RgM_is_FFM(GEN x,GEN * ff)2239 RgM_is_FFM(GEN x, GEN *ff)
2240 {
2241 long j, lx = lg(x);
2242 for (j=lx-1; j>0; j--)
2243 if (!RgC_is_FFC(gel(x,j), ff)) return 0;
2244 return (*ff != NULL);
2245 }
2246
2247 static GEN
FqC_to_FpXQC(GEN x,GEN T,GEN p)2248 FqC_to_FpXQC(GEN x, GEN T, GEN p)
2249 {
2250 long i, lx;
2251 GEN y = cgetg_copy(x,&lx);
2252 for(i=1; i<lx; i++)
2253 gel(y, i) = Fq_to_FpXQ(gel(x, i), T, p);
2254 return y;
2255 }
2256
2257 static GEN
FqM_to_FpXQM(GEN x,GEN T,GEN p)2258 FqM_to_FpXQM(GEN x, GEN T, GEN p)
2259 {
2260 long i, lx;
2261 GEN y = cgetg_copy(x,&lx);
2262 for(i=1; i<lx; i++)
2263 gel(y, i) = FqC_to_FpXQC(gel(x, i), T, p);
2264 return y;
2265 }
2266
2267 /* for functions t_MAT -> t_MAT */
2268 static GEN
FFM_wrap(GEN M,GEN ff,GEN (* Fq)(GEN,GEN,GEN),GEN (* Flxq)(GEN,GEN,ulong),GEN (* F2xq)(GEN,GEN))2269 FFM_wrap(GEN M, GEN ff, GEN (*Fq)(GEN,GEN,GEN),
2270 GEN (*Flxq)(GEN,GEN,ulong),
2271 GEN (*F2xq)(GEN,GEN))
2272 {
2273 pari_sp av = avma;
2274 ulong pp;
2275 GEN T, p;
2276 _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2277 switch(ff[1])
2278 {
2279 case t_FF_FpXQ: M = Fq(M,T,p); if (M) M = FqM_to_FpXQM(M,T,p);
2280 break;
2281 case t_FF_F2xq: M = F2xq(M,T); break;
2282 default: M = Flxq(M,T,pp); break;
2283 }
2284 if (!M) return gc_NULL(av);
2285 return gerepilecopy(av, raw_to_FFM(M, ff));
2286 }
2287
2288 /* for functions (t_MAT, t_MAT) -> t_MAT */
2289 static GEN
FFM_FFM_wrap(GEN M,GEN N,GEN ff,GEN (* Fq)(GEN,GEN,GEN,GEN),GEN (* Flxq)(GEN,GEN,GEN,ulong),GEN (* F2xq)(GEN,GEN,GEN))2290 FFM_FFM_wrap(GEN M, GEN N, GEN ff,
2291 GEN (*Fq)(GEN, GEN, GEN, GEN),
2292 GEN (*Flxq)(GEN, GEN, GEN, ulong),
2293 GEN (*F2xq)(GEN, GEN, GEN))
2294 {
2295 pari_sp av = avma;
2296 ulong pp;
2297 GEN T, p;
2298 int is_sqr = M==N;
2299 _getFF(ff, &T, &p, &pp);
2300 M = FFM_to_raw(M, ff);
2301 N = is_sqr? M: FFM_to_raw(N, ff);
2302 switch(ff[1])
2303 {
2304 case t_FF_FpXQ: M = Fq(M, N, T, p); if (M) M = FqM_to_FpXQM(M, T, p);
2305 break;
2306 case t_FF_F2xq: M = F2xq(M, N, T); break;
2307 default: M = Flxq(M, N, T, pp); break;
2308 }
2309 if (!M) return gc_NULL(av);
2310 return gerepilecopy(av, raw_to_FFM(M, ff));
2311 }
2312
2313 /* for functions (t_MAT, t_COL) -> t_COL */
2314 static GEN
FFM_FFC_wrap(GEN M,GEN C,GEN ff,GEN (* Fq)(GEN,GEN,GEN,GEN),GEN (* Flxq)(GEN,GEN,GEN,ulong),GEN (* F2xq)(GEN,GEN,GEN))2315 FFM_FFC_wrap(GEN M, GEN C, GEN ff,
2316 GEN (*Fq)(GEN, GEN, GEN, GEN),
2317 GEN (*Flxq)(GEN, GEN, GEN, ulong),
2318 GEN (*F2xq)(GEN, GEN, GEN))
2319 {
2320 pari_sp av = avma;
2321 ulong pp;
2322 GEN T, p;
2323 _getFF(ff, &T, &p, &pp);
2324 M = FFM_to_raw(M, ff);
2325 C = FFC_to_raw(C, ff);
2326 switch(ff[1])
2327 {
2328 case t_FF_FpXQ: C = Fq(M, C, T, p); if (C) C = FqC_to_FpXQC(C, T, p);
2329 break;
2330 case t_FF_F2xq: C = F2xq(M, C, T); break;
2331 default: C = Flxq(M, C, T, pp); break;
2332 }
2333 if (!C) return gc_NULL(av);
2334 return gerepilecopy(av, raw_to_FFC(C, ff));
2335 }
2336
2337 GEN
FFM_ker(GEN M,GEN ff)2338 FFM_ker(GEN M, GEN ff)
2339 { return FFM_wrap(M,ff, &FqM_ker,&FlxqM_ker,&F2xqM_ker); }
2340 GEN
FFM_image(GEN M,GEN ff)2341 FFM_image(GEN M, GEN ff)
2342 { return FFM_wrap(M,ff, &FqM_image,&FlxqM_image,&F2xqM_image); }
2343 GEN
FFM_inv(GEN M,GEN ff)2344 FFM_inv(GEN M, GEN ff)
2345 { return FFM_wrap(M,ff, &FqM_inv,&FlxqM_inv,&F2xqM_inv); }
2346 GEN
FFM_suppl(GEN M,GEN ff)2347 FFM_suppl(GEN M, GEN ff)
2348 { return FFM_wrap(M,ff, &FqM_suppl,&FlxqM_suppl,&F2xqM_suppl); }
2349
2350 GEN
FFM_deplin(GEN M,GEN ff)2351 FFM_deplin(GEN M, GEN ff)
2352 {
2353 pari_sp av = avma;
2354 ulong pp;
2355 GEN C, T, p;
2356 _getFF(ff, &T, &p, &pp); M = FFM_to_raw(M, ff);
2357 switch(ff[1]) {
2358 case t_FF_FpXQ: C = FqM_deplin(M, T, p);
2359 if (C) C = FqC_to_FpXQC(C, T, p); break;
2360 case t_FF_F2xq: C = F2xqM_deplin(M, T); break;
2361 default: C = FlxqM_deplin(M, T, pp); break;
2362 }
2363 if (!C) return gc_NULL(av);
2364 return gerepilecopy(av, raw_to_FFC(C, ff));
2365 }
2366
2367 GEN
FFM_indexrank(GEN M,GEN ff)2368 FFM_indexrank(GEN M, GEN ff)
2369 {
2370 pari_sp av = avma;
2371 ulong pp;
2372 GEN R, T, p;
2373 _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2374 switch(ff[1]) {
2375 case t_FF_FpXQ: R = FqM_indexrank(M,T,p); break;
2376 case t_FF_F2xq: R = F2xqM_indexrank(M,T); break;
2377 default: R = FlxqM_indexrank(M,T,pp); break;
2378 }
2379 return gerepileupto(av, R);
2380 }
2381
2382 long
FFM_rank(GEN M,GEN ff)2383 FFM_rank(GEN M, GEN ff)
2384 {
2385 pari_sp av = avma;
2386 long r;
2387 ulong pp;
2388 GEN T, p;
2389 _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2390 switch(ff[1])
2391 {
2392 case t_FF_FpXQ: r = FqM_rank(M,T,p); break;
2393 case t_FF_F2xq: r = F2xqM_rank(M,T); break;
2394 default: r = FlxqM_rank(M,T,pp); break;
2395 }
2396 return gc_long(av,r);
2397 }
2398 GEN
FFM_det(GEN M,GEN ff)2399 FFM_det(GEN M, GEN ff)
2400 {
2401 pari_sp av = avma;
2402 ulong pp;
2403 GEN d, T, p;
2404 _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2405 switch(ff[1])
2406 {
2407 case t_FF_FpXQ: d = FqM_det(M,T,p); break;
2408 case t_FF_F2xq: d = F2xqM_det(M,T); break;
2409 default: d = FlxqM_det(M,T,pp); break;
2410 }
2411 return gerepilecopy(av, mkFF_i(ff, d));
2412 }
2413
2414 GEN
FFM_FFC_gauss(GEN M,GEN C,GEN ff)2415 FFM_FFC_gauss(GEN M, GEN C, GEN ff)
2416 {
2417 return FFM_FFC_wrap(M, C, ff, FqM_FqC_gauss,
2418 FlxqM_FlxqC_gauss, F2xqM_F2xqC_gauss);
2419 }
2420
2421 GEN
FFM_gauss(GEN M,GEN N,GEN ff)2422 FFM_gauss(GEN M, GEN N, GEN ff)
2423 {
2424 return FFM_FFM_wrap(M, N, ff, FqM_gauss,
2425 FlxqM_gauss, F2xqM_gauss);
2426 }
2427
2428 GEN
FFM_FFC_invimage(GEN M,GEN C,GEN ff)2429 FFM_FFC_invimage(GEN M, GEN C, GEN ff)
2430 {
2431 return FFM_FFC_wrap(M, C, ff, FqM_FqC_invimage,
2432 FlxqM_FlxqC_invimage, F2xqM_F2xqC_invimage);
2433 }
2434
2435 GEN
FFM_invimage(GEN M,GEN N,GEN ff)2436 FFM_invimage(GEN M, GEN N, GEN ff)
2437 {
2438 return FFM_FFM_wrap(M, N, ff, FqM_invimage,
2439 FlxqM_invimage, F2xqM_invimage);
2440 }
2441
2442 GEN
FFM_FFC_mul(GEN M,GEN C,GEN ff)2443 FFM_FFC_mul(GEN M, GEN C, GEN ff)
2444 {
2445 return FFM_FFC_wrap(M, C, ff, FqM_FqC_mul,
2446 FlxqM_FlxqC_mul, F2xqM_F2xqC_mul);
2447 }
2448
2449 GEN
FFM_mul(GEN M,GEN N,GEN ff)2450 FFM_mul(GEN M, GEN N, GEN ff)
2451 {
2452 return FFM_FFM_wrap(M, N, ff, FqM_mul, FlxqM_mul, F2xqM_mul);
2453 }
2454