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