Code coverage tests

This page documents the degree to which the PARI/GP source code is tested by our public test suite, distributed with the source distribution in directory src/test/. This is measured by the gcov utility; we then process gcov output using the lcov frond-end.

We test a few variants depending on Configure flags on the pari.math.u-bordeaux.fr machine (x86_64 architecture), and agregate them in the final report:

The target is 90% coverage for all mathematical modules (given that branches depending on DEBUGLEVEL or DEBUGMEM are not covered). This script is run to produce the results below.

LCOV - code coverage report
Current view: top level - basemath - FpV.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 20277-2bd9113) Lines: 628 834 75.3 %
Date: 2017-02-21 05:49:51 Functions: 89 116 76.7 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  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. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : 
      14             : #include "pari.h"
      15             : #include "paripriv.h"
      16             : 
      17             : /********************************************************************/
      18             : /**                                                                **/
      19             : /**                           REDUCTION                            **/
      20             : /**                                                                **/
      21             : /********************************************************************/
      22             : /* z in Z^n, return lift(Col(z) * Mod(1,p)) */
      23             : GEN
      24     4484419 : FpC_red(GEN z, GEN p)
      25             : {
      26     4484419 :   long i,l = lg(z);
      27     4484419 :   GEN x = cgetg(l, t_COL);
      28     4484419 :   for (i=1; i<l; i++) gel(x,i) = modii(gel(z,i),p);
      29     4484419 :   return x;
      30             : }
      31             : 
      32             : /* z in Z^n, return lift(Vec(z) * Mod(1,p)) */
      33             : GEN
      34      202013 : FpV_red(GEN z, GEN p)
      35             : {
      36      202013 :   long i,l = lg(z);
      37      202013 :   GEN x = cgetg(l, t_VEC);
      38      202013 :   for (i=1; i<l; i++) gel(x,i) = modii(gel(z,i),p);
      39      202013 :   return x;
      40             : }
      41             : GEN
      42      181874 : FpC_center(GEN z, GEN p, GEN pov2)
      43             : {
      44      181874 :   long i,l = lg(z);
      45      181874 :   GEN x = cgetg(l, t_COL);
      46      181874 :   for (i=1; i<l; i++) gel(x,i) = Fp_center(gel(z,i),p, pov2);
      47      181874 :   return x;
      48             : }
      49             : 
      50             : /* assume 0 <= u < p and ps2 = p>>1 */
      51             : INLINE void
      52          28 : Fp_center_inplace(GEN u, GEN p, GEN ps2)
      53          28 : { if (abscmpii(u,ps2) > 0) subiiz(u,p,u); }
      54             : 
      55             : void
      56          14 : FpC_center_inplace(GEN z, GEN p, GEN ps2)
      57             : {
      58          14 :   long i,l = lg(z);
      59          42 :   for (i=1; i<l; i++)
      60          28 :     Fp_center_inplace(gel(z,i), p, ps2);
      61          14 : }
      62             : 
      63             : GEN
      64      111678 : Flv_center(GEN z, ulong p, ulong ps2)
      65             : {
      66      111678 :   long i, l = lg(z);
      67      111678 :   GEN x = cgetg(l,t_VECSMALL);
      68      111678 :   for (i=1; i<l; i++) x[i] = Fl_center(z[i],p,ps2);
      69      111678 :   return x;
      70             : }
      71             : 
      72             : /* z in Mat m,n(Z), return lift(z * Mod(1,p)) */
      73             : GEN
      74      496096 : FpM_red(GEN z, GEN p)
      75             : {
      76      496096 :   long i, l = lg(z);
      77      496096 :   GEN x = cgetg(l,t_MAT);
      78      496096 :   for (i=1; i<l; i++) gel(x,i) = FpC_red(gel(z,i), p);
      79      496096 :   return x;
      80             : }
      81             : GEN
      82       49805 : FpM_center(GEN z, GEN p, GEN pov2)
      83             : {
      84       49805 :   long i, l = lg(z);
      85       49805 :   GEN x = cgetg(l,t_MAT);
      86       49805 :   for (i=1; i<l; i++) gel(x,i) = FpC_center(gel(z,i), p, pov2);
      87       49805 :   return x;
      88             : }
      89             : 
      90             : void
      91          14 : FpM_center_inplace(GEN z, GEN p, GEN pov2)
      92             : {
      93          14 :   long i, l = lg(z);
      94          14 :   for (i=1; i<l; i++) FpC_center_inplace(gel(z,i), p, pov2);
      95          14 : }
      96             : GEN
      97        7896 : Flm_center(GEN z, ulong p, ulong ps2)
      98             : {
      99        7896 :   long i, l = lg(z);
     100        7896 :   GEN x = cgetg(l,t_MAT);
     101        7896 :   for (i=1; i<l; i++) gel(x,i) = Flv_center(gel(z,i),p,ps2);
     102        7896 :   return x;
     103             : }
     104             : 
     105             : /********************************************************************/
     106             : /**                                                                **/
     107             : /**                           ADD, SUB                             **/
     108             : /**                                                                **/
     109             : /********************************************************************/
     110             : GEN
     111      391965 : FpC_add(GEN x, GEN y, GEN p)
     112             : {
     113      391965 :   long i, lx = lg(x);
     114      391965 :   GEN z = cgetg(lx, t_COL);
     115      391965 :   for (i = 1; i < lx; i++) gel(z, i) = Fp_add(gel(x, i), gel(y, i), p);
     116      391965 :   return z;
     117             : }
     118             : GEN
     119           0 : FpV_add(GEN x, GEN y, GEN p)
     120             : {
     121           0 :   long i, lx = lg(x);
     122           0 :   GEN z = cgetg(lx, t_VEC);
     123           0 :   for (i = 1; i < lx; i++) gel(z, i) = Fp_add(gel(x, i), gel(y, i), p);
     124           0 :   return z;
     125             : }
     126             : GEN
     127           0 : FpM_add(GEN x, GEN y, GEN p)
     128             : {
     129           0 :   long lx = lg(x), j;
     130             :   GEN z;
     131           0 :   if (lx == 1) return cgetg(1, t_MAT);
     132           0 :   z = cgetg(lx, t_MAT);
     133           0 :   for (j = 1; j < lx; j++) gel(z,j) = FpC_add(gel(x,j), gel(y,j), p);
     134           0 :   return z;
     135             : }
     136             : 
     137             : GEN
     138      945574 : Flv_add(GEN x, GEN y, ulong p)
     139             : {
     140      945574 :   long i, l = lg(x);
     141      945574 :   GEN z = cgetg(l, t_VECSMALL);
     142      945574 :   if (p==2)
     143       41818 :     for (i = 1; i < l; i++) z[i] = x[i]^y[i];
     144             :   else
     145      903756 :     for (i = 1; i < l; i++) z[i] = Fl_add(x[i], y[i], p);
     146      945574 :   return z;
     147             : }
     148             : 
     149             : void
     150      160812 : Flv_add_inplace(GEN x, GEN y, ulong p)
     151             : {
     152      160812 :   long i, l = lg(x);
     153      160812 :   if (p==2)
     154      158712 :     for (i = 1; i < l; i++) x[i] ^= y[i];
     155             :   else
     156        2100 :     for (i = 1; i < l; i++) x[i] = Fl_add(x[i], y[i], p);
     157      160812 : }
     158             : 
     159             : ulong
     160        3822 : Flv_sum(GEN x, ulong p)
     161             : {
     162        3822 :   long i, l = lg(x);
     163        3822 :   ulong s = 0;
     164        3822 :   if (p==2)
     165        3822 :     for (i = 1; i < l; i++) s ^= x[i];
     166             :   else
     167           0 :     for (i = 1; i < l; i++) s = Fl_add(s, x[i], p);
     168        3822 :   return s;
     169             : }
     170             : 
     171             : GEN
     172      337910 : FpC_sub(GEN x, GEN y, GEN p)
     173             : {
     174      337910 :   long i, lx = lg(x);
     175      337910 :   GEN z = cgetg(lx, t_COL);
     176      337910 :   for (i = 1; i < lx; i++) gel(z, i) = Fp_sub(gel(x, i), gel(y, i), p);
     177      337910 :   return z;
     178             : }
     179             : GEN
     180           0 : FpV_sub(GEN x, GEN y, GEN p)
     181             : {
     182           0 :   long i, lx = lg(x);
     183           0 :   GEN z = cgetg(lx, t_VEC);
     184           0 :   for (i = 1; i < lx; i++) gel(z, i) = Fp_sub(gel(x, i), gel(y, i), p);
     185           0 :   return z;
     186             : }
     187             : 
     188             : GEN
     189           0 : FpM_sub(GEN x, GEN y, GEN p)
     190             : {
     191           0 :   long i, l = lg(x);
     192           0 :   GEN z = cgetg(l, t_MAT);
     193           0 :   for (i = 1; i < l; i++) gel(z, i) = FpC_sub(gel(x, i), gel(y, i), p);
     194           0 :   return z;
     195             : }
     196             : 
     197             : GEN
     198         301 : Flv_sub(GEN x, GEN y, ulong p)
     199             : {
     200         301 :   long i, l = lg(x);
     201         301 :   GEN z = cgetg(l, t_VECSMALL);
     202         301 :   for (i = 1; i < l; i++) z[i] = Fl_sub(x[i], y[i], p);
     203         301 :   return z;
     204             : }
     205             : 
     206             : void
     207           0 : Flv_sub_inplace(GEN x, GEN y, ulong p)
     208             : {
     209           0 :   long i, l = lg(x);
     210           0 :   for (i = 1; i < l; i++) x[i] = Fl_sub(x[i], y[i], p);
     211           0 : }
     212             : 
     213             : GEN
     214        7084 : Flm_Fl_add(GEN x, ulong y, ulong p)
     215             : {
     216        7084 :   long l = lg(x), i, j;
     217        7084 :   GEN z = cgetg(l,t_MAT);
     218             : 
     219        7084 :   if (l==1) return z;
     220        7084 :   if (l != lgcols(x)) pari_err_OP( "+", x, utoi(y));
     221       29281 :   for (i=1; i<l; i++)
     222             :   {
     223       22197 :     GEN zi = cgetg(l,t_VECSMALL), xi = gel(x,i);
     224       22197 :     gel(z,i) = zi;
     225       22197 :     for (j=1; j<l; j++) zi[j] = xi[j];
     226       22197 :     zi[i] = Fl_add(zi[i], y, p);
     227             :   }
     228        7084 :   return z;
     229             : }
     230             : 
     231             : GEN
     232       14665 : Flm_add(GEN x, GEN y, ulong p)
     233             : {
     234       14665 :   long i, l = lg(x);
     235       14665 :   GEN z = cgetg(l,t_MAT);
     236       14665 :   for (i = 1; i < l; i++) gel(z,i) = Flv_add(gel(x,i),gel(y,i),p);
     237       14665 :   return z;
     238             : }
     239             : 
     240             : GEN
     241           0 : Flm_sub(GEN x, GEN y, ulong p)
     242             : {
     243           0 :   long i, l = lg(x);
     244           0 :   GEN z = cgetg(l, t_MAT);
     245           0 :   for (i = 1; i < l; i++) gel(z, i) = Flv_sub(gel(x, i), gel(y, i), p);
     246           0 :   return z;
     247             : }
     248             : 
     249             : /********************************************************************/
     250             : /**                                                                **/
     251             : /**                           MULTIPLICATION                       **/
     252             : /**                                                                **/
     253             : /********************************************************************/
     254             : GEN
     255     1046801 : FpC_Fp_mul(GEN x, GEN y, GEN p)
     256             : {
     257     1046801 :   long i, l = lg(x);
     258     1046801 :   GEN z = cgetg(l, t_COL);
     259     1046801 :   for (i=1;i<l;i++) gel(z,i) = Fp_mul(gel(x,i),y,p);
     260     1046801 :   return z;
     261             : }
     262             : GEN
     263      762532 : Flv_Fl_mul(GEN x, ulong y, ulong p)
     264             : {
     265      762532 :   long i, l = lg(x);
     266      762532 :   GEN z = cgetg(l, t_VECSMALL);
     267      762532 :   for (i=1;i<l;i++) z[i] = Fl_mul(x[i], y, p);
     268      762532 :   return z;
     269             : }
     270             : GEN
     271        2849 : Flv_Fl_div(GEN x, ulong y, ulong p)
     272             : {
     273        2849 :   return Flv_Fl_mul(x, Fl_inv(y, p), p);
     274             : }
     275             : void
     276           0 : Flv_Fl_div_inplace(GEN x, ulong y, ulong p)
     277             : {
     278           0 :   Flv_Fl_mul_inplace(x, Fl_inv(y, p), p);
     279           0 : }
     280             : GEN
     281           0 : FpM_Fp_mul(GEN X, GEN c, GEN p) {
     282           0 :   long i, j, h, l = lg(X);
     283           0 :   GEN A = cgetg(l, t_MAT);
     284           0 :   if (l == 1) return A;
     285           0 :   h = lgcols(X);
     286           0 :   for (j=1; j<l; j++)
     287             :   {
     288           0 :     GEN a = cgetg(h, t_COL), x = gel(X, j);
     289           0 :     for (i = 1; i < h; i++) gel(a,i) = Fp_mul(gel(x,i), c, p);
     290           0 :     gel(A,j) = a;
     291             :   }
     292           0 :   return A;
     293             : }
     294             : 
     295             : /* x *= y */
     296             : void
     297     1552450 : Flv_Fl_mul_part_inplace(GEN x, ulong y, ulong p, long l)
     298             : {
     299             :   long i;
     300     1552450 :   for (i=1;i<=l;i++) x[i] = Fl_mul(x[i], y, p);
     301     1552450 : }
     302             : void
     303           0 : Flv_Fl_mul_inplace(GEN x, ulong y, ulong p)
     304           0 : { Flv_Fl_mul_part_inplace(x, y, p, lg(x)-1); }
     305             : 
     306             : /* set y *= x */
     307             : void
     308       25574 : Flm_Fl_mul_inplace(GEN y, ulong x, ulong p)
     309             : {
     310       25574 :   long i, j, m, l = lg(y);
     311       51148 :   if (l == 1) return;
     312       25574 :   m = lgcols(y);
     313       25574 :   if (HIGHWORD(x | p))
     314      250487 :     for(j=1; j<l; j++)
     315      224913 :       for(i=1; i<m; i++) ucoeff(y,i,j) = Fl_mul(ucoeff(y,i,j), x, p);
     316             :   else
     317           0 :     for(j=1; j<l; j++)
     318           0 :       for(i=1; i<m; i++) ucoeff(y,i,j) = (ucoeff(y,i,j) * x) % p;
     319             : }
     320             : 
     321             : /* return x * y */
     322             : GEN
     323       34293 : Flm_Fl_mul(GEN y, ulong x, ulong p)
     324             : {
     325       34293 :   long i, j, m, l = lg(y);
     326       34293 :   GEN z = cgetg(l, t_MAT);
     327       34293 :   if (l == 1) return z;
     328       34293 :   m = lgcols(y);
     329       34293 :   if (HIGHWORD(x | p))
     330           0 :     for(j=1; j<l; j++) {
     331           0 :       GEN c = cgetg(m, t_VECSMALL); gel(z,j) = c;
     332           0 :       for(i=1; i<m; i++) c[i] = Fl_mul(ucoeff(y,i,j), x, p);
     333             :     }
     334             :   else
     335      759542 :     for(j=1; j<l; j++) {
     336      725249 :       GEN c = cgetg(m, t_VECSMALL); gel(z,j) = c;
     337      725249 :       for(i=1; i<m; i++) c[i] = (ucoeff(y,i,j) * x) % p;
     338             :     }
     339       34293 :   return z;
     340             : }
     341             : 
     342             : GEN
     343          56 : Flv_neg(GEN v, ulong p)
     344             : {
     345          56 :   long i, m = lg(v);
     346          56 :   GEN c = cgetg(m, t_VECSMALL);
     347          56 :   for(i=1; i<m; i++) uel(c,i) = Fl_neg(uel(v,i), p);
     348          56 :   return c;
     349             : }
     350             : 
     351             : void
     352        3347 : Flv_neg_inplace(GEN v, ulong p)
     353             : {
     354             :   long i;
     355      148441 :   for (i = 1; i < lg(v); ++i)
     356      145094 :     v[i] = Fl_neg(v[i], p);
     357        3347 : }
     358             : 
     359             : GEN
     360          21 : Flm_neg(GEN y, ulong p)
     361             : {
     362          21 :   long j, l = lg(y);
     363          21 :   GEN z = cgetg(l, t_MAT);
     364          77 :   for(j=1; j<l; j++)
     365          56 :     gel(z,j) = Flv_neg(gel(y,j), p);
     366          21 :   return z;
     367             : }
     368             : 
     369             : /* x[i,]*y. Assume lx > 1 and 0 < i < lgcols(x) */
     370             : static GEN
     371    15556069 : ZMrow_ZC_mul_i(GEN x, GEN y, long lx, long i)
     372             : {
     373    15556069 :   GEN c = mulii(gcoeff(x,i,1), gel(y,1));
     374             :   long k;
     375   314296102 :   for (k = 2; k < lx; k++)
     376             :   {
     377   298740033 :     GEN t = mulii(gcoeff(x,i,k), gel(y,k));
     378   298740033 :     if (signe(t)) c = addii(c, t);
     379             :   }
     380    15556069 :   return c;
     381             : }
     382             : 
     383             : static long
     384    21635523 : zmrow_zc_mul(GEN x, GEN y, long lx, long i)
     385             : {
     386             :   long k;
     387    21635523 :   long c = coeff(x,i,1) * y[1];
     388   289227596 :   for (k = 2; k < lx; k++)
     389   267592073 :     c += coeff(x,i,k) * y[k];
     390    21635523 :   return c;
     391             : }
     392             : 
     393             : GEN
     394     1653225 : zm_zc_mul(GEN x, GEN y)
     395             : {
     396     1653225 :   long lx = lg(x), l, i;
     397             :   GEN z;
     398     1653225 :   if (lx == 1) return cgetg(1, t_VECSMALL);
     399     1653225 :   l = lg(gel(x,1));
     400     1653225 :   z = cgetg(l,t_VECSMALL);
     401     1653225 :   for (i=1; i<l; i++) z[i] = zmrow_zc_mul(x, y, lx, i);
     402     1653225 :   return z;
     403             : }
     404             : 
     405             : GEN
     406         252 : zm_mul(GEN x, GEN y)
     407             : {
     408         252 :   long i,j,lx=lg(x), ly=lg(y);
     409             :   GEN z;
     410         252 :   if (ly==1) return cgetg(1,t_MAT);
     411         252 :   z = cgetg(ly,t_MAT);
     412         252 :   if (lx==1)
     413             :   {
     414           0 :     for (i=1; i<ly; i++) gel(z,i) = cgetg(1,t_VECSMALL);
     415           0 :     return z;
     416             :   }
     417        2128 :   for (j=1; j<ly; j++)
     418        1876 :     gel(z,j) = zm_zc_mul(x, gel(y,j));
     419         252 :   return z;
     420             : }
     421             : 
     422             : static ulong
     423   180976785 : Flmrow_Flc_mul_SMALL(GEN x, GEN y, ulong p, long lx, long i)
     424             : {
     425   180976785 :   ulong c = ucoeff(x,i,1) * uel(y,1);
     426             :   long k;
     427  5855171043 :   for (k = 2; k < lx; k++) {
     428  5674194258 :     c += ucoeff(x,i,k) * uel(y,k);
     429  5674194258 :     if (c & HIGHBIT) c %= p;
     430             :   }
     431   180976785 :   return c % p;
     432             : }
     433             : 
     434             : static ulong
     435    48740948 : Flmrow_Flc_mul_i(GEN x, GEN y, ulong p, ulong pi, long lx, long i)
     436             : {
     437             :   ulong l0, l1, v1, h0, h1;
     438    48740948 :   long k = 1;
     439             :   LOCAL_OVERFLOW;
     440             :   LOCAL_HIREMAINDER;
     441    48740948 :   l1 = mulll(ucoeff(x,i,k), uel(y,k)); h1 = hiremainder; v1 = 0;
     442   746602910 :   while (++k < lx) {
     443   649121014 :     l0 = mulll(ucoeff(x,i,k), uel(y,k)); h0 = hiremainder;
     444   649121014 :     l1 = addll(l0, l1); h1 = addllx(h0, h1); v1 += overflow;
     445             :   }
     446    48740948 :   if (v1 == 0) return remll_pre(h1, l1, p, pi);
     447     2045443 :   else return remlll_pre(v1, h1, l1, p, pi);
     448             : }
     449             : 
     450             : static GEN
     451      142520 : Flm_Flc_mul_i_2(GEN x, GEN y, long lx, long l)
     452             : {
     453             :   long i,j;
     454      142520 :   GEN z = NULL;
     455             : 
     456     3713423 :   for (j=1; j<lx; j++)
     457             :   {
     458     3570903 :     if (!y[j]) continue;
     459      240093 :     if (!z) z = Flv_copy(gel(x,j));
     460      135604 :     else for (i = 1; i < l; i++) z[i] ^= coeff(x,i,j);
     461             :   }
     462      142520 :   if (!z) z = zero_zv(l-1);
     463      142520 :   return z;
     464             : }
     465             : 
     466             : static GEN
     467      983278 : FpM_FpC_mul_i(GEN x, GEN y, long lx, long l, GEN p)
     468             : {
     469      983278 :   GEN z = cgetg(l,t_COL);
     470             :   long i;
     471    16126977 :   for (i = 1; i < l; i++)
     472             :   {
     473    15143699 :     pari_sp av = avma;
     474    15143699 :     GEN c = ZMrow_ZC_mul_i(x, y, lx, i);
     475    15143699 :     gel(z,i) = gerepileuptoint(av, modii(c,p));
     476             :   }
     477      983278 :   return z;
     478             : }
     479             : 
     480             : static void
     481     8086969 : __Flm_Flc_mul_i_SMALL(GEN z, GEN x, GEN y, long lx, long l, ulong p)
     482             : {
     483             :   long i;
     484     8086969 :   for (i = 1; i < l; i++) z[i] = Flmrow_Flc_mul_SMALL(x, y, p, lx, i);
     485     8077420 : }
     486             : static GEN
     487     5159629 : Flm_Flc_mul_i_SMALL(GEN x, GEN y, long lx, long l, ulong p)
     488             : {
     489     5159629 :   GEN z = cgetg(l,t_VECSMALL);
     490     5159629 :   __Flm_Flc_mul_i_SMALL(z, x, y, lx, l, p);
     491     5159629 :   return z;
     492             : }
     493             : 
     494             : static void
     495     5005464 : __Flm_Flc_mul_i(GEN z, GEN x, GEN y, long lx, long l, ulong p, ulong pi)
     496             : {
     497             :   long i;
     498     5005464 :   for (i = 1; i < l; i++) z[i] = Flmrow_Flc_mul_i(x, y, p, pi, lx, i);
     499     5000970 : }
     500             : static GEN
     501     1147839 : Flm_Flc_mul_i(GEN x, GEN y, long lx, long l, ulong p, ulong pi)
     502             : {
     503     1147839 :   GEN z = cgetg(l,t_VECSMALL);
     504     1147839 :   __Flm_Flc_mul_i(z, x, y, lx, l, p, pi);
     505     1147839 :   return z;
     506             : }
     507             : 
     508             : INLINE GEN
     509      232892 : F2m_F2c_mul_i(GEN x, GEN y, long lx, long l)
     510             : {
     511             :   long j;
     512      232892 :   GEN z = NULL;
     513             : 
     514     2836768 :   for (j=1; j<lx; j++)
     515             :   {
     516     2603876 :     if (!F2v_coeff(y,j)) continue;
     517      600420 :     if (!z) z = vecsmall_copy(gel(x,j));
     518      384062 :     else F2v_add_inplace(z,gel(x,j));
     519             :   }
     520      232892 :   if (!z) z = zero_F2v(l);
     521      232892 :   return z;
     522             : }
     523             : 
     524             : GEN
     525      391735 : FpM_mul(GEN x, GEN y, GEN p)
     526             : {
     527      391735 :   long j, l, lx=lg(x), ly=lg(y);
     528             :   GEN z;
     529      391735 :   if (ly==1) return cgetg(1,t_MAT);
     530      391735 :   if (lx==1) return zeromat(0, ly-1);
     531      391735 :   if (lgefint(p) == 3)
     532             :   {
     533      391012 :     pari_sp av = avma;
     534      391012 :     ulong pp = uel(p,2);
     535      391012 :     if (pp == 2)
     536             :     {
     537       49179 :       x = ZM_to_F2m(x);
     538       49179 :       y = ZM_to_F2m(y);
     539       49179 :       z = F2m_to_ZM(F2m_mul(x,y));
     540             :     }
     541             :     else
     542             :     {
     543      341833 :       x = ZM_to_Flm(x, pp);
     544      341833 :       y = ZM_to_Flm(y, pp);
     545      341833 :       z = Flm_to_ZM(Flm_mul(x,y, pp));
     546             :     }
     547      391012 :     return gerepileupto(av, z);
     548             :   }
     549         723 :   l = lgcols(x); z = cgetg(ly,t_MAT);
     550         723 :   for (j=1; j<ly; j++) gel(z,j) = FpM_FpC_mul_i(x, gel(y,j), lx, l, p);
     551         723 :   return z;
     552             : }
     553             : GEN
     554     1517116 : Flm_mul(GEN x, GEN y, ulong p)
     555             : {
     556     1517116 :   long i,j,l,lx=lg(x), ly=lg(y);
     557             :   GEN z;
     558     1517116 :   if (ly==1) return cgetg(1,t_MAT);
     559     1517116 :   z = cgetg(ly,t_MAT);
     560     1517116 :   if (lx==1)
     561             :   {
     562           0 :     for (i=1; i<ly; i++) gel(z,i) = cgetg(1,t_VECSMALL);
     563           0 :     return z;
     564             :   }
     565     1517116 :   l = lgcols(x);
     566     1517116 :   if (SMALL_ULONG(p)) {
     567     5340848 :     for (j=1; j<ly; j++)
     568     4915938 :       gel(z,j) = Flm_Flc_mul_i_SMALL(x, gel(y,j), lx, l, p);
     569             :   } else {
     570     1092206 :     ulong pi = get_Fl_red(p);
     571     2239933 :     for (j=1; j<ly; j++)
     572     1147727 :       gel(z,j) = Flm_Flc_mul_i(x, gel(y,j), lx, l, p, pi);
     573             :   }
     574     1517116 :   return z;
     575             : }
     576             : GEN
     577       49228 : F2m_mul(GEN x, GEN y)
     578             : {
     579       49228 :   long i,j,l,lx=lg(x), ly=lg(y);
     580             :   GEN z;
     581       49228 :   if (ly==1) return cgetg(1,t_MAT);
     582       49228 :   z = cgetg(ly,t_MAT);
     583       49228 :   if (lx==1)
     584             :   {
     585           0 :     for (i=1; i<ly; i++) gel(z,i) = mkvecsmall(0);
     586           0 :     return z;
     587             :   }
     588       49228 :   l = coeff(x,1,1);
     589       49228 :   for (j=1; j<ly; j++) gel(z,j) = F2m_F2c_mul_i(x, gel(y,j), lx, l);
     590       49228 :   return z;
     591             : }
     592             : 
     593             : static GEN
     594       14203 : _Flm_mul(void *p , GEN x, GEN y)
     595       14203 : { return Flm_mul(x,y,*(ulong*)p); }
     596             : static GEN
     597       42322 : _Flm_sqr(void *p, GEN x)
     598       42322 : { return Flm_mul(x,x,*(ulong*)p); }
     599             : GEN
     600       19628 : Flm_powu(GEN x, ulong n, ulong p)
     601             : {
     602       19628 :   pari_sp av = avma;
     603       19628 :   if (!n) return matid(lg(x)-1);
     604       19628 :   return gerepileupto(av, gen_powu(x, n, (void*)&p, &_Flm_sqr, &_Flm_mul));
     605             : }
     606             : static GEN
     607           0 : _F2m_mul(void *data, GEN x, GEN y)
     608           0 : { (void) data; return F2m_mul(x,y); }
     609             : static GEN
     610           0 : _F2m_sqr(void *data, GEN x)
     611           0 : { (void) data; return F2m_mul(x,x); }
     612             : GEN
     613           0 : F2m_powu(GEN x, ulong n)
     614             : {
     615           0 :   pari_sp av = avma;
     616           0 :   if (!n) return matid(lg(x)-1);
     617           0 :   return gerepileupto(av, gen_powu(x, n,NULL, &_F2m_sqr, &_F2m_mul));
     618             : }
     619             : static GEN
     620           0 : _FpM_mul(void *p , GEN x, GEN y)
     621           0 : { return FpM_mul(x,y,(GEN)p); }
     622             : static GEN
     623           0 : _FpM_sqr(void *p, GEN x)
     624           0 : { return FpM_mul(x,x,(GEN)p); }
     625             : GEN
     626           0 : FpM_powu(GEN x, ulong n, GEN p)
     627             : {
     628           0 :   pari_sp av = avma;
     629           0 :   if (!n) return matid(lg(x)-1);
     630           0 :   if (lgefint(p) == 3)
     631             :   {
     632           0 :     pari_sp av = avma;
     633           0 :     ulong pp = uel(p,2);
     634             :     GEN z;
     635           0 :     if (pp == 2)
     636           0 :       z = F2m_to_ZM(F2m_powu(ZM_to_F2m(x),n));
     637             :     else
     638           0 :       z = Flm_to_ZM(Flm_powu(ZM_to_Flm(x, pp), n, pp));
     639           0 :     return gerepileupto(av, z);
     640             :   }
     641           0 :   return gerepileupto(av, gen_powu(x, n, (void*)p, &_FpM_sqr, &_FpM_mul));
     642             : }
     643             : 
     644             : /*Multiple a column vector by a line vector to make a matrix*/
     645             : GEN
     646        1365 : FpC_FpV_mul(GEN x, GEN y, GEN p)
     647             : {
     648        1365 :   long i,j, lx=lg(x), ly=lg(y);
     649             :   GEN z;
     650        1365 :   if (ly==1) return cgetg(1,t_MAT);
     651        1365 :   z = cgetg(ly,t_MAT);
     652       26068 :   for (j=1; j < ly; j++)
     653             :   {
     654       24703 :     gel(z,j) = cgetg(lx,t_COL);
     655       24703 :     for (i=1; i<lx; i++) gcoeff(z,i,j) = Fp_mul(gel(x,i),gel(y,j), p);
     656             :   }
     657        1365 :   return z;
     658             : }
     659             : 
     660             : /* Multiply a line vector by a column and return a scalar (t_INT) */
     661             : GEN
     662      733840 : FpV_dotproduct(GEN x, GEN y, GEN p)
     663             : {
     664      733840 :   long i, lx = lg(x);
     665             :   pari_sp av;
     666             :   GEN c;
     667      733840 :   if (lx == 1) return gen_0;
     668      733798 :   av = avma; c = mulii(gel(x,1),gel(y,1));
     669      733798 :   for (i=2; i<lx; i++) c = addii(c, mulii(gel(x,i),gel(y,i)));
     670      733798 :   return gerepileuptoint(av, modii(c,p));
     671             : }
     672             : GEN
     673           0 : FpV_dotsquare(GEN x, GEN p)
     674             : {
     675           0 :   long i, lx = lg(x);
     676             :   pari_sp av;
     677             :   GEN c;
     678           0 :   if (lx == 1) return gen_0;
     679           0 :   av = avma; c = sqri(gel(x,1));
     680           0 :   for (i=2; i<lx; i++) c = addii(c, sqri(gel(x,i)));
     681           0 :   return gerepileuptoint(av, modii(c,p));
     682             : }
     683             : 
     684             : INLINE ulong
     685      795859 : Flv_dotproductspec_SMALL(GEN x, GEN y, ulong p, long lx)
     686             : {
     687      795859 :   ulong c = uel(x,0) * uel(y,0);
     688             :   long k;
     689    12094318 :   for (k = 1; k < lx; k++) {
     690    11298459 :     c += uel(x,k) * uel(y,k);
     691    11298459 :     if (c & HIGHBIT) c %= p;
     692             :   }
     693      795859 :   return c % p;
     694             : }
     695             : 
     696             : INLINE ulong
     697        4790 : Flv_dotproductspec_i(GEN x, GEN y, ulong p, ulong pi, long lx)
     698             : {
     699             :   ulong l0, l1, v1, h0, h1;
     700        4790 :   long i = 0;
     701             :   LOCAL_OVERFLOW;
     702             :   LOCAL_HIREMAINDER;
     703        4790 :   l1 = mulll(uel(x,i), uel(y,i)); h1 = hiremainder; v1 = 0;
     704      147856 :   while (++i < lx) {
     705      138276 :     l0 = mulll(uel(x,i), uel(y,i)); h0 = hiremainder;
     706      138276 :     l1 = addll(l0, l1); h1 = addllx(h0, h1); v1 += overflow;
     707             :   }
     708        4790 :   if (v1 == 0) return remll_pre(h1, l1, p, pi);
     709           0 :   else return remlll_pre(v1, h1, l1, p, pi);
     710             : }
     711             : 
     712             : ulong
     713      373135 : Flv_dotproduct(GEN x, GEN y, ulong p)
     714             : {
     715      373135 :   long lx = lg(x)-1;
     716      373135 :   if (lx == 1) return 0;
     717      373135 :   if (SMALL_ULONG(p))
     718      373135 :     return Flv_dotproductspec_SMALL(x+1, y+1, p, lx);
     719             :   else
     720           0 :     return Flv_dotproductspec_i(x+1, y+1, p, get_Fl_red(p), lx);
     721             : }
     722             : 
     723             : ulong
     724       44458 : Flv_dotproduct_pre(GEN x, GEN y, ulong p, ulong pi)
     725             : {
     726       44458 :   long lx = lg(x)-1;
     727       44458 :   if (lx == 1) return 0;
     728       44458 :   if (SMALL_ULONG(p))
     729       39752 :     return Flv_dotproductspec_SMALL(x+1, y+1, p, lx);
     730             :   else
     731        4706 :     return Flv_dotproductspec_i(x+1, y+1, p, pi, lx);
     732             : }
     733             : 
     734             : ulong
     735      392444 : Flx_dotproduct(GEN x, GEN y, ulong p)
     736             : {
     737      392444 :   long lx = minss(lgpol(x), lgpol(y));
     738      392444 :   if (lx == 0) return 0;
     739      383056 :   if (SMALL_ULONG(p))
     740      382972 :     return Flv_dotproductspec_SMALL(x+2, y+2, p, lx);
     741             :   else
     742          84 :     return Flv_dotproductspec_i(x+2, y+2, p, get_Fl_red(p), lx);
     743             : }
     744             : 
     745             : ulong
     746           0 : F2v_dotproduct(GEN x, GEN y)
     747             : {
     748           0 :   long i, lx = lg(x);
     749             :   ulong c;
     750           0 :   if (lx == 2) return 0;
     751           0 :   c = uel(x,2) & uel(y,2);
     752           0 :   for (i=3; i<lx; i++) c ^= uel(x,i) & uel(y,i);
     753             : #ifdef LONG_IS_64BIT
     754           0 :   c ^= c >> 32;
     755             : #endif
     756           0 :   c ^= c >> 16;
     757           0 :   c ^= c >>  8;
     758           0 :   c ^= c >>  4;
     759           0 :   c ^= c >>  2;
     760           0 :   c ^= c >>  1;
     761           0 :   return c & 1;
     762             : }
     763             : 
     764             : GEN
     765      976596 : FpM_FpC_mul(GEN x, GEN y, GEN p)
     766             : {
     767      976596 :   long lx = lg(x);
     768      976596 :   return lx==1? cgetg(1,t_COL): FpM_FpC_mul_i(x, y, lx, lgcols(x), p);
     769             : }
     770             : GEN
     771      386323 : Flm_Flc_mul(GEN x, GEN y, ulong p)
     772             : {
     773      386323 :   long l, lx = lg(x);
     774      386323 :   if (lx==1) return cgetg(1,t_VECSMALL);
     775      386323 :   l = lgcols(x);
     776      386323 :   if (p==2)
     777      142520 :     return Flm_Flc_mul_i_2(x, y, lx, l);
     778      243803 :   else if (SMALL_ULONG(p))
     779      243691 :     return Flm_Flc_mul_i_SMALL(x, y, lx, l, p);
     780             :   else
     781         112 :     return Flm_Flc_mul_i(x, y, lx, l, p, get_Fl_red(p));
     782             : }
     783             : 
     784             : GEN
     785        4816 : Flm_Flc_mul_pre(GEN x, GEN y, ulong p, ulong pi)
     786             : {
     787        4816 :   long l, lx = lg(x);
     788             :   GEN z;
     789        4816 :   if (lx==1) return cgetg(1,t_VECSMALL);
     790        4816 :   l = lgcols(x);
     791        4816 :   z = cgetg(l, t_VECSMALL);
     792        4816 :   if (SMALL_ULONG(p))
     793        4128 :     __Flm_Flc_mul_i_SMALL(z, x, y, lx, l, p);
     794             :   else
     795         688 :     __Flm_Flc_mul_i(z, x, y, lx, l, p, pi);
     796        4816 :   return z;
     797             : }
     798             : 
     799             : GEN
     800     6751197 : Flm_Flc_mul_pre_Flx(GEN x, GEN y, ulong p, ulong pi, long sv)
     801             : {
     802     6751197 :   long l, lx = lg(x);
     803             :   GEN z;
     804     6751197 :   if (lx==1) return pol0_Flx(sv);
     805     6751197 :   l = lgcols(x);
     806     6757651 :   z = cgetg(l + 1, t_VECSMALL); z[1] = sv;
     807     6765130 :   if (SMALL_ULONG(p))
     808     2912984 :     __Flm_Flc_mul_i_SMALL(z + 1, x, y, lx, l, p);
     809             :   else
     810     3852146 :     __Flm_Flc_mul_i(z + 1, x, y, lx, l, p, pi);
     811     6765048 :   return Flx_normalize(z, l + 1);
     812             : }
     813             : 
     814             : GEN
     815           0 : F2m_F2c_mul(GEN x, GEN y)
     816             : {
     817           0 :   long l, lx = lg(x);
     818           0 :   if (lx==1) return cgetg(1,t_VECSMALL);
     819           0 :   l = coeff(x,1,1);
     820           0 :   return F2m_F2c_mul_i(x, y, lx, l);
     821             : }
     822             : /* RgV_to_RgX(FpM_FpC_mul(x,y,p), v), p != NULL, memory clean */
     823             : GEN
     824      113795 : FpM_FpC_mul_FpX(GEN x, GEN y, GEN p, long v)
     825             : {
     826      113795 :   long i, l, lx = lg(x);
     827             :   GEN z;
     828      113795 :   if (lx==1) return pol_0(v);
     829      113795 :   l = lgcols(x);
     830      113795 :   z = new_chunk(l+1);
     831      189176 :   for (i=l-1; i; i--)
     832             :   {
     833      174922 :     pari_sp av = avma;
     834      174922 :     GEN p1 = ZMrow_ZC_mul_i(x,y,lx,i);
     835      174922 :     p1 = modii(p1, p);
     836      174922 :     if (signe(p1))
     837             :     {
     838       99541 :       if (i != l-1) stackdummy((pari_sp)(z + l+1), (pari_sp)(z + i+2));
     839       99541 :       gel(z,i+1) = gerepileuptoint(av, p1);
     840       99541 :       break;
     841             :     }
     842       75381 :     avma = av;
     843             :   }
     844      113795 :   if (!i) { avma = (pari_sp)(z + l+1); return pol_0(v); }
     845       99541 :   z[0] = evaltyp(t_POL) | evallg(i+2);
     846       99541 :   z[1] = evalsigne(1) | evalvarn(v);
     847      336989 :   for (; i; i--)
     848             :   {
     849      237448 :     pari_sp av = avma;
     850      237448 :     GEN p1 = ZMrow_ZC_mul_i(x,y,lx,i);
     851      237448 :     gel(z,i+1) = gerepileuptoint(av, modii(p1,p));
     852             :   }
     853       99541 :   return z;
     854             : }
     855             : 
     856             : /********************************************************************/
     857             : /**                                                                **/
     858             : /**                           TRANSPOSITION                        **/
     859             : /**                                                                **/
     860             : /********************************************************************/
     861             : 
     862             : /* == zm_transpose */
     863             : GEN
     864        4285 : Flm_transpose(GEN x)
     865             : {
     866        4285 :   long i, dx, lx = lg(x);
     867             :   GEN y;
     868        4285 :   if (lx == 1) return cgetg(1,t_MAT);
     869        4285 :   dx = lgcols(x); y = cgetg(dx,t_MAT);
     870        4292 :   for (i=1; i<dx; i++) gel(y,i) = Flm_row(x,i);
     871        4294 :   return y;
     872             : }
     873             : 
     874             : /********************************************************************/
     875             : /**                                                                **/
     876             : /**                           SCALAR MATRICES                      **/
     877             : /**                                                                **/
     878             : /********************************************************************/
     879             : 
     880             : GEN
     881          70 : gen_matid(long n, void *E, const struct bb_field *S)
     882             : {
     883          70 :   GEN y = cgetg(n+1,t_MAT), _0, _1;
     884             :   long i;
     885          70 :   if (n < 0) pari_err_DOMAIN("gen_matid", "dimension","<",gen_0,stoi(n));
     886          70 :   _0 = S->s(E,0);
     887          70 :   _1 = S->s(E,1);
     888         266 :   for (i=1; i<=n; i++)
     889             :   {
     890         196 :     GEN z = const_col(n, _0); gel(z,i) = _1;
     891         196 :     gel(y, i) = z;
     892             :   }
     893          70 :   return y;
     894             : }
     895             : 
     896             : GEN
     897        9394 : matid_F2m(long n)
     898             : {
     899        9394 :   GEN y = cgetg(n+1,t_MAT);
     900             :   long i;
     901        9394 :   if (n < 0) pari_err_DOMAIN("matid_F2m", "dimension","<",gen_0,stoi(n));
     902        9394 :   for (i=1; i<=n; i++) { gel(y,i) = zero_F2v(n); F2v_set(gel(y,i),i); }
     903        9394 :   return y;
     904             : }
     905             : 
     906             : GEN
     907          35 : matid_F2xqM(long n, GEN T)
     908             : {
     909             :   void *E;
     910          35 :   const struct bb_field *S = get_F2xq_field(&E, T);
     911          35 :   return gen_matid(n, E, S);
     912             : }
     913             : GEN
     914          35 : matid_FlxqM(long n, GEN T, ulong p)
     915             : {
     916             :   void *E;
     917          35 :   const struct bb_field *S = get_Flxq_field(&E, T, p);
     918          35 :   return gen_matid(n, E, S);
     919             : }
     920             : 
     921             : GEN
     922      731269 : matid_Flm(long n)
     923             : {
     924      731269 :   GEN y = cgetg(n+1,t_MAT);
     925             :   long i;
     926      731269 :   if (n < 0) pari_err_DOMAIN("matid_Flm", "dimension","<",gen_0,stoi(n));
     927      731269 :   for (i=1; i<=n; i++) { gel(y,i) = zero_zv(n); ucoeff(y, i,i) = 1; }
     928      731269 :   return y;
     929             : }
     930             : 
     931             : GEN
     932          42 : scalar_Flm(long s, long n)
     933             : {
     934             :   long i;
     935          42 :   GEN y = cgetg(n+1,t_MAT);
     936          42 :   for (i=1; i<=n; i++) { gel(y,i) = zero_Flv(n); coeff(y, i,i) = s; }
     937          42 :   return y;
     938             : }
     939             : 
     940             : /********************************************************************/
     941             : /**                                                                **/
     942             : /**                           CONVERSIONS                          **/
     943             : /**                                                                **/
     944             : /********************************************************************/
     945             : GEN
     946    19994300 : ZV_to_Flv(GEN x, ulong p)
     947             : {
     948    19994300 :   long i, n = lg(x);
     949    19994300 :   GEN y = cgetg(n,t_VECSMALL);
     950    19994338 :   for (i=1; i<n; i++) y[i] = umodiu(gel(x,i), p);
     951    19994305 :   return y;
     952             : }
     953             : GEN
     954     3381311 : ZM_to_Flm(GEN x, ulong p)
     955             : {
     956     3381311 :   long j,n = lg(x);
     957     3381311 :   GEN y = cgetg(n,t_MAT);
     958     3381316 :   if (n == 1) return y;
     959     3381141 :   for (j=1; j<n; j++) gel(y,j) = ZV_to_Flv(gel(x,j), p);
     960     3381139 :   return y;
     961             : }
     962             : GEN
     963        1372 : ZMV_to_FlmV(GEN z, ulong m)
     964             : {
     965        1372 :   long i, l = lg(z);
     966        1372 :   GEN x = cgetg(l,t_VEC);
     967        1372 :   for (i=1; i<l; i++) gel(x,i) = ZM_to_Flm(gel(z,i), m);
     968        1372 :   return x;
     969             : }
     970             : 
     971             : /*                          TO INTMOD                        */
     972             : static GEN
     973     1270396 : to_intmod(GEN x, GEN p) { retmkintmod(modii(x, p), p); }
     974             : static GEN
     975        1154 : Fl_to_intmod(ulong x, GEN p) { retmkintmod(utoi(x), p); }
     976             : 
     977             : GEN
     978      284885 : Fp_to_mod(GEN z, GEN p)
     979             : {
     980      284885 :   retmkintmod(modii(z, p), icopy(p));
     981             : }
     982             : 
     983             : /* z in Z[X], return z * Mod(1,p), normalized*/
     984             : GEN
     985       53550 : FpX_to_mod(GEN z, GEN p)
     986             : {
     987       53550 :   long i,l = lg(z);
     988       53550 :   GEN x = cgetg(l,t_POL);
     989       53550 :   if (l >2) p = icopy(p);
     990       53550 :   for (i=2; i<l; i++) gel(x,i) = to_intmod(gel(z,i), p);
     991       53550 :   x[1] = z[1]; return normalizepol_lg(x,l);
     992             : }
     993             : 
     994             : /* z in Z^n, return z * Mod(1,p), normalized*/
     995             : GEN
     996        4249 : FpV_to_mod(GEN z, GEN p)
     997             : {
     998        4249 :   long i,l = lg(z);
     999        4249 :   GEN x = cgetg(l, t_VEC);
    1000        4249 :   if (l == 1) return x;
    1001        4249 :   p = icopy(p);
    1002        4249 :   for (i=1; i<l; i++) gel(x,i) = to_intmod(gel(z,i), p);
    1003        4249 :   return x;
    1004             : }
    1005             : /* z in Z^n, return z * Mod(1,p), normalized*/
    1006             : GEN
    1007          63 : FpC_to_mod(GEN z, GEN p)
    1008             : {
    1009          63 :   long i, l = lg(z);
    1010          63 :   GEN x = cgetg(l, t_COL);
    1011          63 :   if (l == 1) return x;
    1012          63 :   p = icopy(p);
    1013          63 :   for (i=1; i<l; i++) gel(x,i) = to_intmod(gel(z,i), p);
    1014          63 :   return x;
    1015             : }
    1016             : /* z in Mat m,n(Z), return z * Mod(1,p), normalized*/
    1017             : GEN
    1018         100 : FpM_to_mod(GEN z, GEN p)
    1019             : {
    1020         100 :   long i, j, m, l = lg(z);
    1021         100 :   GEN  x = cgetg(l,t_MAT), y, zi;
    1022         100 :   if (l == 1) return x;
    1023          93 :   m = lgcols(z);
    1024          93 :   p = icopy(p);
    1025         790 :   for (i=1; i<l; i++)
    1026             :   {
    1027         697 :     gel(x,i) = cgetg(m,t_COL);
    1028         697 :     y = gel(x,i); zi= gel(z,i);
    1029         697 :     for (j=1; j<m; j++) gel(y,j) = to_intmod(gel(zi,j), p);
    1030             :   }
    1031          93 :   return x;
    1032             : }
    1033             : GEN
    1034          28 : Flc_to_mod(GEN z, ulong pp)
    1035             : {
    1036          28 :   long i, l = lg(z);
    1037          28 :   GEN p, x = cgetg(l, t_COL);
    1038          28 :   if (l == 1) return x;
    1039          28 :   p = utoipos(pp);
    1040          28 :   for (i=1; i<l; i++) gel(x,i) = Fl_to_intmod(z[i], p);
    1041          28 :   return x;
    1042             : }
    1043             : GEN
    1044         166 : Flm_to_mod(GEN z, ulong pp)
    1045             : {
    1046         166 :   long i, j, m, l = lg(z);
    1047         166 :   GEN p, x = cgetg(l,t_MAT), y, zi;
    1048         166 :   if (l == 1) return x;
    1049         152 :   m = lgcols(z);
    1050         152 :   p = utoipos(pp);
    1051         547 :   for (i=1; i<l; i++)
    1052             :   {
    1053         395 :     gel(x,i) = cgetg(m,t_COL);
    1054         395 :     y = gel(x,i); zi= gel(z,i);
    1055         395 :     for (j=1; j<m; j++) gel(y,j) = Fl_to_intmod(zi[j], p);
    1056             :   }
    1057         152 :   return x;
    1058             : }
    1059             : 
    1060             : GEN
    1061        1820 : FpVV_to_mod(GEN z, GEN p)
    1062             : {
    1063        1820 :   long i, j, m, l = lg(z);
    1064        1820 :   GEN  x = cgetg(l,t_VEC), y, zi;
    1065        1820 :   if (l == 1) return x;
    1066        1743 :   m = lgcols(z);
    1067        1743 :   p = icopy(p);
    1068        3647 :   for (i=1; i<l; i++)
    1069             :   {
    1070        1904 :     gel(x,i) = cgetg(m,t_VEC);
    1071        1904 :     y = gel(x,i); zi= gel(z,i);
    1072        1904 :     for (j=1; j<m; j++) gel(y,j) = to_intmod(gel(zi,j), p);
    1073             :   }
    1074        1743 :   return x;
    1075             : }
    1076             : 
    1077             : /* z in Z^n, return z * Mod(1,p), normalized*/
    1078             : GEN
    1079           7 : FpXQC_to_mod(GEN z, GEN T, GEN p)
    1080             : {
    1081           7 :   long i,l = lg(z);
    1082           7 :   GEN x = cgetg(l, t_COL); T = FpX_to_mod(T, p);
    1083          21 :   for (i=1; i<l; i++)
    1084          14 :     gel(x,i) = mkpolmod(FpX_to_mod(gel(z,i), p), T);
    1085           7 :   return x;
    1086             : }
    1087             : 
    1088             : /********************************************************************/
    1089             : /*                                                                  */
    1090             : /*                     Blackbox linear algebra                      */
    1091             : /*                                                                  */
    1092             : /********************************************************************/
    1093             : 
    1094             : /* A sparse column (zCs) v is a t_COL with two components C and E which are
    1095             :  * t_VECSMALL of the same length, representing sum_i E[i]*e_{C[i]}, where
    1096             :  * (e_j) is the canonical basis.
    1097             :  * A sparse matrix (zMs) is a t_VEC of zCs */
    1098             : 
    1099             : /* FpCs and FpMs are identical but E[i] is interpreted as a _signed_ C long
    1100             :  * integer representing an element of Fp. This is important since p can be
    1101             :  * large and p+E[i] would not fit in a C long.  */
    1102             : 
    1103             : /* RgCs and RgMs are similar, except that the type of the component is
    1104             :  * unspecified. Functions handling RgCs/RgMs must be independent of the type
    1105             :  * of E. */
    1106             : 
    1107             : /* Most functions take an argument nbrow which is the number of lines of the
    1108             :  * column/matrix, which cannot be derived from the data. */
    1109             : 
    1110             : GEN
    1111           0 : zCs_to_ZC(GEN R, long nbrow)
    1112             : {
    1113           0 :   GEN C = gel(R,1), E = gel(R,2), c = zerocol(nbrow);
    1114           0 :   long j, l = lg(C);
    1115           0 :   for (j = 1; j < l; ++j) gel(c, C[j]) = stoi(E[j]);
    1116           0 :   return c;
    1117             : }
    1118             : 
    1119             : GEN
    1120           0 : zMs_to_ZM(GEN M, long nbrow)
    1121             : {
    1122           0 :   long i, l = lg(M);
    1123           0 :   GEN m = cgetg(l, t_MAT);
    1124           0 :   for (i = 1; i < l; ++i) gel(m,i) = zCs_to_ZC(gel(M,i), nbrow);
    1125           0 :   return m;
    1126             : }
    1127             : 
    1128             : /* Solve equation f(X) = B (mod p) where B is a FpV, and f is an endomorphism.
    1129             :  * Return either a solution as a t_COL, or a kernel vector as a t_VEC. */
    1130             : GEN
    1131         119 : gen_FpM_Wiedemann(void *E, GEN (*f)(void*, GEN), GEN B, GEN p)
    1132             : {
    1133         119 :   pari_sp ltop = avma;
    1134         119 :   long col = 0, n = lg(B)-1, m = 2*n+1;
    1135         119 :   if (ZV_equal0(B)) return zerocol(n);
    1136         238 :   while (++col <= n)
    1137             :   {
    1138         119 :     pari_sp btop = avma, av;
    1139             :     long i, lQ;
    1140         119 :     GEN V, Q, M, W = B;
    1141         119 :     GEN b = cgetg(m+2, t_POL);
    1142         119 :     b[1] = evalsigne(1)|evalvarn(0);
    1143         119 :     gel(b, 2) = gel(W, col);
    1144       51269 :     for (i = 3; i<m+2; i++)
    1145       51150 :       gel(b, i) = cgeti(lgefint(p));
    1146         119 :     av = avma;
    1147       51269 :     for (i = 3; i<m+2; i++)
    1148             :     {
    1149       51150 :       W = f(E, W);
    1150       51150 :       affii(gel(W, col),gel(b, i));
    1151       51150 :       if (gc_needed(av,1))
    1152             :       {
    1153        2046 :         if (DEBUGMEM>1) pari_warn(warnmem,"Wiedemann: first loop, %ld",i);
    1154        2046 :         W = gerepileupto(av, W);
    1155             :       }
    1156             :     }
    1157         119 :     b = FpX_renormalize(b, m+2);
    1158         119 :     if (lgpol(b)==0) {avma = btop; continue; }
    1159         119 :     M = FpX_halfgcd(b, pol_xn(m, 0), p);
    1160         119 :     Q = FpX_neg(FpX_normalize(gcoeff(M, 2, 1),p),p);
    1161         119 :     W = B; lQ =lg(Q);
    1162         119 :     if (DEBUGLEVEL) err_printf("Wiedemann: deg. minpoly: %ld\n",lQ-3);
    1163         119 :     V = FpC_Fp_mul(W, gel(Q, lQ-2), p);
    1164         119 :     av = avma;
    1165       25101 :     for (i = lQ-3; i > 1; i--)
    1166             :     {
    1167       24982 :       W = f(E, W);
    1168       24982 :       V = ZC_lincomb(gen_1, gel(Q,i), V, W);
    1169       24982 :       if (gc_needed(av,1))
    1170             :       {
    1171        1710 :         if (DEBUGMEM>1) pari_warn(warnmem,"Wiedemann: second loop, %ld",i);
    1172        1710 :         gerepileall(av, 2, &V, &W);
    1173             :       }
    1174             :     }
    1175         119 :     V = FpC_red(V, p);
    1176         119 :     W = FpC_sub(f(E,V), B, p);
    1177         238 :     if (ZV_equal0(W)) return gerepilecopy(ltop, V);
    1178           1 :     av = avma;
    1179           1 :     for (i = 1; i <= n; ++i)
    1180             :     {
    1181           1 :       V = W;
    1182           1 :       W = f(E, V);
    1183           1 :       if (ZV_equal0(W))
    1184           1 :         return gerepilecopy(ltop, shallowtrans(V));
    1185           0 :       gerepileall(av, 2, &V, &W);
    1186             :     }
    1187           0 :     avma = btop;
    1188             :   }
    1189           0 :   return NULL;
    1190             : }
    1191             : 
    1192             : GEN
    1193           0 : zMs_ZC_mul(GEN M, GEN B)
    1194             : {
    1195             :   long i, j;
    1196           0 :   long n = lg(B)-1;
    1197           0 :   GEN V = zerocol(n);
    1198           0 :   for (i = 1; i <= n; ++i)
    1199           0 :     if (signe(gel(B, i)))
    1200             :     {
    1201           0 :       GEN R = gel(M, i), C = gel(R, 1), E = gel(R, 2);
    1202           0 :       long l = lg(C);
    1203           0 :       for (j = 1; j < l; ++j)
    1204             :       {
    1205           0 :         long k = C[j];
    1206           0 :         switch(E[j])
    1207             :         {
    1208             :         case 1:
    1209           0 :           gel(V, k) = gel(V,k)==gen_0 ? gel(B,i) : addii(gel(V, k), gel(B,i));
    1210           0 :           break;
    1211             :         case -1:
    1212           0 :           gel(V, k) = gel(V,k)==gen_0 ? negi(gel(B,i)) : subii(gel(V, k), gel(B,i));
    1213           0 :           break;
    1214             :         default:
    1215           0 :           gel(V, k) = gel(V,k)==gen_0 ? mulis(gel(B, i), E[j]) : addii(gel(V, k), mulis(gel(B, i), E[j]));
    1216           0 :           break;
    1217             :         }
    1218             :       }
    1219             :     }
    1220           0 :   return V;
    1221             : }
    1222             : 
    1223             : GEN
    1224           0 : FpMs_FpC_mul(GEN M, GEN B, GEN p) { return FpC_red(zMs_ZC_mul(M, B), p); }
    1225             : 
    1226             : GEN
    1227       76371 : ZV_zMs_mul(GEN B, GEN M)
    1228             : {
    1229             :   long i, j;
    1230       76371 :   long m = lg(M)-1;
    1231       76371 :   GEN V = cgetg(m+1,t_VEC);
    1232    40630379 :   for (i = 1; i <= m; ++i)
    1233             :   {
    1234    40554008 :     GEN R = gel(M, i), C = gel(R, 1), E = gel(R, 2);
    1235    40554008 :     long l = lg(C);
    1236    40554008 :     GEN z = mulis(gel(B, C[1]), E[1]);
    1237   340965601 :     for (j = 2; j < l; ++j)
    1238             :     {
    1239   300411593 :       long k = C[j];
    1240   300411593 :       switch(E[j])
    1241             :       {
    1242             :       case 1:
    1243   204282868 :         z = addii(z, gel(B,k));
    1244   204282868 :         break;
    1245             :       case -1:
    1246    81844176 :         z = subii(z, gel(B,k));
    1247    81844176 :         break;
    1248             :       default:
    1249    14284549 :         z = addii(z, mulis(gel(B,k), E[j]));
    1250    14284549 :         break;
    1251             :       }
    1252             :     }
    1253    40554008 :     gel(V,i) = z;
    1254             :   }
    1255       76371 :   return V;
    1256             : }
    1257             : 
    1258             : GEN
    1259         119 : FpV_FpMs_mul(GEN B, GEN M, GEN p) { return FpV_red(ZV_zMs_mul(B, M), p); }
    1260             : 
    1261             : GEN
    1262      469694 : ZlM_gauss(GEN a, GEN b, ulong p, long e, GEN C)
    1263             : {
    1264      469694 :   pari_sp av = avma, av2;
    1265      469694 :   GEN xi, xb, pi = gen_1, P;
    1266             :   long i;
    1267      469694 :   if (!C) {
    1268           0 :     C = Flm_inv(ZM_to_Flm(a, p), p);
    1269           0 :     if (!C) pari_err_INV("ZlM_gauss", a);
    1270             :   }
    1271      469694 :   P = utoipos(p);
    1272      469694 :   av2 = avma;
    1273      469694 :   xi = Flm_mul(C, ZM_to_Flm(b, p), p);
    1274      469694 :   xb = Flm_to_ZM(xi);
    1275     1090767 :   for (i = 2; i <= e; i++)
    1276             :   {
    1277      621073 :     pi = muliu(pi, p); /* = p^(i-1) */
    1278      621073 :     b = ZM_Z_divexact(ZM_sub(b, ZM_nm_mul(a, xi)), P);
    1279      621073 :     if (gc_needed(av,2))
    1280             :     {
    1281          38 :       if(DEBUGMEM>1) pari_warn(warnmem,"ZlM_gauss. i=%ld",i);
    1282          38 :       gerepileall(av2,3, &pi,&b,&xb);
    1283             :     }
    1284      621073 :     xi = Flm_mul(C, ZM_to_Flm(b, p), p);
    1285      621073 :     xb = ZM_add(xb, nm_Z_mul(xi, pi));
    1286             :   }
    1287      469694 :   return gerepileupto(av, xb);
    1288             : }
    1289             : 
    1290             : struct wrapper_modp_s {
    1291             :   GEN (*f)(void*, GEN);
    1292             :   void *E;
    1293             :   GEN p;
    1294             : };
    1295             : 
    1296             : /* compute f(x) mod p */
    1297             : static GEN
    1298       76252 : wrap_relcomb_modp(void *E, GEN x)
    1299             : {
    1300       76252 :   struct wrapper_modp_s *W = (struct wrapper_modp_s*)E;
    1301       76252 :   return FpC_red(W->f(W->E, x), W->p);
    1302             : }
    1303             : static GEN
    1304           0 : wrap_relcomb(void*E, GEN x) { return zMs_ZC_mul((GEN)E, x); }
    1305             : 
    1306             : static GEN
    1307       76252 : wrap_relker(void*E, GEN x) { return ZV_zMs_mul(x, (GEN)E); }
    1308             : 
    1309             : /* Solve f(X) = B (mod p^e); blackbox version of ZlM_gauss */
    1310             : GEN
    1311           0 : gen_ZpM_Dixon(void *E, GEN (*f)(void*, GEN), GEN B, GEN p, long e)
    1312             : {
    1313             :   struct wrapper_modp_s W;
    1314           0 :   pari_sp av = avma;
    1315           0 :   GEN xb, xi, pi = gen_1;
    1316             :   long i;
    1317           0 :   W.E = E;
    1318           0 :   W.f = f;
    1319           0 :   W.p = p;
    1320           0 :   xi = gen_FpM_Wiedemann((void*)&W, wrap_relcomb_modp, FpC_red(B, p), p); /* f^(-1) B */
    1321           0 :   if (!xi || e == 1 || typ(xi) == t_VEC) return xi;
    1322           0 :   xb = xi;
    1323           0 :   for (i = 2; i <= e; i++)
    1324             :   {
    1325           0 :     pi = mulii(pi, p); /* = p^(i-1) */
    1326           0 :     B = ZC_Z_divexact(ZC_sub(B, f(E, xi)), p);
    1327           0 :     if (gc_needed(av,2))
    1328             :     {
    1329           0 :       if(DEBUGMEM>1) pari_warn(warnmem,"gen_ZpM_Dixon. i=%ld",i);
    1330           0 :       gerepileall(av,3, &pi,&B,&xb);
    1331             :     }
    1332           0 :     xi = gen_FpM_Wiedemann((void*)&W, wrap_relcomb_modp, FpC_red(B, p), p);
    1333           0 :     if (!xi) return NULL;
    1334           0 :     if (typ(xi) == t_VEC) return gerepileupto(av, xi);
    1335           0 :     xb = ZC_add(xb, ZC_Z_mul(xi, pi));
    1336             :   }
    1337           0 :   return gerepileupto(av, xb);
    1338             : }
    1339             : 
    1340             : static GEN
    1341       25575 : vecprow(GEN A, GEN prow)
    1342             : {
    1343       25575 :   return mkvec2(vecsmallpermute(prow,gel(A,1)), gel(A,2));
    1344             : }
    1345             : 
    1346             : /* Solve the equation MX = A. Return either a solution as a t_COL,
    1347             :  * or the index of a column which is linearly dependent from the others as a
    1348             :  * t_VECSMALL with a single component. */
    1349             : GEN
    1350           0 : ZpMs_ZpCs_solve(GEN M, GEN A, long nbrow, GEN p, long e)
    1351             : {
    1352           0 :   pari_sp av = avma;
    1353             :   GEN pcol, prow;
    1354           0 :   long nbi=lg(M)-1, lR;
    1355             :   long i, n;
    1356             :   GEN Mp, Ap, Rp;
    1357             :   pari_timer ti;
    1358           0 :   if (DEBUGLEVEL) timer_start(&ti);
    1359           0 :   RgMs_structelim(M, nbrow, gel(A, 1), &pcol, &prow);
    1360           0 :   if (!pcol) { avma = av; return NULL; }
    1361           0 :   if (DEBUGLEVEL)
    1362           0 :     timer_printf(&ti,"structured elimination (%ld -> %ld)",nbi,lg(pcol)-1);
    1363           0 :   n = lg(pcol)-1;
    1364           0 :   Mp = cgetg(n+1, t_MAT);
    1365           0 :   for(i=1; i<=n; i++)
    1366           0 :     gel(Mp, i) = vecprow(gel(M,pcol[i]), prow);
    1367           0 :   Ap = zCs_to_ZC(vecprow(A, prow), n);
    1368           0 :   if (DEBUGLEVEL) timer_start(&ti);
    1369           0 :   Rp = gen_ZpM_Dixon((void*)Mp,wrap_relcomb, Ap, p, e);
    1370           0 :   if (DEBUGLEVEL) timer_printf(&ti,"linear algebra");
    1371           0 :   if (!Rp) { avma = av; return NULL; }
    1372           0 :   lR = lg(Rp)-1;
    1373           0 :   if (typ(Rp) == t_COL)
    1374             :   {
    1375           0 :     GEN R = zerocol(nbi+1);
    1376           0 :     for (i=1; i<=lR; i++)
    1377           0 :        gel(R,pcol[i]) = gel(Rp,i);
    1378           0 :     return gerepilecopy(av, R);
    1379             :   }
    1380           0 :   for (i = 1; i <= lR; ++i)
    1381           0 :     if (signe(gel(Rp, i)))
    1382           0 :       return gerepileuptoleaf(av, mkvecsmall(pcol[i]));
    1383             :   return NULL; /* LCOV_EXCL_LINE */
    1384             : }
    1385             : 
    1386             : GEN
    1387           0 : FpMs_FpCs_solve(GEN M, GEN A, long nbrow, GEN p)
    1388             : {
    1389           0 :   return ZpMs_ZpCs_solve(M, A, nbrow, p, 1);
    1390             : }
    1391             : 
    1392             : GEN
    1393           0 : FpMs_FpCs_solve_safe(GEN M, GEN A, long nbrow, GEN p)
    1394             : {
    1395             :   GEN res;
    1396           0 :   pari_CATCH(e_INV)
    1397             :   {
    1398           0 :     GEN E = pari_err_last();
    1399           0 :     GEN x = err_get_compo(E,2);
    1400           0 :     if (typ(x) != t_INTMOD) pari_err(0,E);
    1401           0 :     if (DEBUGLEVEL)
    1402           0 :       pari_warn(warner,"FpMs_FpCs_solve_safe, impossible inverse %Ps", x);
    1403           0 :     res = NULL;
    1404             :   } pari_TRY {
    1405           0 :     res = ZpMs_ZpCs_solve(M, A, nbrow, p, 1);
    1406           0 :   } pari_ENDCATCH
    1407           0 :   return res;
    1408             : }
    1409             : 
    1410             : static GEN
    1411         119 : FpMs_structelim_back(GEN M, GEN V, GEN prow, GEN p)
    1412             : {
    1413         119 :   long i, j, oldf = 0, f = 0;
    1414         119 :   long lrow = lg(prow), lM = lg(M);
    1415         119 :   GEN W = const_vecsmall(lM-1,1);
    1416         119 :   GEN R = cgetg(lrow, t_VEC);
    1417      221069 :   for (i=1; i<lrow; i++)
    1418      220950 :     gel(R,i) = prow[i]==0 ? NULL: gel(V,prow[i]);
    1419             :   do
    1420             :   {
    1421         386 :     oldf = f;
    1422      417457 :     for(i=1; i<lM; i++)
    1423      417071 :       if (W[i])
    1424             :       {
    1425      141336 :         GEN C = gel(M,i), F = gel(C,1), E = gel(C,2);
    1426      141336 :         long c=0, cj=0, lF = lg(F);
    1427     1236759 :         for(j=1; j<lF; j++)
    1428     1095423 :           if (!gel(R,F[j]))
    1429       82014 :           { c++; cj=j; }
    1430      141336 :         if (c>=2) continue;
    1431      122104 :         if (c==1)
    1432             :         {
    1433       39422 :           pari_sp av = avma;
    1434       39422 :           GEN s = gen_0;
    1435      343487 :           for(j=1; j<lF; j++)
    1436      304065 :             if (j!=cj) s = Fp_add(s, mulis(gel(R,F[j]), E[j]), p);
    1437       39422 :           gel(R,F[cj]) = gerepileupto(av, Fp_div(Fp_neg(s, p), stoi(E[cj]), p));
    1438       39422 :           f++;
    1439             :         }
    1440      122104 :         W[i]=0;
    1441             :       }
    1442         386 :   } while(oldf!=f);
    1443      221069 :   for (i=1; i<lrow; i++)
    1444      220950 :     if (!gel(R,i)) gel(R,i) = gen_0;
    1445         119 :   return R;
    1446             : }
    1447             : 
    1448             : /* Return a linear form Y such that YM is essentially 0 */
    1449             : GEN
    1450         119 : FpMs_leftkernel_elt_col(GEN M, long nbcol, long nbrow, GEN p)
    1451             : {
    1452         119 :   pari_sp av = avma, av2;
    1453             :   GEN pcol, prow;
    1454             :   long i, n;
    1455             :   GEN Mp, B, MB, R, Rp;
    1456             :   pari_timer ti;
    1457             :   struct wrapper_modp_s W;
    1458         119 :   if (DEBUGLEVEL) timer_start(&ti);
    1459         119 :   RgMs_structelim_col(M, nbcol, nbrow, cgetg(1,t_VECSMALL), &pcol, &prow);
    1460         119 :   if (!pcol) { avma = av; return NULL; }
    1461         119 :   if (DEBUGLEVEL)
    1462           0 :     timer_printf(&ti,"structured elimination (%ld -> %ld)",nbcol,lg(pcol)-1);
    1463         119 :   n = lg(pcol)-1;
    1464         119 :   Mp = cgetg(n+1, t_MAT);
    1465       25694 :   for(i=1; i<=n; i++)
    1466       25575 :     gel(Mp, i) = vecprow(gel(M,pcol[i]), prow);
    1467         119 :   W.E = (void*) Mp;
    1468         119 :   W.f = wrap_relker;
    1469         119 :   W.p = p;
    1470         119 :   av2 = avma;
    1471             :   for(;;)
    1472             :   {
    1473         119 :     avma = av2;
    1474         119 :     B = cgetg(n+1,t_VEC);
    1475       25694 :     for(i=1; i<=n; i++)
    1476       25575 :       gel(B,i) = randomi(p);
    1477         119 :     MB = FpV_FpMs_mul(B, Mp, p);
    1478         119 :     if (DEBUGLEVEL) timer_start(&ti);
    1479         119 :     pari_CATCH(e_INV)
    1480             :     {
    1481           0 :       GEN E = pari_err_last();
    1482           0 :       GEN x = err_get_compo(E,2);
    1483           0 :       if (typ(x) != t_INTMOD) pari_err(0,E);
    1484           0 :       if (DEBUGLEVEL)
    1485           0 :         pari_warn(warner,"FpMs_leftkernel_elt, impossible inverse %Ps", x);
    1486           0 :       Rp = NULL;
    1487             :     } pari_TRY {
    1488         119 :       Rp = gen_FpM_Wiedemann((void*)&W, wrap_relcomb_modp, MB, p);
    1489         119 :     } pari_ENDCATCH
    1490         119 :     if (!Rp) continue;
    1491         119 :     if (typ(Rp)==t_COL)
    1492             :     {
    1493         118 :       Rp = FpC_sub(Rp,B,p);
    1494         118 :       if (ZV_equal0(Rp)) continue;
    1495             :     }
    1496         119 :     R = FpMs_structelim_back(M, Rp, prow, p);
    1497         119 :     if (DEBUGLEVEL) timer_printf(&ti,"Wiedemann left kernel");
    1498         119 :     return gerepilecopy(av, R);
    1499           0 :   }
    1500             : }
    1501             : 
    1502             : GEN
    1503          35 : FpMs_leftkernel_elt(GEN M, long nbrow, GEN p)
    1504             : {
    1505          35 :   return FpMs_leftkernel_elt_col(M, lg(M)-1, nbrow, p);
    1506             : }

Generated by: LCOV version 1.11