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 86040217 : _getFF(GEN x, GEN *T, GEN *p, ulong *pp)
32 : {
33 86040217 : *T=gel(x,3);
34 86040217 : *p=gel(x,4);
35 86040217 : *pp=(*p)[2];
36 86040217 : }
37 :
38 : INLINE GEN
39 84760146 : _initFF(GEN x, GEN *T, GEN *p, ulong *pp)
40 : {
41 84760146 : _getFF(x,T,p,pp);
42 84760147 : return cgetg(5,t_FFELT);
43 : }
44 :
45 : INLINE void
46 69848787 : _checkFF(GEN x, GEN y, const char *s)
47 69848787 : { if (!FF_samefield(x,y)) pari_err_OP(s,x,y); }
48 :
49 : INLINE GEN
50 84524421 : _mkFF(GEN x, GEN z, GEN r)
51 : {
52 84524421 : z[1]=x[1];
53 84524421 : gel(z,2)=r;
54 84524421 : gel(z,3)=gcopy(gel(x,3));
55 84524423 : gel(z,4)=icopy(gel(x,4));
56 84524423 : return z;
57 : }
58 :
59 : INLINE GEN
60 3350881 : _mkFF_i(GEN x, GEN z, GEN r)
61 : {
62 3350881 : z[1]=x[1];
63 3350881 : gel(z,2)=r;
64 3350881 : gel(z,3)=gel(x,3);
65 3350881 : gel(z,4)=gel(x,4);
66 3350881 : return z;
67 : }
68 :
69 : INLINE GEN
70 3122079 : mkFF_i(GEN x, GEN r)
71 : {
72 3122079 : GEN z = cgetg(5,t_FFELT);
73 3122079 : return _mkFF_i(x,z,r);
74 : }
75 :
76 : /*************************************************************************/
77 : /** **/
78 : /** medium-level constructors **/
79 : /** **/
80 : /*************************************************************************/
81 :
82 : static GEN
83 431312 : Z_to_raw(GEN x, GEN ff)
84 : {
85 : ulong pp;
86 : GEN T, p;
87 431312 : _getFF(ff,&T,&p,&pp);
88 431312 : 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 216439 : default:
95 216439 : return Z_to_Flx(x, pp, T[1]);
96 : }
97 : }
98 :
99 : static GEN
100 2222940 : Rg_to_raw(GEN x, GEN ff)
101 : {
102 2222940 : long tx = typ(x);
103 2222940 : switch(tx)
104 : {
105 431312 : case t_INT: case t_FRAC: case t_PADIC: case t_INTMOD:
106 431312 : return Z_to_raw(Rg_to_Fp(x, FF_p_i(ff)), ff);
107 1791628 : case t_FFELT:
108 1791628 : if (!FF_samefield(x,ff))
109 0 : pari_err_MODULUS("Rg_to_raw",x,ff);
110 1791628 : 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 326209 : FFX_to_raw(GEN x, GEN ff)
118 : {
119 : long i, lx;
120 326209 : GEN y = cgetg_copy(x,&lx);
121 326209 : y[1] = x[1];
122 1897351 : for(i=2; i<lx; i++)
123 1571142 : gel(y, i) = Rg_to_raw(gel(x, i), ff);
124 326209 : 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 179758 : default:
131 179758 : return FlxX_renormalize(y, lx);
132 : }
133 : }
134 :
135 : static GEN
136 696087 : FFC_to_raw(GEN x, GEN ff) { pari_APPLY_same(Rg_to_raw(gel(x, i), ff)) }
137 : static GEN
138 54033 : 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 670965 : rawFq_to_FF(GEN x, GEN ff)
143 : {
144 670965 : return mkFF_i(ff, typ(x)==t_INT ? scalarpol(x, varn(gel(ff,3))): x);
145 : }
146 :
147 : /* in place */
148 : static GEN
149 111010 : raw_to_FFX(GEN x, GEN ff)
150 : {
151 111010 : long i, lx = lg(x);
152 781975 : for (i=2; i<lx; i++) gel(x,i) = rawFq_to_FF(gel(x,i), ff);
153 111010 : return x;
154 : }
155 :
156 : /* in place */
157 : static GEN
158 124397 : raw_to_FFC(GEN x, GEN ff)
159 : {
160 124397 : long i, lx = lg(x);
161 530697 : for (i=1; i<lx; i++) gel(x,i) = mkFF_i(ff, gel(x,i));
162 124397 : return x;
163 : }
164 :
165 : /* in place */
166 : static GEN
167 4844 : raw_to_FFM(GEN x, GEN ff)
168 : {
169 4844 : long i, lx = lg(x);
170 25361 : for (i=1; i<lx; i++) gel(x,i) = raw_to_FFC(gel(x,i), ff);
171 4844 : return x;
172 : }
173 :
174 : GEN
175 143738 : Fq_to_FF(GEN x, GEN ff)
176 : {
177 : ulong pp;
178 143738 : GEN r, T, p, z = _initFF(ff,&T,&p,&pp);
179 143738 : if (typ(x) == t_INT) switch(ff[1])
180 : {
181 2 : case t_FF_FpXQ: r = scalarpol(x, varn(T)); break;
182 1638 : case t_FF_F2xq: r = Z_to_F2x(x,T[1]); break;
183 4765 : 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 143738 : 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 73637724 : FF_samechar(GEN x, GEN y)
204 73637724 : { return x[1] == y[1] && equalii(gel(x,4),gel(y,4)); }
205 :
206 : int
207 73637724 : FF_samefield(GEN x, GEN y)
208 73637724 : { return FF_samechar(x, y) && gidentical(gel(x,3),gel(y,3)); }
209 :
210 : int
211 256033 : FF_equal(GEN x, GEN y)
212 256033 : { return FF_samefield(x,y) && gidentical(gel(x,2),gel(y,2)); }
213 :
214 : int
215 11511007 : FF_equal0(GEN x)
216 : {
217 11511007 : return lgpol(gel(x,2))==0;
218 : }
219 :
220 : int
221 26201 : FF_equal1(GEN x)
222 : {
223 26201 : GEN A = gel(x,2);
224 26201 : switch(x[1])
225 : {
226 5575 : case t_FF_FpXQ:
227 5575 : return degpol(A)==0 && gequal1(gel(A,2));
228 20626 : default:
229 20626 : 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 6108 : FF_zero(GEN x)
254 : {
255 : ulong pp;
256 6108 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
257 6108 : 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 4277 : default:
266 4277 : r=zero_Flx(T[1]);
267 : }
268 6108 : return _mkFF(x,z,r);
269 : }
270 :
271 : GEN
272 27895 : FF_1(GEN x)
273 : {
274 : ulong pp;
275 27895 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
276 27895 : 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 15335 : default:
285 15335 : r=pol1_Flx(T[1]);
286 : }
287 27895 : 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 81921 : FF_q(GEN x)
313 : {
314 : ulong pp;
315 : GEN T, p;
316 81921 : _getFF(x,&T,&p,&pp);
317 81921 : switch(x[1])
318 : {
319 2528 : case t_FF_FpXQ:
320 2528 : return powiu(p, degpol(T));
321 : break;
322 10696 : case t_FF_F2xq:
323 10696 : return int2n(F2x_degree(T));
324 : break;
325 68697 : default:
326 68697 : return powuu(pp,degpol(T));
327 : }
328 : }
329 :
330 : GEN
331 112 : FF_p(GEN x)
332 : {
333 112 : return icopy(gel(x,4));
334 : }
335 :
336 : GEN
337 3153540 : FF_p_i(GEN x)
338 : {
339 3153540 : return gel(x,4);
340 : }
341 :
342 : GEN
343 416171 : FF_mod(GEN x)
344 : {
345 416171 : switch(x[1])
346 : {
347 1340 : case t_FF_FpXQ:
348 1340 : return ZX_copy(gel(x,3));
349 184730 : case t_FF_F2xq:
350 184730 : return F2x_to_ZX(gel(x,3));
351 230101 : default:
352 230101 : return Flx_to_ZX(gel(x,3));
353 : }
354 : }
355 :
356 : long
357 140 : FF_var(GEN x)
358 : {
359 140 : switch(x[1])
360 : {
361 56 : case t_FF_FpXQ:
362 56 : return varn(gel(x,3));
363 84 : case t_FF_F2xq:
364 : default:
365 84 : 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 549927 : FF_to_F2xq(GEN x)
383 : {
384 549927 : switch(x[1])
385 : {
386 0 : case t_FF_FpXQ:
387 0 : return ZX_to_F2x(gel(x,2));
388 549927 : case t_FF_F2xq:
389 549927 : 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 603026 : FF_to_Flxq(GEN x)
411 : {
412 603026 : 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 603026 : default:
419 603026 : 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 18973 : FF_to_FpXQ(GEN x)
439 : {
440 18973 : switch(x[1])
441 : {
442 14907 : case t_FF_FpXQ:
443 14907 : return ZX_copy(gel(x,2));
444 609 : case t_FF_F2xq:
445 609 : 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 172802 : FF_to_FpXQ_i(GEN x)
453 : {
454 172802 : 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 170050 : default:
461 170050 : return Flx_to_ZX(gel(x,2));
462 : }
463 : }
464 :
465 : GEN
466 33688964 : FF_add(GEN x, GEN y)
467 : {
468 : ulong pp;
469 33688964 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
470 33688964 : _checkFF(x,y,"+");
471 33688964 : switch(x[1])
472 : {
473 2672119 : case t_FF_FpXQ:
474 2672119 : r=FpX_add(gel(x,2),gel(y,2),p);
475 2672119 : break;
476 11160170 : case t_FF_F2xq:
477 11160170 : r=F2x_add(gel(x,2),gel(y,2));
478 11160170 : break;
479 19856675 : default:
480 19856675 : r=Flx_add(gel(x,2),gel(y,2),pp);
481 : }
482 33688964 : return _mkFF(x,z,r);
483 : }
484 : GEN
485 7934937 : FF_sub(GEN x, GEN y)
486 : {
487 : ulong pp;
488 7934937 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
489 7934937 : _checkFF(x,y,"+");
490 7934937 : switch(x[1])
491 : {
492 724726 : case t_FF_FpXQ:
493 724726 : r=FpX_sub(gel(x,2),gel(y,2),p);
494 724726 : break;
495 3845614 : case t_FF_F2xq:
496 3845614 : r=F2x_add(gel(x,2),gel(y,2));
497 3845614 : break;
498 3364597 : default:
499 3364597 : r=Flx_sub(gel(x,2),gel(y,2),pp);
500 : }
501 7934937 : return _mkFF(x,z,r);
502 : }
503 :
504 : GEN
505 1365428 : FF_Z_add(GEN x, GEN y)
506 : {
507 : ulong pp;
508 1365428 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
509 1365428 : switch(x[1])
510 : {
511 2796 : case t_FF_FpXQ:
512 : {
513 2796 : pari_sp av=avma;
514 2796 : r=gc_upto(av,FpX_Fp_add(gel(x,2),modii(y,p),p));
515 2796 : break;
516 : }
517 735358 : case t_FF_F2xq:
518 735358 : r=mpodd(y)?F2x_1_add(gel(x,2)):vecsmall_copy(gel(x,2));
519 735357 : break;
520 627274 : default:
521 627274 : r=Flx_Fl_add(gel(x,2),umodiu(y,pp),pp);
522 : }
523 1365427 : 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 2299202 : FF_neg(GEN x)
550 : {
551 : ulong pp;
552 2299202 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
553 2299202 : switch(x[1])
554 : {
555 226916 : case t_FF_FpXQ:
556 226916 : r=FpX_neg(gel(x,2),p);
557 226916 : break;
558 1080684 : case t_FF_F2xq:
559 1080684 : r=vecsmall_copy(gel(x,2));
560 1080684 : break;
561 991602 : default:
562 991602 : r=Flx_neg(gel(x,2),pp);
563 : }
564 2299202 : return _mkFF(x,z,r);
565 : }
566 :
567 : GEN
568 85064 : FF_neg_i(GEN x)
569 : {
570 : ulong pp;
571 85064 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
572 85064 : 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 74741 : default:
581 74741 : r=Flx_neg(gel(x,2),pp);
582 : }
583 85064 : 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 25760666 : FF_mul(GEN x, GEN y)
677 : {
678 : ulong pp;
679 25760666 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
680 25760666 : pari_sp av=avma;
681 25760666 : _checkFF(x,y,"*");
682 25760666 : switch(x[1])
683 : {
684 1803673 : case t_FF_FpXQ:
685 1803673 : r=FpXQ_mul(gel(x,2),gel(y,2),T,p);
686 1803673 : break;
687 6741635 : case t_FF_F2xq:
688 6741635 : r=F2xq_mul(gel(x,2),gel(y,2),T);
689 6741634 : break;
690 17215358 : default:
691 17215358 : r=Flxq_mul(gel(x,2),gel(y,2),T,pp);
692 : }
693 25760665 : return _mkFF(x,z,gc_upto(av, r));
694 : }
695 :
696 : GEN
697 3946799 : FF_Z_mul(GEN x, GEN y)
698 : {
699 : ulong pp;
700 3946799 : GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
701 3946799 : switch(x[1])
702 : {
703 250532 : case t_FF_FpXQ: /* modii(y,p) left on stack for efficiency */
704 250532 : r = FpX_Fp_mul(A, modii(y,p),p);
705 250532 : break;
706 2022215 : case t_FF_F2xq:
707 2022215 : r = mpodd(y)? vecsmall_copy(A): zero_Flx(A[1]);
708 2022215 : break;
709 1674052 : default:
710 1674052 : r = Flx_Fl_mul(A, umodiu(y,pp), pp);
711 : }
712 3946799 : 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 2971446 : FF_sqr(GEN x)
737 : {
738 : ulong pp;
739 2971446 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
740 2971446 : 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 474166 : case t_FF_F2xq:
749 474166 : r=F2xq_sqr(gel(x,2),T);
750 474166 : break;
751 2477995 : default:
752 2477995 : r=Flxq_sqr(gel(x,2),T,pp);
753 : }
754 2971446 : return _mkFF(x,z,r);
755 : }
756 :
757 : GEN
758 3843732 : FF_mul2n(GEN x, long n)
759 : {
760 : ulong pp;
761 3843732 : GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
762 3843732 : switch(x[1])
763 : {
764 390152 : case t_FF_FpXQ:
765 : {
766 : GEN p1; /* left on stack for efficiency */
767 390152 : if (n>0) p1=remii(int2n(n),p);
768 34 : else p1=Fp_inv(remii(int2n(-n),p),p);
769 390152 : r = FpX_Fp_mul(A, p1, p);
770 : }
771 390152 : break;
772 1917838 : case t_FF_F2xq:
773 1917838 : if (n<0) pari_err_INV("FF_mul2n", gen_2);
774 1917838 : r = n==0? vecsmall_copy(A): zero_Flx(A[1]);
775 1917838 : break;
776 1535742 : default:
777 : {
778 : ulong l1;
779 1535742 : if (n>0) l1 = umodiu(int2n(n),pp);
780 263 : else l1 = Fl_inv(umodiu(int2n(-n),pp),pp);
781 1535742 : r = Flx_Fl_mul(A,l1,pp);
782 : }
783 : }
784 3843732 : return _mkFF(x,z,r);
785 : }
786 :
787 : GEN
788 14096 : FF_inv(GEN x)
789 : {
790 : ulong pp;
791 14096 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
792 14096 : pari_sp av=avma;
793 14096 : 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 8692 : case t_FF_F2xq:
799 8692 : r=F2xq_inv(gel(x,2),T);
800 8692 : break;
801 2106 : default:
802 2106 : r=Flxq_inv(gel(x,2),T,pp);
803 : }
804 14096 : return _mkFF(x,z,r);
805 : }
806 :
807 : GEN
808 2464024 : FF_div(GEN x, GEN y)
809 : {
810 : ulong pp;
811 2464024 : GEN r, T, p, z=_initFF(x,&T,&p,&pp);
812 2464024 : pari_sp av=avma;
813 2464024 : _checkFF(x,y,"/");
814 2464024 : switch(x[1])
815 : {
816 225402 : case t_FF_FpXQ:
817 225402 : r=gc_upto(av,FpXQ_div(gel(x,2),gel(y,2),T,p));
818 225402 : break;
819 1167617 : case t_FF_F2xq:
820 1167617 : r=gc_upto(av,F2xq_div(gel(x,2),gel(y,2),T));
821 1167547 : break;
822 1071005 : default:
823 1071005 : r=gc_upto(av,Flxq_div(gel(x,2),gel(y,2),T,pp));
824 : }
825 2463926 : return _mkFF(x,z,r);
826 : }
827 :
828 : GEN
829 462 : Z_FF_div(GEN n, GEN x)
830 : {
831 : ulong pp;
832 462 : GEN r, T, p, A = gel(x,2), z=_initFF(x,&T,&p,&pp);
833 462 : pari_sp av=avma;
834 462 : 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 390 : default:
844 390 : r = gc_upto(av, Flx_Fl_mul(Flxq_inv(A,T,pp),umodiu(n,pp),pp));
845 : }
846 462 : return _mkFF(x,z,r);
847 : }
848 :
849 : GEN
850 2212 : FF_sqrtn(GEN x, GEN n, GEN *zetan)
851 : {
852 : ulong pp;
853 2212 : GEN r, T, p, y=_initFF(x,&T,&p,&pp);
854 2212 : 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 1950 : default:
863 1950 : r=Flxq_sqrtn(gel(x,2),n,T,pp,zetan);
864 : }
865 2191 : if (!r) pari_err_SQRTN("FF_sqrtn",x);
866 2191 : (void)_mkFF(x, y, r);
867 2191 : if (zetan)
868 : {
869 189 : GEN z = cgetg(lg(y),t_FFELT);
870 189 : *zetan=_mkFF(x, z, *zetan);
871 : }
872 2191 : 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 129 : if (pt) { *pt = z; (void)_mkFF(x,z,r); }
943 129 : 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 196 : FF_log(GEN x, GEN g, GEN ord)
1065 : {
1066 196 : pari_sp av=avma;
1067 : ulong pp;
1068 : GEN r, T, p;
1069 196 : _getFF(x,&T,&p,&pp);
1070 196 : _checkFF(x,g,"log");
1071 196 : 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 124 : default:
1082 124 : if (!ord) ord = factor_pn_1(p,degpol(T));
1083 124 : r = Flxq_log(gel(x,2), gel(g,2), ord, T, pp);
1084 : }
1085 168 : 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 266511 : to_FFE(GEN P, GEN fg)
1134 : {
1135 266511 : if(ell_is_inf(P))
1136 7 : return ellinf();
1137 : else
1138 266504 : 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 970 : FqV_to_FpXQV(GEN x, GEN T)
1151 : {
1152 970 : pari_sp av = avma;
1153 970 : long v = varn(T), i, s=0, l = lg(x);
1154 970 : GEN y = shallowcopy(x);
1155 4850 : for(i=1; i<l; i++)
1156 3880 : if (typ(gel(x,i))==t_INT)
1157 : {
1158 0 : gel(y,i) = scalarpol(gel(x,i), v);
1159 0 : s = 1;
1160 : }
1161 970 : if (!s) { set_avma(av); return x; }
1162 0 : return y;
1163 : }
1164 :
1165 : GEN
1166 103697 : FF_ellcard(GEN E)
1167 : {
1168 : GEN T,p;
1169 : ulong pp;
1170 103697 : GEN e = ellff_get_a4a6(E);
1171 103697 : GEN fg = ellff_get_field(E);
1172 103697 : _getFF(fg,&T,&p,&pp);
1173 103697 : switch(fg[1])
1174 : {
1175 1710 : case t_FF_FpXQ:
1176 1710 : return FpXQ_ellcard(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p),T,p);
1177 45709 : case t_FF_F2xq:
1178 45709 : return F2xq_ellcard(gel(e,1),gel(e,2),T);
1179 56278 : default:
1180 56278 : return Flxq_ellcard(gel(e,1),gel(e,2),T,pp);
1181 : }
1182 : }
1183 :
1184 : GEN
1185 14 : FF_ellcard_SEA(GEN E, long smallfact)
1186 : {
1187 14 : pari_sp av = avma;
1188 : GEN T,p;
1189 : ulong pp;
1190 14 : GEN e = ellff_get_a4a6(E), a4, a6, card;
1191 14 : GEN fg = ellff_get_field(E);
1192 14 : _getFF(fg,&T,&p,&pp);
1193 14 : switch(fg[1])
1194 : {
1195 0 : case t_FF_FpXQ:
1196 0 : a4 = Fq_to_FpXQ(gel(e,1), T, p);
1197 0 : a6 = Fq_to_FpXQ(gel(e,2), T, p);
1198 0 : card = Fq_ellcard_SEA(a4, a6, powiu(p,degpol(T)), T,p, smallfact);
1199 0 : break;
1200 0 : case t_FF_F2xq:
1201 0 : pari_err_IMPL("SEA for char 2");
1202 14 : default:
1203 14 : a4 = Flx_to_ZX(gel(e,1));
1204 14 : a6 = Flx_to_ZX(gel(e,2));
1205 14 : card = Fq_ellcard_SEA(a4, a6, powuu(pp,degpol(T)), Flx_to_ZX(T), p, smallfact);
1206 : }
1207 14 : return gc_INT(av, card);
1208 : }
1209 :
1210 : /* return G, set m */
1211 : GEN
1212 26117 : FF_ellgroup(GEN E, GEN *pm)
1213 : {
1214 : GEN T, p, e, fg, N;
1215 : ulong pp;
1216 :
1217 26117 : N = ellff_get_card(E);
1218 26117 : e = ellff_get_a4a6(E);
1219 26117 : fg = ellff_get_field(E);
1220 26117 : _getFF(fg,&T,&p,&pp);
1221 26117 : switch(fg[1])
1222 : {
1223 15 : case t_FF_FpXQ:
1224 15 : return FpXQ_ellgroup(Fq_to_FpXQ(gel(e,1),T,p),
1225 15 : Fq_to_FpXQ(gel(e,2),T,p),N,T,p,pm);
1226 3808 : case t_FF_F2xq:
1227 3808 : return F2xq_ellgroup(gel(e,1),gel(e,2),N,T,pm);
1228 22294 : default:
1229 22294 : return Flxq_ellgroup(gel(e,1),gel(e,2),N,T,pp,pm);
1230 : }
1231 : }
1232 :
1233 : GEN
1234 18116 : FF_ellgens(GEN E)
1235 : {
1236 : GEN D, fg, e, m, T, p, F, e3;
1237 : ulong pp;
1238 :
1239 18116 : fg = ellff_get_field(E);
1240 18116 : e = ellff_get_a4a6(E);
1241 18116 : m = ellff_get_m(E);
1242 18116 : D = ellff_get_D(E);
1243 18116 : _getFF(fg,&T,&p,&pp);
1244 18116 : switch(fg[1])
1245 : {
1246 8 : case t_FF_FpXQ:
1247 8 : e3 = FqV_to_FpXQV(gel(e,3),T);
1248 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);
1249 8 : break;
1250 3738 : case t_FF_F2xq:
1251 3738 : F = F2xq_ellgens(gel(e,1),gel(e,2),gel(e,3),D,m,T);
1252 3738 : break;
1253 14370 : default:
1254 14370 : F = Flxq_ellgens(gel(e,1),gel(e,2),gel(e,3),D,m,T, pp);
1255 14370 : break;
1256 : }
1257 18116 : return to_FFE_vec(F,fg);
1258 : }
1259 :
1260 : GEN
1261 119 : FF_elldata(GEN E, GEN fg)
1262 : {
1263 : GEN T,p,e;
1264 : ulong pp;
1265 119 : _getFF(fg,&T,&p,&pp);
1266 119 : switch(fg[1])
1267 : {
1268 0 : case t_FF_FpXQ:
1269 0 : e = ell_to_a4a6_FpXQ(E,T,p); break;
1270 56 : case t_FF_F2xq:
1271 56 : e = ell_to_a4a6_F2xq(E,T); break;
1272 63 : default:
1273 63 : e = ell_to_a4a6_Flxq(E,T,pp); break;
1274 : }
1275 119 : return mkvec2(fg,e);
1276 : }
1277 :
1278 : /* allow singular E, set E.j = 0 in this case */
1279 : GEN
1280 121428 : FF_ellinit(GEN E, GEN fg)
1281 : {
1282 121428 : GEN T,p,e, D, c4, y = E;
1283 : ulong pp;
1284 : long i;
1285 121428 : _getFF(fg,&T,&p,&pp);
1286 121428 : switch(fg[1])
1287 : {
1288 1726 : case t_FF_FpXQ:
1289 1726 : e = ell_to_a4a6_FpXQ(E,T,p);
1290 22438 : for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_FpXQ(gel(E,i),T,p));
1291 1726 : break;
1292 45905 : case t_FF_F2xq:
1293 45905 : e = ell_to_a4a6_F2xq(E,T);
1294 596765 : for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_F2xq(gel(E,i),T));
1295 45905 : break;
1296 73797 : default:
1297 73797 : e = ell_to_a4a6_Flxq(E,T,pp);
1298 959361 : for(i=1;i<=12;i++) gel(y,i) = mkFF_i(fg,Rg_to_Flxq(gel(E,i),T,pp));
1299 73797 : break;
1300 : }
1301 121428 : D = ell_get_disc(y);
1302 121428 : c4 = ell_get_c4(y);
1303 121428 : gel(y,13) = FF_equal0(D)? D: gdiv(gpowgs(c4,3), D);
1304 121428 : gel(y,14) = mkvecsmall(t_ELL_Fq);
1305 121428 : gel(y,15) = mkvec2(fg,e);
1306 121428 : return y;
1307 : }
1308 :
1309 : GEN
1310 27188 : FF_elltwist(GEN E)
1311 : {
1312 27188 : pari_sp av = avma;
1313 27188 : GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1314 : GEN T, p, a, a6, V;
1315 : ulong pp;
1316 27188 : _getFF(fg,&T,&p,&pp);
1317 27188 : switch (fg[1])
1318 : {
1319 840 : case t_FF_FpXQ:
1320 840 : FpXQ_elltwist(gel(e,1), gel(e,2), T, p, &a, &a6);
1321 840 : V = mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6));
1322 840 : break;
1323 3514 : case t_FF_F2xq:
1324 3514 : F2xq_elltwist(gel(e,1), gel(e,2), T, &a, &a6);
1325 7028 : V = typ(a)==t_VECSMALL ?
1326 3514 : mkvec5(gen_1, mkFF_i(fg, a), gen_0, gen_0, mkFF_i(fg, a6)):
1327 0 : mkvec5(gen_0, gen_0, mkFF_i(fg, gel(a,1)), mkFF_i(fg, gel(a,2)), mkFF_i(fg, a6));
1328 3514 : break;
1329 22834 : default:
1330 22834 : Flxq_elltwist(gel(e,1), gel(e,2), T, pp, &a, &a6);
1331 22834 : V = typ(a)==t_VECSMALL ?
1332 22834 : mkvec5(gen_0, gen_0, gen_0, mkFF_i(fg, a), mkFF_i(fg, a6)):
1333 7602 : mkvec5(gen_0, mkFF_i(fg, gel(a,1)), gen_0, gen_0, mkFF_i(fg, a6));
1334 : }
1335 27188 : return gc_GEN(av, V);
1336 : }
1337 :
1338 : static long
1339 0 : F3x_equalm1(GEN x) { return degpol(x)==0 && x[2] == 2; }
1340 : GEN
1341 245977 : FF_ellrandom(GEN E)
1342 : {
1343 245977 : pari_sp av = avma;
1344 245977 : GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
1345 : GEN T,p;
1346 : ulong pp;
1347 245977 : _getFF(fg,&T,&p,&pp);
1348 245977 : switch (fg[1])
1349 : {
1350 934 : case t_FF_FpXQ:
1351 934 : Q = random_FpXQE(Fq_to_FpXQ(gel(e,1),T,p), Fq_to_FpXQ(gel(e,2),T,p), T, p);
1352 934 : Q = FpXQE_changepoint(Q, FqV_to_FpXQV(gel(e,3), T), T, p);
1353 934 : break;
1354 168088 : case t_FF_F2xq:
1355 : {
1356 168088 : long d = F2x_degree(T);
1357 : /* if #E(Fq) = 1 return [0] */
1358 168088 : if (d<=2 && typ(gel(e,1)) == t_VEC)
1359 : { /* over F2 or F4, supersingular */
1360 1419 : GEN v = gel(e,1), A6 = gel(e,2), a3 = gel(v,1), A4 = gel(v,2);
1361 1419 : if (F2x_equal1(a3) &&
1362 128 : ((d==1 && F2x_equal1(A4) && F2x_equal1(A6))
1363 595 : || (d==2 && !lgpol(A4) && F2x_degree(A6)==1))) return ellinf();
1364 : }
1365 167972 : Q = random_F2xqE(gel(e,1), gel(e,2), T);
1366 167972 : Q = F2xqE_changepoint(Q, gel(e,3), T);
1367 167972 : break;
1368 : }
1369 76955 : default:
1370 : /* if #E(Fq) = 1 return [0] */
1371 76955 : if (pp==3 && degpol(T)==1 && typ(gel(e,1))==t_VECSMALL)
1372 : { /* over F3, supersingular */
1373 0 : GEN mb4 = gel(e,1), b6 = gel(e,2);
1374 0 : if (F3x_equalm1(mb4) && F3x_equalm1(b6)) return ellinf();
1375 : }
1376 76955 : Q = random_FlxqE(gel(e,1), gel(e,2), T, pp);
1377 76955 : Q = FlxqE_changepoint(Q, gel(e,3), T, pp);
1378 : }
1379 245861 : return gc_GEN(av, to_FFE(Q, fg));
1380 : }
1381 :
1382 : GEN
1383 7 : FF_ellmul(GEN E, GEN P, GEN n)
1384 : {
1385 7 : pari_sp av = avma;
1386 7 : GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E), Q;
1387 : GEN T,p, Pp, Qp, e3;
1388 : ulong pp;
1389 7 : _getFF(fg,&T,&p,&pp);
1390 7 : switch (fg[1])
1391 : {
1392 0 : case t_FF_FpXQ:
1393 0 : e3 = FqV_to_FpXQV(gel(e,3),T);
1394 0 : Pp = FpXQE_changepointinv(RgE_to_FpXQE(P, T, p), e3, T, p);
1395 0 : Qp = FpXQE_mul(Pp, n, gel(e,1), T, p);
1396 0 : Q = FpXQE_changepoint(Qp, gel(e,3), T, p);
1397 0 : break;
1398 0 : case t_FF_F2xq:
1399 0 : Pp = F2xqE_changepointinv(RgE_to_F2xqE(P, T), gel(e,3), T);
1400 0 : Qp = F2xqE_mul(Pp, n, gel(e,1), T);
1401 0 : Q = F2xqE_changepoint(Qp, gel(e,3), T);
1402 0 : break;
1403 7 : default:
1404 7 : Pp = FlxqE_changepointinv(RgE_to_FlxqE(P, T, pp), gel(e,3), T, pp);
1405 7 : Qp = FlxqE_mul(Pp, n, gel(e,1), T, pp);
1406 7 : Q = FlxqE_changepoint(Qp, gel(e,3), T, pp);
1407 : }
1408 7 : return gc_GEN(av, to_FFE(Q, fg));
1409 : }
1410 :
1411 : GEN
1412 1764 : FF_ellorder(GEN E, GEN P, GEN o)
1413 : {
1414 1764 : pari_sp av = avma;
1415 1764 : GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1416 : GEN r,T,p,Pp,e3;
1417 : ulong pp;
1418 1764 : _getFF(fg,&T,&p,&pp);
1419 1764 : switch (fg[1])
1420 : {
1421 14 : case t_FF_FpXQ:
1422 14 : e3 = FqV_to_FpXQV(gel(e,3),T);
1423 14 : Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1424 14 : r = FpXQE_order(Pp, o, gel(e,1), T, p);
1425 14 : break;
1426 280 : case t_FF_F2xq:
1427 280 : Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1428 280 : r = F2xqE_order(Pp, o, gel(e,1), T);
1429 280 : break;
1430 1470 : default:
1431 1470 : Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1432 1470 : r = FlxqE_order(Pp, o, gel(e,1), T, pp);
1433 : }
1434 1764 : return gc_upto(av, r);
1435 : }
1436 :
1437 : GEN
1438 91 : FF_elllog(GEN E, GEN P, GEN Q, GEN o)
1439 : {
1440 91 : pari_sp av = avma;
1441 91 : GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1442 : GEN r,T,p, Pp,Qp, e3;
1443 : ulong pp;
1444 91 : _getFF(fg,&T,&p,&pp);
1445 91 : switch(fg[1])
1446 : {
1447 0 : case t_FF_FpXQ:
1448 0 : e3 = FqV_to_FpXQV(gel(e,3),T);
1449 0 : Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1450 0 : Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1451 0 : r = FpXQE_log(Pp, Qp, o, gel(e,1), T, p);
1452 0 : break;
1453 42 : case t_FF_F2xq:
1454 42 : Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1455 42 : Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1456 42 : r = F2xqE_log(Pp, Qp, o, gel(e,1), T);
1457 42 : break;
1458 49 : default:
1459 49 : Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1460 49 : Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1461 49 : r = FlxqE_log(Pp, Qp, o, gel(e,1), T, pp);
1462 : }
1463 91 : return gc_upto(av, r);
1464 : }
1465 :
1466 : GEN
1467 4998 : FF_ellweilpairing(GEN E, GEN P, GEN Q, GEN m)
1468 : {
1469 4998 : GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1470 : GEN r,T,p, Pp,Qp, e3;
1471 : ulong pp;
1472 4998 : GEN z=_initFF(fg,&T,&p,&pp);
1473 4998 : pari_sp av = avma;
1474 4998 : switch(fg[1])
1475 : {
1476 7 : case t_FF_FpXQ:
1477 7 : e3 = FqV_to_FpXQV(gel(e,3),T);
1478 7 : Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1479 7 : Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1480 7 : r = FpXQE_weilpairing(Pp, Qp, m, gel(e,1), T, p);
1481 7 : break;
1482 4970 : case t_FF_F2xq:
1483 4970 : Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1484 4970 : Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1485 4970 : r = F2xqE_weilpairing(Pp, Qp, m, gel(e,1), T);
1486 4970 : break;
1487 21 : default:
1488 21 : Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1489 21 : Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1490 21 : r = FlxqE_weilpairing(Pp, Qp, m, gel(e,1), T, pp);
1491 : }
1492 4998 : r = gc_upto(av, r);
1493 4998 : return _mkFF(fg,z,r);
1494 : }
1495 :
1496 : GEN
1497 98 : FF_elltatepairing(GEN E, GEN P, GEN Q, GEN m)
1498 : {
1499 98 : GEN fg = ellff_get_field(E), e = ellff_get_a4a6(E);
1500 : GEN r,T,p, Pp,Qp, e3;
1501 : ulong pp;
1502 98 : GEN z=_initFF(fg,&T,&p,&pp);
1503 98 : pari_sp av = avma;
1504 98 : switch(fg[1])
1505 : {
1506 7 : case t_FF_FpXQ:
1507 7 : e3 = FqV_to_FpXQV(gel(e,3),T);
1508 7 : Pp = FpXQE_changepointinv(RgE_to_FpXQE(P,T,p), e3, T, p);
1509 7 : Qp = FpXQE_changepointinv(RgE_to_FpXQE(Q,T,p), e3, T, p);
1510 7 : r = FpXQE_tatepairing(Pp, Qp, m, gel(e,1), T, p);
1511 7 : break;
1512 28 : case t_FF_F2xq:
1513 28 : Pp = F2xqE_changepointinv(RgE_to_F2xqE(P,T), gel(e,3), T);
1514 28 : Qp = F2xqE_changepointinv(RgE_to_F2xqE(Q,T), gel(e,3), T);
1515 28 : r = F2xqE_tatepairing(Pp, Qp, m, gel(e,1), T);
1516 28 : break;
1517 63 : default:
1518 63 : Pp = FlxqE_changepointinv(RgE_to_FlxqE(P,T,pp), gel(e,3), T, pp);
1519 63 : Qp = FlxqE_changepointinv(RgE_to_FlxqE(Q,T,pp), gel(e,3), T, pp);
1520 63 : r = FlxqE_tatepairing(Pp, Qp, m, gel(e,1), T, pp);
1521 : }
1522 98 : r = gc_upto(av, r);
1523 98 : return _mkFF(fg,z,r);
1524 : }
1525 :
1526 : GEN
1527 103670 : FFX_roots(GEN Pf, GEN ff)
1528 : {
1529 103670 : pari_sp av = avma;
1530 : GEN r,T,p;
1531 : ulong pp;
1532 103670 : GEN P = FFX_to_raw(Pf, ff);
1533 103670 : _getFF(ff,&T,&p,&pp);
1534 103670 : switch(ff[1])
1535 : {
1536 85 : case t_FF_FpXQ:
1537 85 : r = FpXQX_roots(P, T, p);
1538 85 : break;
1539 57512 : case t_FF_F2xq:
1540 57512 : r = F2xqX_roots(P, T);
1541 57512 : break;
1542 46073 : default:
1543 46073 : r = FlxqX_roots(P, T, pp);
1544 : }
1545 103670 : return gc_GEN(av, raw_to_FFC(r, ff));
1546 : }
1547 :
1548 : long
1549 0 : FFX_nbroots(GEN Pf, GEN ff)
1550 : {
1551 0 : pari_sp av = avma;
1552 : GEN T,p;
1553 : ulong pp;
1554 : long r;
1555 0 : GEN P = FFX_to_raw(Pf, ff);
1556 0 : _getFF(ff,&T,&p,&pp);
1557 0 : switch(ff[1])
1558 : {
1559 0 : case t_FF_FpXQ:
1560 0 : r = FpXQX_nbroots(P, T, p);
1561 0 : break;
1562 0 : case t_FF_F2xq:
1563 0 : r = F2xqX_nbroots(P, T);
1564 0 : break;
1565 0 : default:
1566 0 : r = FlxqX_nbroots(P, T, pp);
1567 : }
1568 0 : return gc_long(av, r);
1569 : }
1570 :
1571 : static GEN
1572 140 : raw_to_FFXC(GEN x, GEN ff) { pari_APPLY_type(t_COL, raw_to_FFX(gel(x,i), ff)); }
1573 : static GEN
1574 63 : raw_to_FFXM(GEN x, GEN ff) { pari_APPLY_same(raw_to_FFXC(gel(x,i), ff)); }
1575 : static GEN
1576 448 : raw_to_FFX_fact(GEN F, GEN ff)
1577 : {
1578 : GEN y, u, v;
1579 448 : GEN P = gel(F,1), E = gel(F,2);
1580 448 : long j, l = lg(P);
1581 448 : y = cgetg(3,t_MAT);
1582 448 : u = cgetg(l,t_COL); gel(y,1) = u;
1583 448 : v = cgetg(l,t_COL); gel(y,2) = v;
1584 2093 : for (j=1; j<l; j++)
1585 : {
1586 1645 : gel(u,j) = raw_to_FFX(gel(P,j), ff);
1587 1645 : gel(v,j) = utoi(uel(E,j));
1588 : }
1589 448 : return y;
1590 : }
1591 :
1592 : static GEN
1593 2643 : FFX_zero(GEN ff, long v)
1594 : {
1595 2643 : GEN r = cgetg(3,t_POL);
1596 2643 : r[1] = evalvarn(v);
1597 2643 : gel(r,2) = FF_zero(ff);
1598 2643 : return r;
1599 : }
1600 :
1601 : GEN
1602 0 : FFX_add(GEN Pf, GEN Qf, GEN ff)
1603 : {
1604 0 : pari_sp av = avma;
1605 : GEN r,T,p;
1606 : ulong pp;
1607 0 : GEN P = FFX_to_raw(Pf, ff);
1608 0 : GEN Q = FFX_to_raw(Qf, ff);
1609 0 : _getFF(ff,&T,&p,&pp);
1610 0 : switch(ff[1])
1611 : {
1612 0 : case t_FF_FpXQ:
1613 0 : r = FpXX_add(P, Q, p);
1614 0 : break;
1615 0 : case t_FF_F2xq:
1616 0 : r = F2xX_add(P, Q);
1617 0 : break;
1618 0 : default:
1619 0 : r = FlxX_add(P, Q, pp);
1620 : }
1621 0 : if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1622 0 : return gc_GEN(av, raw_to_FFX(r, ff));
1623 : }
1624 :
1625 : static GEN
1626 108816 : FFX_wrap2(GEN Pf, GEN Qf, GEN ff, GEN FpXQX(GEN, GEN, GEN, GEN),
1627 : GEN F2xqX(GEN, GEN, GEN), GEN FlxqX(GEN, GEN, GEN, ulong))
1628 : {
1629 108816 : pari_sp av = avma;
1630 : GEN r,T,p;
1631 : ulong pp;
1632 108816 : GEN P = FFX_to_raw(Pf, ff);
1633 108816 : GEN Q = FFX_to_raw(Qf, ff);
1634 108816 : _getFF(ff,&T,&p,&pp);
1635 108816 : switch(ff[1])
1636 : {
1637 2423 : case t_FF_FpXQ:
1638 2423 : r = FpXQX(P, Q, T, p);
1639 2423 : break;
1640 40526 : case t_FF_F2xq:
1641 40526 : r = F2xqX(P, Q, T);
1642 40526 : break;
1643 65867 : default:
1644 65867 : r = FlxqX(P, Q, T, pp);
1645 : }
1646 108816 : if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1647 106173 : return gc_GEN(av, raw_to_FFX(r, ff));
1648 : }
1649 :
1650 : GEN
1651 105477 : FFX_mul(GEN Pf, GEN Qf, GEN ff)
1652 105477 : { return FFX_wrap2(Pf, Qf, ff, FpXQX_mul, F2xqX_mul, FlxqX_mul); }
1653 :
1654 : GEN
1655 2744 : FFX_gcd(GEN Pf, GEN Qf, GEN ff)
1656 2744 : { return FFX_wrap2(Pf, Qf, ff, FpXQX_gcd, F2xqX_gcd, FlxqX_gcd); }
1657 :
1658 : GEN
1659 2499 : FFX_sqr(GEN Pf, GEN ff)
1660 : {
1661 2499 : pari_sp av = avma;
1662 : GEN r,T,p;
1663 : ulong pp;
1664 2499 : GEN P = FFX_to_raw(Pf, ff);
1665 2499 : _getFF(ff,&T,&p,&pp);
1666 2499 : switch(ff[1])
1667 : {
1668 210 : case t_FF_FpXQ:
1669 210 : r = FpXQX_sqr(P, T, p);
1670 210 : break;
1671 1071 : case t_FF_F2xq:
1672 1071 : r = F2xqX_sqr(P, T);
1673 1071 : break;
1674 1218 : default:
1675 1218 : r = FlxqX_sqr(P, T, pp);
1676 : }
1677 2499 : if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1678 2499 : return gc_GEN(av, raw_to_FFX(r, ff));
1679 : }
1680 :
1681 : GEN
1682 574 : FFX_rem(GEN Pf, GEN Qf, GEN ff)
1683 574 : { return FFX_wrap2(Pf, Qf, ff, FpXQX_rem, F2xqX_rem, FlxqX_rem); }
1684 :
1685 : GEN
1686 21 : FFX_resultant(GEN Pf, GEN Qf, GEN ff)
1687 : {
1688 21 : pari_sp av = avma;
1689 : GEN r,T,p;
1690 : ulong pp;
1691 21 : GEN P = FFX_to_raw(Pf, ff);
1692 21 : GEN Q = FFX_to_raw(Qf, ff);
1693 21 : GEN z = _initFF(ff,&T,&p,&pp);
1694 21 : switch(ff[1])
1695 : {
1696 7 : case t_FF_FpXQ:
1697 7 : r = FpXQX_resultant(P, Q, T, p);
1698 7 : break;
1699 7 : case t_FF_F2xq:
1700 7 : r = F2xqX_resultant(P, Q, T);
1701 7 : break;
1702 7 : default:
1703 7 : r = FlxqX_resultant(P, Q, T, pp);
1704 : }
1705 21 : return gc_upto(av, _mkFF(ff,z,r));
1706 : }
1707 :
1708 : GEN
1709 35 : FFX_disc(GEN Pf, GEN ff)
1710 : {
1711 35 : pari_sp av = avma;
1712 : GEN r,T,p;
1713 : ulong pp;
1714 35 : GEN P = FFX_to_raw(Pf, ff);
1715 35 : GEN z = _initFF(ff,&T,&p,&pp);
1716 35 : switch(ff[1])
1717 : {
1718 7 : case t_FF_FpXQ:
1719 7 : r = FpXQX_disc(P, T, p);
1720 7 : break;
1721 14 : case t_FF_F2xq:
1722 14 : r = F2xqX_disc(P, T);
1723 14 : break;
1724 14 : default:
1725 14 : r = FlxqX_disc(P, T, pp);
1726 : }
1727 35 : return gc_upto(av, _mkFF(ff,z,r));
1728 : }
1729 :
1730 : static GEN
1731 21 : gc_gcdext(pari_sp av, GEN r, GEN *u, GEN *v)
1732 : {
1733 21 : if (!u && !v) return gc_GEN(av, r);
1734 21 : if (u && v) return gc_all(av, 3, &r, u, v);
1735 0 : else return gc_all(av, 2, &r, u ? u: v);
1736 : }
1737 :
1738 : GEN
1739 21 : FFX_extgcd(GEN Pf, GEN Qf, GEN ff, GEN *pt_Uf, GEN *pt_Vf)
1740 : {
1741 21 : pari_sp av = avma;
1742 : GEN r,T,p;
1743 : ulong pp;
1744 21 : GEN P = FFX_to_raw(Pf, ff);
1745 21 : GEN Q = FFX_to_raw(Qf, ff);
1746 21 : _getFF(ff,&T,&p,&pp);
1747 21 : switch(ff[1])
1748 : {
1749 0 : case t_FF_FpXQ:
1750 0 : r = FpXQX_extgcd(P, Q, T, p, pt_Uf, pt_Vf);
1751 0 : break;
1752 7 : case t_FF_F2xq:
1753 7 : r = F2xqX_extgcd(P, Q, T, pt_Uf, pt_Vf);
1754 7 : break;
1755 14 : default:
1756 14 : r = FlxqX_extgcd(P, Q, T, pp, pt_Uf, pt_Vf);
1757 : }
1758 21 : if (pt_Uf) *pt_Uf = raw_to_FFX(*pt_Uf, ff);
1759 21 : if (pt_Vf) *pt_Vf = raw_to_FFX(*pt_Vf, ff);
1760 21 : return gc_gcdext(av, raw_to_FFX(r, ff), pt_Uf, pt_Vf);
1761 : }
1762 :
1763 : GEN
1764 0 : FFX_halfgcd(GEN Pf, GEN Qf, GEN ff)
1765 : {
1766 0 : pari_sp av = avma;
1767 : GEN r,T,p;
1768 : ulong pp;
1769 0 : GEN P = FFX_to_raw(Pf, ff);
1770 0 : GEN Q = FFX_to_raw(Qf, ff);
1771 0 : _getFF(ff,&T,&p,&pp);
1772 0 : switch(ff[1])
1773 : {
1774 0 : case t_FF_FpXQ:
1775 0 : r = FpXQX_halfgcd(P, Q, T, p);
1776 0 : break;
1777 0 : case t_FF_F2xq:
1778 0 : r = F2xqX_halfgcd(P, Q, T);
1779 0 : break;
1780 0 : default:
1781 0 : r = FlxqX_halfgcd(P, Q, T, pp);
1782 : }
1783 0 : return gc_GEN(av, raw_to_FFXM(r, ff));
1784 : }
1785 :
1786 : GEN
1787 21 : FFX_halfgcd_all(GEN Pf, GEN Qf, GEN ff, GEN *a, GEN *b)
1788 : {
1789 21 : pari_sp av = avma;
1790 : GEN r,T,p,R;
1791 : ulong pp;
1792 21 : GEN P = FFX_to_raw(Pf, ff);
1793 21 : GEN Q = FFX_to_raw(Qf, ff);
1794 21 : _getFF(ff,&T,&p,&pp);
1795 21 : switch(ff[1])
1796 : {
1797 7 : case t_FF_FpXQ:
1798 7 : r = FpXQX_halfgcd_all(P, Q, T, p, a, b);
1799 7 : break;
1800 7 : case t_FF_F2xq:
1801 7 : r = F2xqX_halfgcd_all(P, Q, T, a, b);
1802 7 : break;
1803 7 : default:
1804 7 : r = FlxqX_halfgcd_all(P, Q, T, pp, a, b);
1805 : }
1806 21 : if (*a) *a = raw_to_FFX(*a, ff);
1807 21 : if (*b) *b = raw_to_FFX(*b, ff);
1808 21 : R = raw_to_FFXM(r, ff);
1809 21 : return !a && b ? gc_all(av, 2, &R, b): gc_all(av, 1+!!a+!!b, &R, a, b);
1810 : }
1811 :
1812 : GEN
1813 7 : FFXQ_sqr(GEN Pf, GEN Qf, GEN ff)
1814 7 : { return FFX_wrap2(Pf, Qf, ff, FpXQXQ_sqr, F2xqXQ_sqr, FlxqXQ_sqr); }
1815 :
1816 : GEN
1817 14 : FFXQ_inv(GEN Pf, GEN Qf, GEN ff)
1818 14 : { return FFX_wrap2(Pf, Qf, ff, FpXQXQ_inv, F2xqXQ_inv, FlxqXQ_inv); }
1819 :
1820 : GEN
1821 105 : FFXQ_mul(GEN Pf, GEN Qf, GEN Sf, GEN ff)
1822 : {
1823 105 : pari_sp av = avma;
1824 : GEN r,T,p;
1825 : ulong pp;
1826 105 : GEN P = FFX_to_raw(Pf, ff);
1827 105 : GEN Q = FFX_to_raw(Qf, ff);
1828 105 : GEN S = FFX_to_raw(Sf, ff);
1829 105 : _getFF(ff,&T,&p,&pp);
1830 105 : switch(ff[1])
1831 : {
1832 28 : case t_FF_FpXQ:
1833 28 : r = FpXQXQ_mul(P, Q, S, T, p);
1834 28 : break;
1835 56 : case t_FF_F2xq:
1836 56 : r = F2xqXQ_mul(P, Q, S, T);
1837 56 : break;
1838 21 : default:
1839 21 : r = FlxqXQ_mul(P, Q, S, T, pp);
1840 : }
1841 105 : if (!lgpol(r)) { set_avma(av); return FFX_zero(ff, varn(Pf)); }
1842 105 : return gc_GEN(av, raw_to_FFX(r, ff));
1843 : }
1844 :
1845 : GEN
1846 77 : FFXQ_minpoly(GEN Pf, GEN Qf, GEN ff)
1847 : {
1848 77 : pari_sp av = avma;
1849 : GEN r,T,p;
1850 : ulong pp;
1851 77 : GEN P = FFX_to_raw(Pf, ff);
1852 77 : GEN Q = FFX_to_raw(Qf, ff);
1853 77 : _getFF(ff,&T,&p,&pp);
1854 77 : switch(ff[1])
1855 : {
1856 28 : case t_FF_FpXQ:
1857 28 : r = FpXQXQ_minpoly(P, Q, T, p);
1858 28 : break;
1859 28 : case t_FF_F2xq:
1860 28 : r = FlxX_to_F2xX(FlxqXQ_minpoly(F2xX_to_FlxX(P), F2xX_to_FlxX(Q), F2x_to_Flx(T), 2UL));
1861 28 : break;
1862 21 : default:
1863 21 : r = FlxqXQ_minpoly(P, Q, T, pp);
1864 : }
1865 77 : return gc_GEN(av, raw_to_FFX(r, ff));
1866 : }
1867 :
1868 : long
1869 168 : FFX_ispower(GEN Pf, long k, GEN ff, GEN *pt_r)
1870 : {
1871 168 : pari_sp av = avma;
1872 : GEN P,T,p;
1873 : ulong pp;
1874 : long s;
1875 168 : if (degpol(Pf) % k) return 0;
1876 168 : P = FFX_to_raw(Pf, ff);
1877 168 : _getFF(ff,&T,&p,&pp);
1878 168 : switch(ff[1])
1879 : {
1880 56 : case t_FF_FpXQ:
1881 56 : s = FpXQX_ispower(P, k, T, p, pt_r);
1882 56 : break;
1883 56 : case t_FF_F2xq:
1884 56 : s = F2xqX_ispower(P, k, T, pt_r);
1885 56 : break;
1886 56 : default:
1887 56 : s = FlxqX_ispower(P, k, T, pp, pt_r);
1888 : }
1889 168 : if (s==0) return gc_long(av,0);
1890 147 : if (pt_r)
1891 147 : *pt_r = gc_GEN(av, raw_to_FFX(*pt_r, ff));
1892 0 : else set_avma(av);
1893 147 : return 1;
1894 : }
1895 :
1896 : GEN
1897 441 : FFX_factor(GEN Pf, GEN ff)
1898 : {
1899 441 : pari_sp av = avma;
1900 : GEN r,T,p;
1901 : ulong pp;
1902 441 : GEN P = FFX_to_raw(Pf, ff);
1903 441 : _getFF(ff,&T,&p,&pp);
1904 441 : switch(ff[1])
1905 : {
1906 121 : case t_FF_FpXQ:
1907 121 : r = FpXQX_factor(P, T, p);
1908 121 : break;
1909 133 : case t_FF_F2xq:
1910 133 : r = F2xqX_factor(P, T);
1911 133 : break;
1912 187 : default:
1913 187 : r = FlxqX_factor(P, T, pp);
1914 : }
1915 441 : return gc_GEN(av, raw_to_FFX_fact(r, ff));
1916 : }
1917 :
1918 : GEN
1919 7 : FFX_factor_squarefree(GEN Pf, GEN ff)
1920 : {
1921 7 : pari_sp av = avma;
1922 : GEN r,T,p;
1923 : ulong pp;
1924 7 : GEN P = FFX_to_raw(Pf, ff);
1925 7 : _getFF(ff,&T,&p,&pp);
1926 7 : switch(ff[1])
1927 : {
1928 7 : case t_FF_FpXQ:
1929 7 : r = FpXQX_factor_squarefree(P, T, p);
1930 7 : break;
1931 0 : case t_FF_F2xq:
1932 0 : r = F2xqX_factor_squarefree(P, T);
1933 0 : break;
1934 0 : default:
1935 0 : r = FlxqX_factor_squarefree(P, T, pp);
1936 : }
1937 7 : return gc_GEN(av, raw_to_FFXC(r, ff));
1938 : }
1939 :
1940 : GEN
1941 7 : FFX_ddf(GEN Pf, GEN ff)
1942 : {
1943 7 : pari_sp av = avma;
1944 : GEN r,T,p;
1945 : ulong pp;
1946 7 : GEN P = FFX_to_raw(Pf, ff);
1947 7 : _getFF(ff,&T,&p,&pp);
1948 7 : switch(ff[1])
1949 : {
1950 7 : case t_FF_FpXQ:
1951 7 : r = FpXQX_ddf(P, T, p);
1952 7 : break;
1953 0 : case t_FF_F2xq:
1954 0 : r = F2xqX_ddf(P, T);
1955 0 : break;
1956 0 : default:
1957 0 : r = FlxqX_ddf(P, T, pp);
1958 : }
1959 7 : return gc_GEN(av, raw_to_FFX_fact(r, ff));
1960 : }
1961 :
1962 : GEN
1963 126 : FFX_degfact(GEN Pf, GEN ff)
1964 : {
1965 126 : pari_sp av = avma;
1966 : GEN r,T,p;
1967 : ulong pp;
1968 126 : GEN P = FFX_to_raw(Pf, ff);
1969 126 : _getFF(ff, &T, &p, &pp);
1970 126 : switch(ff[1])
1971 : {
1972 42 : case t_FF_FpXQ:
1973 42 : r = FpXQX_degfact(P, T, p);
1974 42 : break;
1975 42 : case t_FF_F2xq:
1976 42 : r = F2xqX_degfact(P, T);
1977 42 : break;
1978 42 : default:
1979 42 : r = FlxqX_degfact(P, T, pp);
1980 : }
1981 126 : return gc_GEN(av, r);
1982 : }
1983 :
1984 : GEN
1985 0 : FqX_to_FFX(GEN x, GEN ff)
1986 0 : { pari_APPLY_pol_normalized(Fq_to_FF(gel(x,i), ff)); }
1987 :
1988 : GEN
1989 3731 : FqC_to_FFC(GEN x, GEN ff)
1990 14434 : { pari_APPLY_type(t_COL, Fq_to_FF(gel(x,i), ff)) }
1991 :
1992 : GEN
1993 0 : FqV_to_FFV(GEN x, GEN ff)
1994 0 : { pari_APPLY_type(t_VEC, Fq_to_FF(gel(x,i), ff)) }
1995 :
1996 : GEN
1997 1715 : FqM_to_FFM(GEN x, GEN ff)
1998 5446 : { pari_APPLY_same(FqC_to_FFC(gel(x,i), ff)) }
1999 :
2000 : GEN
2001 3469 : ffgen(GEN T, long v)
2002 : {
2003 3469 : GEN A, p = NULL, ff = cgetg(5,t_FFELT);
2004 : long d;
2005 3470 : switch(typ(T))
2006 : {
2007 266 : case t_FFELT:
2008 266 : if (v < 0 || FF_var(T)==v) return FF_gen(T);
2009 0 : p = FF_p_i(T); T = FF_mod(T); d = degpol(T);
2010 0 : break;
2011 385 : case t_POL:
2012 385 : d = degpol(T); p = NULL;
2013 385 : if (d < 1 || !RgX_is_FpX(T, &p) || !p) pari_err_TYPE("ffgen",T);
2014 385 : T = RgX_to_FpX(T, p);
2015 : /* testing for irreducibility is too costly */
2016 385 : if (!FpX_is_squarefree(T,p)) pari_err_IRREDPOL("ffgen",T);
2017 378 : break;
2018 2049 : case t_INT:
2019 2049 : d = ispseudoprimepower(T,&p);
2020 2048 : if (!d) pari_err_PRIME("ffgen",T);
2021 2048 : T = init_Fq(p, d, v);
2022 2049 : break;
2023 770 : case t_VEC: case t_COL:
2024 770 : if (lg(T) == 3) {
2025 770 : p = gel(T,1);
2026 770 : A = gel(T,2);
2027 770 : if (typ(p) == t_INT && typ(A) == t_INT)
2028 : {
2029 770 : d = itos(A);
2030 770 : T = init_Fq(p, d, v);
2031 770 : break;
2032 : }
2033 : }
2034 : default:
2035 0 : pari_err_TYPE("ffgen",T);
2036 : return NULL;/* LCOV_EXCL_LINE */
2037 : }
2038 3197 : if (v < 0) v = varn(T);
2039 3197 : if (lgefint(p)==3)
2040 : {
2041 2821 : ulong pp = p[2];
2042 2821 : long sv = evalvarn(v);
2043 2821 : if (pp==2)
2044 : {
2045 1258 : ff[1] = t_FF_F2xq;
2046 1258 : T = ZX_to_F2x(T); T[1] = sv;
2047 1258 : A = polx_F2x(sv); if (d == 1) A = F2x_rem(A, T);
2048 1258 : p = gen_2;
2049 : }
2050 : else
2051 : {
2052 1563 : ff[1] = t_FF_Flxq;
2053 1563 : T = ZX_to_Flx(T,pp); T[1] = sv;
2054 1563 : A = polx_Flx(sv); if (d == 1) A = Flx_rem(A, T, pp);
2055 1563 : p = icopy(p);
2056 : }
2057 : }
2058 : else
2059 : {
2060 376 : ff[1] = t_FF_FpXQ;
2061 376 : setvarn(T,v);
2062 376 : A = pol_x(v); if (d == 1) A = FpX_rem(A, T, p);
2063 376 : p = icopy(p);
2064 : }
2065 3197 : gel(ff,2) = A;
2066 3197 : gel(ff,3) = T;
2067 3197 : gel(ff,4) = p; return ff;
2068 : }
2069 :
2070 : GEN
2071 9779 : p_to_FF(GEN p, long v)
2072 : {
2073 : GEN A, T;
2074 9779 : GEN ff = cgetg(5,t_FFELT);
2075 9779 : if (lgefint(p)==3)
2076 : {
2077 9778 : ulong pp = p[2];
2078 9778 : long sv = evalvarn(v);
2079 9778 : if (pp==2)
2080 : {
2081 385 : ff[1] = t_FF_F2xq;
2082 385 : T = polx_F2x(sv);
2083 385 : A = pol1_F2x(sv);
2084 385 : p = gen_2;
2085 : }
2086 : else
2087 : {
2088 9393 : ff[1] = t_FF_Flxq;
2089 9393 : T = polx_Flx(sv);
2090 9393 : A = pol1_Flx(sv);
2091 9393 : p = icopy(p);
2092 : }
2093 : }
2094 : else
2095 : {
2096 1 : ff[1] = t_FF_FpXQ;
2097 1 : T = pol_x(v);
2098 1 : A = pol_1(v);
2099 1 : p = icopy(p);
2100 : }
2101 9779 : gel(ff,2) = A;
2102 9779 : gel(ff,3) = T;
2103 9779 : gel(ff,4) = p; return ff;
2104 : }
2105 : GEN
2106 8225 : Tp_to_FF(GEN T, GEN p)
2107 : {
2108 : GEN A, ff;
2109 : long v;
2110 8225 : if (!T) return p_to_FF(p,0);
2111 8148 : ff = cgetg(5,t_FFELT);
2112 8148 : v = varn(T);
2113 8148 : if (lgefint(p)==3)
2114 : {
2115 7929 : ulong pp = p[2];
2116 7929 : long sv = evalvarn(v);
2117 7929 : if (pp==2)
2118 : {
2119 1925 : ff[1] = t_FF_F2xq;
2120 1925 : T = ZX_to_F2x(T);
2121 1925 : A = pol1_F2x(sv);
2122 1925 : p = gen_2;
2123 : }
2124 : else
2125 : {
2126 6004 : ff[1] = t_FF_Flxq;
2127 6004 : T = ZX_to_Flx(T, pp);
2128 6004 : A = pol1_Flx(sv);
2129 6004 : p = icopy(p);
2130 : }
2131 : }
2132 : else
2133 : {
2134 219 : ff[1] = t_FF_FpXQ;
2135 219 : T = ZX_copy(T);
2136 219 : A = pol_1(v);
2137 219 : p = icopy(p);
2138 : }
2139 8148 : gel(ff,2) = A;
2140 8148 : gel(ff,3) = T;
2141 8148 : gel(ff,4) = p; return ff;
2142 : }
2143 :
2144 : GEN
2145 63 : fforder(GEN x, GEN o)
2146 : {
2147 63 : if (typ(x)!=t_FFELT) pari_err_TYPE("fforder",x);
2148 63 : if (FF_equal0(x)) pari_err_DOMAIN("fforder", "x", "=", gen_0, x);
2149 56 : return FF_order(x,o);
2150 : }
2151 :
2152 : GEN
2153 406 : ffprimroot(GEN x, GEN *o)
2154 : {
2155 406 : if (typ(x)!=t_FFELT) pari_err_TYPE("ffprimroot",x);
2156 406 : return FF_primroot(x,o);
2157 : }
2158 :
2159 : GEN
2160 196 : fflog(GEN x, GEN g, GEN o)
2161 : {
2162 196 : if (typ(x)!=t_FFELT) pari_err_TYPE("fflog",x);
2163 196 : if (typ(g)!=t_FFELT) pari_err_TYPE("fflog",g);
2164 196 : return FF_log(x,g,o);
2165 : }
2166 :
2167 : GEN
2168 184493 : ffrandom(GEN ff)
2169 : {
2170 : ulong pp;
2171 184493 : GEN r, T, p, z = _initFF(ff,&T,&p,&pp);
2172 184493 : switch(ff[1])
2173 : {
2174 10000 : case t_FF_FpXQ:
2175 10000 : r = random_FpX(degpol(T), varn(T), p);
2176 10000 : break;
2177 117271 : case t_FF_F2xq:
2178 117271 : r = random_F2x(F2x_degree(T), T[1]);
2179 117271 : break;
2180 57222 : default:
2181 57222 : r = random_Flx(degpol(T), T[1], pp);
2182 : }
2183 184493 : return _mkFF(ff,z,r);
2184 : }
2185 :
2186 : int
2187 0 : Rg_is_FF(GEN c, GEN *ff)
2188 : {
2189 0 : switch(typ(c))
2190 : {
2191 0 : case t_FFELT:
2192 0 : if (!*ff) *ff = c;
2193 0 : else if (!FF_samefield(*ff, c)) return 0;
2194 0 : break;
2195 0 : default:
2196 0 : return 0;
2197 : }
2198 0 : return 1;
2199 : }
2200 :
2201 : int
2202 0 : RgC_is_FFC(GEN x, GEN *ff)
2203 : {
2204 0 : long i, lx = lg(x);
2205 0 : for (i=lx-1; i>0; i--)
2206 0 : if (!Rg_is_FF(gel(x,i), ff)) return 0;
2207 0 : return (*ff != NULL);
2208 : }
2209 :
2210 : int
2211 0 : RgM_is_FFM(GEN x, GEN *ff)
2212 : {
2213 0 : long j, lx = lg(x);
2214 0 : for (j=lx-1; j>0; j--)
2215 0 : if (!RgC_is_FFC(gel(x,j), ff)) return 0;
2216 0 : return (*ff != NULL);
2217 : }
2218 :
2219 : static GEN
2220 3436 : FqC_to_FpXQC(GEN x, GEN T, GEN p)
2221 54891 : { pari_APPLY_same(Fq_to_FpXQ(gel(x,i), T, p)); }
2222 :
2223 : static GEN
2224 476 : FqM_to_FpXQM(GEN x, GEN T, GEN p)
2225 3835 : { pari_APPLY_same(FqC_to_FpXQC(gel(x,i), T, p)); }
2226 :
2227 : /* for functions t_MAT -> t_MAT */
2228 : static GEN
2229 308 : FFM_wrap(GEN M, GEN ff, GEN (*Fq)(GEN,GEN,GEN),
2230 : GEN (*Flxq)(GEN,GEN,ulong),
2231 : GEN (*F2xq)(GEN,GEN))
2232 : {
2233 308 : pari_sp av = avma;
2234 : ulong pp;
2235 : GEN T, p;
2236 308 : _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2237 308 : switch(ff[1])
2238 : {
2239 119 : case t_FF_FpXQ: M = Fq(M,T,p); if (M) M = FqM_to_FpXQM(M,T,p);
2240 119 : break;
2241 70 : case t_FF_F2xq: M = F2xq(M,T); break;
2242 119 : default: M = Flxq(M,T,pp); break;
2243 : }
2244 308 : if (!M) return gc_NULL(av);
2245 273 : return gc_GEN(av, raw_to_FFM(M, ff));
2246 : }
2247 :
2248 : /* for functions (t_MAT, t_MAT) -> t_MAT */
2249 : static GEN
2250 4662 : FFM_FFM_wrap(GEN M, GEN N, GEN ff,
2251 : GEN (*Fq)(GEN, GEN, GEN, GEN),
2252 : GEN (*Flxq)(GEN, GEN, GEN, ulong),
2253 : GEN (*F2xq)(GEN, GEN, GEN))
2254 : {
2255 4662 : pari_sp av = avma;
2256 : ulong pp;
2257 : GEN T, p;
2258 4662 : int is_sqr = M==N;
2259 4662 : _getFF(ff, &T, &p, &pp);
2260 4662 : M = FFM_to_raw(M, ff);
2261 4662 : N = is_sqr? M: FFM_to_raw(N, ff);
2262 4662 : switch(ff[1])
2263 : {
2264 406 : case t_FF_FpXQ: M = Fq(M, N, T, p); if (M) M = FqM_to_FpXQM(M, T, p);
2265 406 : break;
2266 1491 : case t_FF_F2xq: M = F2xq(M, N, T); break;
2267 2765 : default: M = Flxq(M, N, T, pp); break;
2268 : }
2269 4662 : if (!M) return gc_NULL(av);
2270 4571 : return gc_GEN(av, raw_to_FFM(M, ff));
2271 : }
2272 :
2273 : /* for functions (t_MAT, t_COL) -> t_COL */
2274 : static GEN
2275 210 : FFM_FFC_wrap(GEN M, GEN C, GEN ff,
2276 : GEN (*Fq)(GEN, GEN, GEN, GEN),
2277 : GEN (*Flxq)(GEN, GEN, GEN, ulong),
2278 : GEN (*F2xq)(GEN, GEN, GEN))
2279 : {
2280 210 : pari_sp av = avma;
2281 : ulong pp;
2282 : GEN T, p;
2283 210 : _getFF(ff, &T, &p, &pp);
2284 210 : M = FFM_to_raw(M, ff);
2285 210 : C = FFC_to_raw(C, ff);
2286 210 : switch(ff[1])
2287 : {
2288 70 : case t_FF_FpXQ: C = Fq(M, C, T, p); if (C) C = FqC_to_FpXQC(C, T, p);
2289 70 : break;
2290 70 : case t_FF_F2xq: C = F2xq(M, C, T); break;
2291 70 : default: C = Flxq(M, C, T, pp); break;
2292 : }
2293 210 : if (!C) return gc_NULL(av);
2294 161 : return gc_GEN(av, raw_to_FFC(C, ff));
2295 : }
2296 :
2297 : GEN
2298 77 : FFM_ker(GEN M, GEN ff)
2299 77 : { return FFM_wrap(M,ff, &FqM_ker,&FlxqM_ker,&F2xqM_ker); }
2300 : GEN
2301 49 : FFM_image(GEN M, GEN ff)
2302 49 : { return FFM_wrap(M,ff, &FqM_image,&FlxqM_image,&F2xqM_image); }
2303 : GEN
2304 147 : FFM_inv(GEN M, GEN ff)
2305 147 : { return FFM_wrap(M,ff, &FqM_inv,&FlxqM_inv,&F2xqM_inv); }
2306 : GEN
2307 35 : FFM_suppl(GEN M, GEN ff)
2308 35 : { return FFM_wrap(M,ff, &FqM_suppl,&FlxqM_suppl,&F2xqM_suppl); }
2309 :
2310 : GEN
2311 84 : FFM_deplin(GEN M, GEN ff)
2312 : {
2313 84 : pari_sp av = avma;
2314 : ulong pp;
2315 : GEN C, T, p;
2316 84 : _getFF(ff, &T, &p, &pp); M = FFM_to_raw(M, ff);
2317 84 : switch(ff[1]) {
2318 35 : case t_FF_FpXQ: C = FqM_deplin(M, T, p);
2319 35 : if (C) C = FqC_to_FpXQC(C, T, p); break;
2320 14 : case t_FF_F2xq: C = F2xqM_deplin(M, T); break;
2321 35 : default: C = FlxqM_deplin(M, T, pp); break;
2322 : }
2323 84 : if (!C) return gc_NULL(av);
2324 49 : return gc_GEN(av, raw_to_FFC(C, ff));
2325 : }
2326 :
2327 : GEN
2328 21 : FFM_indexrank(GEN M, GEN ff)
2329 : {
2330 21 : pari_sp av = avma;
2331 : ulong pp;
2332 : GEN R, T, p;
2333 21 : _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2334 21 : switch(ff[1]) {
2335 7 : case t_FF_FpXQ: R = FqM_indexrank(M,T,p); break;
2336 7 : case t_FF_F2xq: R = F2xqM_indexrank(M,T); break;
2337 7 : default: R = FlxqM_indexrank(M,T,pp); break;
2338 : }
2339 21 : return gc_upto(av, R);
2340 : }
2341 :
2342 : long
2343 70 : FFM_rank(GEN M, GEN ff)
2344 : {
2345 70 : pari_sp av = avma;
2346 : long r;
2347 : ulong pp;
2348 : GEN T, p;
2349 70 : _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2350 70 : switch(ff[1])
2351 : {
2352 28 : case t_FF_FpXQ: r = FqM_rank(M,T,p); break;
2353 7 : case t_FF_F2xq: r = F2xqM_rank(M,T); break;
2354 35 : default: r = FlxqM_rank(M,T,pp); break;
2355 : }
2356 70 : return gc_long(av,r);
2357 : }
2358 : GEN
2359 63 : FFM_det(GEN M, GEN ff)
2360 : {
2361 63 : pari_sp av = avma;
2362 : ulong pp;
2363 : GEN d, T, p;
2364 63 : _getFF(ff,&T,&p,&pp); M = FFM_to_raw(M, ff);
2365 63 : switch(ff[1])
2366 : {
2367 28 : case t_FF_FpXQ: d = FqM_det(M,T,p); break;
2368 7 : case t_FF_F2xq: d = F2xqM_det(M,T); break;
2369 28 : default: d = FlxqM_det(M,T,pp); break;
2370 : }
2371 63 : return gc_GEN(av, mkFF_i(ff, d));
2372 : }
2373 :
2374 : GEN
2375 56 : FFM_FFC_gauss(GEN M, GEN C, GEN ff)
2376 : {
2377 56 : return FFM_FFC_wrap(M, C, ff, FqM_FqC_gauss,
2378 : FlxqM_FlxqC_gauss, F2xqM_F2xqC_gauss);
2379 : }
2380 :
2381 : GEN
2382 63 : FFM_gauss(GEN M, GEN N, GEN ff)
2383 : {
2384 63 : return FFM_FFM_wrap(M, N, ff, FqM_gauss,
2385 : FlxqM_gauss, F2xqM_gauss);
2386 : }
2387 :
2388 : GEN
2389 63 : FFM_FFC_invimage(GEN M, GEN C, GEN ff)
2390 : {
2391 63 : return FFM_FFC_wrap(M, C, ff, FqM_FqC_invimage,
2392 : FlxqM_FlxqC_invimage, F2xqM_F2xqC_invimage);
2393 : }
2394 :
2395 : GEN
2396 105 : FFM_invimage(GEN M, GEN N, GEN ff)
2397 : {
2398 105 : return FFM_FFM_wrap(M, N, ff, FqM_invimage,
2399 : FlxqM_invimage, F2xqM_invimage);
2400 : }
2401 :
2402 : GEN
2403 91 : FFM_FFC_mul(GEN M, GEN C, GEN ff)
2404 : {
2405 91 : return FFM_FFC_wrap(M, C, ff, FqM_FqC_mul,
2406 : FlxqM_FlxqC_mul, F2xqM_F2xqC_mul);
2407 : }
2408 :
2409 : GEN
2410 4494 : FFM_mul(GEN M, GEN N, GEN ff)
2411 : {
2412 4494 : return FFM_FFM_wrap(M, N, ff, FqM_mul, FlxqM_mul, F2xqM_mul);
2413 : }
2414 :
2415 : GEN
2416 14 : FFV_roots_to_pol(GEN V, GEN ff, long v)
2417 : {
2418 14 : pari_sp av = avma;
2419 : ulong pp;
2420 : GEN P, T, p;
2421 14 : long w = fetch_var_higher();
2422 14 : _getFF(ff,&T,&p,&pp); V = FFC_to_raw(V, ff);
2423 14 : switch(ff[1])
2424 : {
2425 0 : case t_FF_FpXQ: P = FqV_roots_to_pol(V, T, p, w); break;
2426 7 : case t_FF_F2xq: P = F2xqV_roots_to_pol(V, T, w); break;
2427 7 : default: P = FlxqV_roots_to_pol(V, T, pp, w); break;
2428 : }
2429 14 : if (!P) return gc_NULL(av);
2430 14 : P = raw_to_FFX(P, ff);
2431 14 : setvarn(P, v);
2432 14 : delete_var();
2433 14 : return gc_GEN(av, P);
2434 : }
|
