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