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-bordeaux1.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 - Flxq_log.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.8.0 lcov report (development 16804-345a01c) Lines: 401 430 93.3 %
Date: 2014-09-20 Functions: 25 25 100.0 %
Legend: Lines: hit not hit | Branches: + taken - not taken # not executed Branches: 175 248 70.6 %

           Branch data     Line data    Source code
       1                 :            : /* Copyright (C) 2013 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                 :            : /* Let [ be the following order on Fp: 0 [ p-1 [ 1 [ p-2 [ 2 .. [ p\2
      18                 :            : and [[ the lexicographic extension of [ to Fp[T]. Compute the
      19                 :            : isomorphism (Fp[X], [[) -> (N,<) on P */
      20                 :            : 
      21                 :            : static long
      22                 :     378588 : Flx_cindex(GEN P, ulong p)
      23                 :            : {
      24                 :     378588 :   long d = degpol(P), i;
      25                 :     378588 :   ulong s = 0, p2 = (p-1)>>1;
      26         [ +  + ]:    1710961 :   for (i = 0; i <= d; ++i)
      27                 :            :   {
      28                 :    1332373 :     ulong x = P[d-i+2];
      29         [ +  + ]:    1332373 :     if (x<=p2) x = 2*x; else x = 1+2*(p-1-x);
      30                 :    1332373 :     s = p*s+x;
      31                 :            :   }
      32                 :     378588 :   return s;
      33                 :            : }
      34                 :            : 
      35                 :            : /* Compute the polynomial immediately after t for the [[ order */
      36                 :            : 
      37                 :            : static void
      38                 :     367248 : Flx_cnext(GEN t, ulong p)
      39                 :            : {
      40                 :            :   long i;
      41                 :     367248 :   long p2 = p>>1;
      42                 :     367248 :   for(i=2;;i++)
      43         [ +  + ]:     457352 :     if (t[i]==p2)
      44                 :      90104 :       t[i]=0;
      45                 :            :     else
      46                 :            :     {
      47         [ +  + ]:     367248 :       t[i] = t[i]<p2 ? p-1-t[i]: p-t[i];
      48                 :     367248 :       break;
      49                 :      90104 :     }
      50                 :     367248 : }
      51                 :            : 
      52                 :            : static int
      53                 :         21 : has_deg1_auto(GEN T, ulong p)
      54                 :            : {
      55                 :         21 :   long i, n = degpol(T);
      56                 :         21 :   GEN a = polx_Flx(get_Flx_var(T));
      57         [ +  + ]:        441 :   for (i=1; i<n; i++)
      58                 :            :   {
      59                 :        420 :     a = Flxq_powu(a, p, T, p);
      60         [ -  + ]:        420 :     if (degpol(a)==1) return 1;
      61                 :            :   }
      62                 :         21 :   return 0;
      63                 :            : }
      64                 :            : 
      65                 :            : static void
      66                 :        581 : smallirred_Flx_next(GEN a, long p)
      67                 :            : {
      68                 :            :   do
      69                 :            :   {
      70                 :            :     long i;
      71                 :        581 :     for(i=2;;i++)
      72         [ +  + ]:        756 :       if (++a[i]==p) a[i]=0;
      73                 :        756 :       else break;
      74 [ +  + ][ -  + ]:        581 :   } while (!Flx_is_irred(a, p) || has_deg1_auto(a,p) );
      75                 :         21 : }
      76                 :            : 
      77                 :            : /* Avoid automorphisms of degree 1 */
      78                 :            : static GEN
      79                 :         21 : smallirred_Flx(long p, ulong n, long sv)
      80                 :            : {
      81                 :         21 :   GEN a = zero_zv(n+2);
      82                 :         21 :   a[1] = sv; a[3] = 1; a[n+2] = 1;
      83                 :         21 :   smallirred_Flx_next(a, p);
      84                 :         21 :   return a;
      85                 :            : }
      86                 :            : 
      87                 :            : struct Flxq_log_rel
      88                 :            : {
      89                 :            :   long nbrel;
      90                 :            :   GEN rel;
      91                 :            :   long nb;
      92                 :            :   long r, off, nbmax, nbexp;
      93                 :            :   ulong nbtest;
      94                 :            : };
      95                 :            : 
      96                 :            : static GEN
      97                 :       3283 : cindex_Flx(long c, long d, ulong p, long v)
      98                 :            : {
      99                 :       3283 :   GEN P = cgetg(d+3, t_VECSMALL);
     100                 :            :   long i;
     101                 :       3283 :   P[1] = v;
     102         [ +  + ]:      20524 :   for (i = 0; i <= d; ++i)
     103                 :            :   {
     104                 :      17241 :     ulong x = c%p;
     105         [ +  + ]:      17241 :     P[i+2] = (x&1) ? p-1-(x>>1) : x>>1;
     106                 :      17241 :     c/=p;
     107                 :            :   }
     108                 :       3283 :   return Flx_renormalize(P, d+3);
     109                 :            : }
     110                 :            : 
     111                 :            : static GEN
     112                 :       7224 : factorel(GEN h, ulong p)
     113                 :            : {
     114                 :       7224 :   GEN F = Flx_factcantor(h, p, 0);
     115                 :       7224 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
     116                 :       7224 :   long i, l1 = lg(F1)-1;
     117                 :       7224 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
     118                 :       7224 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
     119         [ +  + ]:      35469 :   for (i = 1; i <= l1; ++i)
     120                 :            :   {
     121                 :      28245 :     p2[i] = Flx_cindex(gel(F1, i), p);
     122                 :      28245 :     e2[i] = F2[i];
     123                 :            :   }
     124                 :       7224 :   return mkmat2(p2, e2);
     125                 :            : }
     126                 :            : 
     127                 :            : static long
     128                 :      74256 : Flx_addifsmooth3(pari_sp *av, struct Flxq_log_rel *r, GEN h, long u, long v, long w, ulong p)
     129                 :            : {
     130                 :      74256 :   long off = r->off;
     131                 :      74256 :   r->nbtest++;
     132         [ +  + ]:      74256 :   if (Flx_is_smooth(h, r->r, p))
     133                 :            :   {
     134                 :       5670 :     GEN z = factorel(h, p);
     135         [ +  + ]:       5670 :     if (v<0)
     136                 :       1225 :       z = mkmat2(vecsmall_append(gel(z,1),off+u),vecsmall_append(gel(z,2),-1));
     137                 :            :     else
     138                 :       4445 :       z = famatsmall_reduce(mkmat2(
     139                 :       4445 :             vecsmall_concat(gel(z,1),mkvecsmall3(off+u,off+v,off+w)),
     140                 :       4445 :             vecsmall_concat(gel(z,2),mkvecsmall3(-1,-1,-1))));
     141                 :       5670 :     gel(r->rel,++r->nbrel) = gerepilecopy(*av,z);
     142 [ -  + ][ #  # ]:       5670 :     if (DEBUGLEVEL && (r->nbrel&511UL)==0)
     143                 :          0 :       err_printf("%ld%% ",r->nbrel*100/r->nbexp);
     144                 :       5670 :     *av = avma;
     145                 :      68586 :   } else avma = *av;
     146 [ +  + ][ -  + ]:      74256 :   return r->nbrel==r->nb || r->nbrel==r->nbmax;
     147                 :            : }
     148                 :            : 
     149                 :            : static void
     150                 :     367276 : Flx_renormalize_inplace(GEN x, long lx)
     151                 :            : {
     152                 :            :   long i;
     153         [ +  + ]:    3024273 :   for (i = lx-1; i>1; i--)
     154         [ +  + ]:    3021459 :     if (x[i]) break;
     155                 :     367276 :   setlg(x, i+1);
     156                 :     367276 : }
     157                 :            : 
     158                 :            : /*
     159                 :            :    Let T*X^e=C^3-R
     160                 :            :    a+b+c = 0
     161                 :            :    (C+a)*(C+b)*(C+c) = C^3+ (a*b+a*c+b*c)*C+a*b*c
     162                 :            :    = R + (a*b+a*c+b*c)*C+a*b*c
     163                 :            :    = R + (a*b-c^2)*C+a*b*c
     164                 :            :  */
     165                 :            : static void
     166                 :         14 : Flxq_log_cubic(struct Flxq_log_rel *r, GEN C, GEN R, ulong p)
     167                 :            : {
     168                 :         14 :   long l = lg(C);
     169                 :         14 :   GEN a = zero_zv(l); /*We allocate one extra word to catch overflow*/
     170                 :         14 :   GEN b = zero_zv(l);
     171                 :         14 :   pari_sp av = avma;
     172                 :         14 :   long i,j,k, dh=0;
     173                 :       2800 :   for(i=0; ; i++, Flx_cnext(a, p))
     174                 :            :   {
     175                 :       2800 :     Flx_renormalize_inplace(a, l+1);
     176                 :       2800 :     r->nb++;
     177         [ +  - ]:       2800 :     if (Flx_addifsmooth3(&av, r, Flx_add(a, C, p), i, -1, -1, p)) return;
     178         [ +  + ]:      29400 :     for(j=2; j<=l; j++) b[j] = 0;
     179         [ +  + ]:     353129 :     for(j=0; j<=i; j++, Flx_cnext(b, p))
     180                 :            :     {
     181                 :            :       GEN h,c;
     182                 :            :       GEN pab,pabc,pabc2;
     183                 :     350343 :       Flx_renormalize_inplace(b, l+1);
     184                 :     350343 :       c = Flx_neg(Flx_add(a,b,p),p);
     185                 :     350343 :       k = Flx_cindex(c, p);
     186         [ +  + ]:     350343 :       if (k > j) continue;
     187                 :      71456 :       pab  = Flx_mul(a, b, p);
     188                 :      71456 :       pabc = Flx_mul(pab,c,p);
     189                 :      71456 :       pabc2= Flx_sub(pab,Flx_sqr(c,p),p);
     190                 :      71456 :       h = Flx_add(R,Flx_add(Flx_mul(C,pabc2,p),pabc,p), p);
     191                 :      71456 :       h = Flx_normalize(h, p);
     192                 :      71456 :       dh = maxss(dh,degpol(h));
     193         [ +  + ]:      71456 :       if (Flx_addifsmooth3(&av, r, h, i, j, k, p)) return;
     194                 :            :     }
     195                 :       2800 :   }
     196                 :            : }
     197                 :            : 
     198                 :            : static GEN
     199                 :         63 : Flxq_log_find_rel(GEN b, long r, GEN T, ulong p, GEN *g, long *e)
     200                 :            : {
     201                 :         63 :   pari_sp av = avma;
     202                 :            :   while (1)
     203                 :            :   {
     204                 :            :     GEN M;
     205                 :        700 :     *g = Flxq_mul(*g, b, T, p); (*e)++;
     206                 :        700 :     M = Flx_halfgcd(*g,T,p);
     207         [ +  + ]:        700 :     if (Flx_is_smooth(gcoeff(M,1,1), r, p))
     208                 :            :     {
     209                 :        140 :       GEN z = Flx_add(Flx_mul(gcoeff(M,1,1),*g,p), Flx_mul(gcoeff(M,1,2),T,p),p);
     210         [ +  + ]:        140 :       if (Flx_is_smooth(z, r, p))
     211                 :            :       {
     212                 :         63 :         GEN F = factorel(z, p);
     213                 :         63 :         GEN G = factorel(gcoeff(M,1,1), p);
     214                 :         63 :         GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
     215                 :        126 :                          vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
     216                 :         63 :         gerepileall(av,2,g,&rel); return rel;
     217                 :            :       }
     218                 :            :     }
     219         [ -  + ]:        637 :     if (gc_needed(av,2))
     220                 :            :     {
     221         [ #  # ]:          0 :       if (DEBUGMEM>1) pari_warn(warnmem,"Flxq_log_find_rel");
     222                 :          0 :       *g = gerepilecopy(av, *g);
     223                 :            :     }
     224                 :        637 :   }
     225                 :            : }
     226                 :            : 
     227                 :            : /* Generalised Odlyzko formulae ( EUROCRYPT '84, LNCS 209, pp. 224-314, 1985. ) */
     228                 :            : /* Return the number of monic, k smooth, degree n polynomials for k=1..r */
     229                 :            : static GEN
     230                 :        518 : smoothness_vec(ulong p, long r, long n)
     231                 :            : {
     232                 :            :   long i,j,k;
     233                 :        518 :   GEN R = cgetg(r+1, t_VEC);
     234                 :        518 :   GEN V = cgetg(n+1, t_VEC);
     235         [ +  + ]:       6384 :   for (j = 1; j <= n; ++j)
     236                 :       5866 :     gel(V, j) =  binomialuu(p+j-1,j);
     237                 :        518 :   gel(R, 1) = gel(V, n);
     238         [ +  + ]:       1652 :   for (k = 2; k <= r; ++k)
     239                 :            :   {
     240                 :       1134 :     GEN W = cgetg(n+1, t_VEC);
     241                 :       1134 :     GEN Ik = ffnbirred(utoi(p),k);
     242         [ +  + ]:      12936 :     for (j = 1; j <= n; ++j)
     243                 :            :     {
     244                 :      11802 :       long l = j/k;
     245                 :      11802 :       GEN s = gen_0;
     246                 :      11802 :       pari_sp av2 = avma;
     247         [ +  + ]:      11802 :       if (l*k == j)
     248                 :            :       {
     249                 :       3906 :         s = binomial(addis(Ik,l-1), l);
     250                 :       3906 :         l--;
     251                 :            :       }
     252         [ +  + ]:      42686 :       for (i = 0; i <= l; ++i)
     253                 :      30884 :         s = addii(s, mulii(gel(V, j-k*i), binomial(addis(Ik,i-1), i)));
     254                 :      11802 :       gel(W, j) = gerepileuptoint(av2, s);
     255                 :            :     }
     256                 :       1134 :     V = W;
     257                 :       1134 :     gel(R, k) = gel(V, n);
     258                 :            :   }
     259                 :        518 :   return R;
     260                 :            : }
     261                 :            : 
     262                 :            : /* Solve N^2*pr/6 + N*prC = N+fb
     263                 :            :    N^2*pr/6 + N*(prC-1) -fb = 0
     264                 :            :  */
     265                 :            : 
     266                 :            : static GEN
     267                 :        434 : smooth_cost(GEN fb, GEN pr, GEN prC)
     268                 :            : {
     269                 :        434 :   GEN a = gdivgs(pr,6);
     270                 :        434 :   GEN b = gsubgs(prC,1);
     271                 :        434 :   GEN c = gneg(fb);
     272                 :        434 :   GEN vD = gsqrt(gsub(gsqr(b),gmul2n(gmul(a,c),2)),BIGDEFAULTPREC);
     273                 :        434 :   return ceil_safe(gdiv(gsub(vD,b),gmul2n(a,1)));
     274                 :            : }
     275                 :            : 
     276                 :            : /* Return best choice of r.
     277                 :            :    We loop over d until there is sufficiently many triples (a,b,c) (a+b+c=0)
     278                 :            :    of degree <=d with respect to the probability of smoothness of (a*b-c^2)*C
     279                 :            :  */
     280                 :            : 
     281                 :            : static GEN
     282                 :         14 : smooth_best(long p, long n, long *pt_r, long *pt_nb)
     283                 :            : {
     284                 :         14 :   pari_sp av = avma, av2;
     285                 :         14 :   GEN bestc = NULL;
     286                 :         14 :   long bestr = 0, bestFB = 0;
     287                 :         14 :   long r,d, dC = (n+2)/3;
     288         [ +  + ]:         98 :   for (r = 1; r < dC; ++r)
     289                 :            :   {
     290                 :         84 :     GEN fb = ffsumnbirred(utoi(p), r);
     291                 :         84 :     GEN smoothC = smoothness_vec(p,r,dC);
     292                 :         84 :     GEN prC = gdiv(gel(smoothC,r), powuu(p,dC));
     293                 :         84 :     ulong rels = 0;
     294                 :         84 :     av2 = avma;
     295 [ +  + ][ +  - ]:        469 :     for(d=0; d<dC && rels < ULONG_MAX; d++)
     296                 :            :     {
     297                 :            :       GEN c;
     298                 :        434 :       long dt = dC+2*d;
     299                 :        434 :       GEN smooth = smoothness_vec(p,r,dt);
     300                 :        434 :       GEN pr = gdiv(gel(smooth,r), powuu(p,dt));
     301                 :        434 :       GEN FB = addii(fb,powuu(p,d));
     302                 :        434 :       GEN N = smooth_cost(subiu(FB,rels),pr,prC);
     303                 :        434 :       GEN Nmax = powuu(p,d+1);
     304         [ +  + ]:        434 :       if (gcmp(N,Nmax) >= 0)
     305                 :            :       {
     306                 :        385 :         rels = itou_or_0(addui(rels, gceil(gmul(gdivgs(sqri(Nmax),6),pr))));
     307         [ -  + ]:        385 :         if (!rels) rels = ULONG_MAX;
     308                 :        385 :         avma = av2;
     309                 :        385 :         continue;
     310                 :            :       }
     311                 :         49 :       c = gdivgs(addii(powuu(p,2*d),sqri(N)),6);
     312                 :         49 :       FB = addii(FB,N);
     313 [ +  + ][ +  + ]:         49 :       if ((!bestc || gcmp(gmul2n(c,r), gmul2n(bestc,bestr)) < 0))
     314                 :            :       {
     315         [ -  + ]:         21 :         if (DEBUGLEVEL)
     316                 :          0 :           err_printf("r=%ld d=%ld fb=%Ps early rels=%lu P=%.5Pe -> C=%.5Pe \n",
     317                 :            :                       r, dt, FB, rels, pr, c);
     318                 :         21 :         bestc = c;
     319                 :         21 :         bestr = r;
     320                 :         21 :         bestFB = itos_or_0(FB);
     321                 :            :       }
     322                 :         49 :       break;
     323                 :            :     }
     324                 :            :   }
     325                 :         14 :   *pt_r=bestr;
     326                 :         14 :   *pt_nb=bestFB;
     327         [ +  - ]:         14 :   return bestc ? gerepileupto(av, gceil(bestc)): NULL;
     328                 :            : }
     329                 :            : 
     330                 :            : static GEN
     331                 :         21 : check_kernel(long r, GEN M, long nbi, long nbrow, GEN T, ulong p, GEN m)
     332                 :            : {
     333                 :         21 :   pari_sp av = avma;
     334                 :         21 :   long N = 3*upowuu(p, r);
     335                 :         21 :   GEN K = FpMs_leftkernel_elt(M, nbrow, m);
     336                 :         21 :   long i, f=0;
     337                 :         21 :   long lm = lgefint(m), u=1;
     338                 :            :   GEN g;
     339                 :         21 :   GEN idx = diviiexact(subis(powuu(p,degpol(T)),1),m);
     340                 :            :   pari_timer ti;
     341         [ -  + ]:         21 :   if (DEBUGLEVEL) timer_start(&ti);
     342         [ +  + ]:        182 :   while (signe(gel(K,u))==0)
     343                 :        161 :    u++;
     344                 :         21 :   K = FpC_Fp_mul(K, Fp_inv(gel(K, u), m), m);
     345                 :         21 :   g = Flxq_pow(cindex_Flx(u, r, p, T[1]), idx, T, p);
     346                 :         21 :   setlg(K, N);
     347         [ +  + ]:      31353 :   for (i=1; i<N; i++)
     348                 :            :   {
     349                 :      31332 :     GEN k = gel(K,i);
     350                 :      31332 :     pari_sp av = avma;
     351 [ +  + ][ +  - ]:      31332 :     long t = signe(k) && Flx_equal(Flxq_pow(g, k, T, p),
     352                 :       3143 :                                    Flxq_pow(cindex_Flx(i,r,p,T[1]), idx, T, p));
     353                 :      31332 :     avma = av;
     354         [ +  + ]:      31332 :     if (!t)
     355                 :      28189 :       gel(K,i) = cgetineg(lm);
     356                 :            :     else
     357                 :       3143 :       f++;
     358                 :            :   }
     359         [ -  + ]:         21 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
     360         [ -  + ]:         21 :   if (f < maxss(3,maxss(p/2,nbi/p))) return NULL; /* Not enough logs found */
     361                 :         21 :   return gerepilecopy(av, K);
     362                 :            : }
     363                 :            : 
     364                 :            : static GEN
     365                 :         28 : Flxq_log_rec(GEN W, GEN a, long r, GEN T, ulong p, GEN m)
     366                 :            : {
     367                 :         28 :   long AV = 0, u = 1;
     368                 :         28 :   GEN g = a, b;
     369                 :            :   pari_timer ti;
     370         [ +  + ]:        280 :   while (!equali1(gel(W,u)))
     371                 :        252 :    u++;
     372                 :         28 :   b = cindex_Flx(u, r, p, T[1]);
     373                 :            :   while(1)
     374                 :            :   {
     375                 :            :     long i, l;
     376                 :            :     GEN V, F, E, Ao;
     377                 :         49 :     timer_start(&ti);
     378                 :         49 :     V = Flxq_log_find_rel(b, r, T, p, &g, &AV);
     379         [ -  + ]:         49 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r);
     380                 :         49 :     F = gel(V,1); E = gel(V,2);
     381                 :         49 :     l = lg(F);
     382                 :         49 :     Ao = gen_0;
     383         [ +  + ]:        308 :     for(i=1; i<l; i++)
     384                 :            :     {
     385                 :        280 :       GEN R = gel(W,F[i]);
     386         [ +  + ]:        280 :       if (signe(R)<=0)
     387                 :         21 :         break;
     388                 :        259 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
     389                 :            :     }
     390         [ +  + ]:         49 :     if (i==l) return subis(Ao,AV);
     391                 :         21 :   }
     392                 :            : }
     393                 :            : 
     394                 :            : static GEN
     395                 :         14 : Flxq_log_index_cubic(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
     396                 :            : {
     397                 :         14 :   long n = get_Flx_degree(T0), r, nb;
     398                 :         14 :   pari_sp av = avma;
     399                 :            :   struct Flxq_log_rel rel;
     400                 :            :   long nbi;
     401                 :            :   GEN W, M, S, T, a, b, Ao, Bo, e, C, R;
     402                 :            :   pari_timer ti;
     403                 :         14 :   GEN cost = smooth_best(p, n, &r, &nb);
     404                 :         14 :   GEN cost_rho = sqrti(shifti(m,2));
     405 [ +  - ][ -  + ]:         14 :   if (!cost || gcmp(cost,cost_rho)>=0) { avma = av; return NULL; }
     406                 :         14 :   nbi = itos(ffsumnbirred(stoi(p), r));
     407         [ -  + ]:         14 :   if (DEBUGLEVEL)
     408                 :            :   {
     409                 :          0 :     err_printf("Size FB=%ld, looking for %ld relations, %Ps tests needed\n", nbi, nb,cost);
     410                 :          0 :     timer_start(&ti);
     411                 :            :   }
     412                 :         14 :   T = smallirred_Flx(p,n,get_Flx_var(T0));
     413                 :            :   for(;;)
     414                 :            :   {
     415                 :         14 :     S = Flx_ffisom(T0,T,p);
     416                 :         14 :     a = Flx_Flxq_eval(a0, S, T, p);
     417                 :         14 :     b = Flx_Flxq_eval(b0, S, T, p);
     418                 :         14 :     C = Flx_shift(pol1_Flx(get_Flx_var(T)), (n+2)/3);
     419                 :         14 :     R = Flxq_powu(C,3,T,p);
     420         [ -  + ]:         14 :     if (DEBUGLEVEL)
     421                 :          0 :       timer_printf(&ti," model change: %Ps",Flx_to_ZX(T));
     422                 :         14 :     rel.nbmax=2*nb;
     423                 :         14 :     M = cgetg(rel.nbmax+1, t_VEC);
     424                 :         14 :     rel.rel = M;
     425                 :         14 :     rel.nbrel = 0; rel.r = r; rel.off = 3*upowuu(p,r);
     426                 :         14 :     rel.nb = nbi; rel.nbexp = nb; rel.nbtest=0;
     427                 :         14 :     Flxq_log_cubic(&rel, C, R, p);
     428                 :         14 :     setlg(M,1+rel.nbrel);
     429         [ -  + ]:         14 :     if (DEBUGLEVEL)
     430                 :            :     {
     431                 :          0 :       err_printf("\n");
     432                 :          0 :       timer_printf(&ti," %ld relations, %ld generators (%ld tests)",rel.nbrel,rel.nb,rel.nbtest);
     433                 :            :     }
     434                 :         14 :     W = check_kernel(r, M, nbi, rel.off + rel.nb - nbi, T, p, m);
     435         [ +  - ]:         14 :     if (W) break;
     436         [ #  # ]:          0 :     if (DEBUGLEVEL) timer_start(&ti);
     437                 :          0 :     smallirred_Flx_next(T,p);
     438                 :          0 :   }
     439         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_start(&ti);
     440                 :         14 :   Ao = Flxq_log_rec(W, a, r, T, p, m);
     441         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
     442                 :         14 :   Bo = Flxq_log_rec(W, b, r, T, p, m);
     443         [ -  + ]:         14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
     444                 :         14 :   e = Fp_div(Ao, Bo, m);
     445         [ -  + ]:         14 :   if (!Flx_equal(Flxq_pow(b0, e, T0, p), a0)) pari_err_BUG("Flxq_log");
     446                 :         14 :   return gerepileupto(av, e);
     447                 :            : }
     448                 :            : 
     449                 :       5726 : INLINE GEN Flx_frob(GEN u, ulong p) { return Flx_inflate(u, p); }
     450                 :            : 
     451                 :            : static GEN
     452                 :       9996 : rel_Coppersmith(long r, GEN u, GEN v, long h, GEN R, long d, ulong p)
     453                 :            : {
     454                 :            :   GEN a, b, F, G, M;
     455         [ +  + ]:       9996 :   if (degpol(Flx_gcd(u,v,p))) return NULL;
     456                 :       6881 :   a = Flx_add(Flx_shift(u, h), v, p);
     457 [ +  - ][ +  + ]:       6881 :   if (lgpol(a)==0 || !Flx_is_smooth(a, r, p)) return NULL;
     458                 :       2835 :   b = Flx_add(Flx_mul(R, Flx_frob(u, p), p), Flx_shift(Flx_frob(v, p),d), p);
     459         [ +  + ]:       2835 :   if (!Flx_is_smooth(b, r, p)) return NULL;
     460                 :        707 :   F = factorel(a, p); G = factorel(b, p);
     461                 :        707 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2*p)),
     462                 :       1414 :              vecsmall_concat(zv_z_mul(gel(F, 2),p), vecsmall_append(zv_neg(gel(G, 2)),d)));
     463                 :       9996 :   return famatsmall_reduce(M);
     464                 :            : }
     465                 :            : 
     466                 :            : static GEN
     467                 :          7 : Flxq_log_Coppersmith(long nbrel, long r, GEN T, ulong p)
     468                 :            : {
     469                 :          7 :   long dT = degpol(T);
     470                 :          7 :   long h = dT/p, d = dT-(h*p);
     471                 :          7 :   GEN R = Flx_sub(Flx_shift(pol1_Flx(T[1]), dT), T, p);
     472                 :          7 :   GEN u = zero_zv(dT+2), v = zero_zv(dT+2);
     473                 :          7 :   long nbtest = 0, rel = 0;
     474                 :          7 :   GEN M = cgetg(nbrel+1, t_VEC);
     475                 :          7 :   pari_sp av = avma;
     476                 :            :   long i, j;
     477         [ -  + ]:          7 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",degpol(R));
     478                 :          7 :   for (i=1; ; i++)
     479                 :            :   {
     480                 :        448 :     Flx_cnext(u, p);
     481                 :        448 :     Flx_renormalize_inplace(u, dT+2);
     482         [ +  + ]:       2268 :     for(j=2; j<lg(v); j++) v[j] = 0;
     483         [ +  + ]:      14126 :     for(j=1; j<i; j++)
     484                 :            :     {
     485                 :            :       GEN z;
     486                 :      13685 :       Flx_cnext(v, p);
     487                 :      13685 :       Flx_renormalize_inplace(v, dT+2);
     488                 :      13685 :       avma = av;
     489         [ +  + ]:      13685 :       if (Flx_lead(u)==1)
     490                 :            :       {
     491                 :       5495 :         z = rel_Coppersmith(r, u, v, h, R, d, p);
     492                 :       5495 :         nbtest++;
     493         [ +  + ]:       5495 :         if (z)
     494                 :            :         {
     495                 :        322 :           gel(M,++rel) = gerepilecopy(av, z); av = avma;
     496 [ -  + ][ #  # ]:        322 :           if (DEBUGLEVEL && (rel&511UL)==0)
     497                 :          0 :             err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
     498                 :            :         }
     499         [ +  + ]:       5495 :         if (rel>nbrel) break;
     500                 :            :       }
     501         [ -  + ]:      13678 :       if (i==j) continue;
     502         [ +  + ]:      13678 :       if (Flx_lead(v)==1)
     503                 :            :       {
     504                 :       4501 :         z = rel_Coppersmith(r, v, u, h, R, d, p);
     505                 :       4501 :         nbtest++;
     506         [ +  + ]:       4501 :         if (z)
     507                 :            :         {
     508                 :        385 :           gel(M,++rel) = gerepilecopy(av, z); av = avma;
     509 [ -  + ][ #  # ]:        385 :           if (DEBUGLEVEL && (rel&511UL)==0)
     510                 :          0 :             err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
     511                 :            :         }
     512         [ -  + ]:       4501 :         if (rel>nbrel) break;
     513                 :            :       }
     514                 :            :     }
     515         [ +  + ]:        448 :     if (rel>nbrel) break;
     516                 :        441 :   }
     517         [ -  + ]:          7 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
     518                 :          7 :   return M;
     519                 :            : }
     520                 :            : 
     521                 :            : static GEN Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, GEN mo);
     522                 :            : 
     523                 :            : static GEN
     524                 :          7 : Flxq_log_from_rel(GEN W, GEN rel, long r, GEN T, ulong p, GEN m)
     525                 :            : {
     526                 :          7 :   pari_sp av = avma;
     527                 :          7 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
     528                 :          7 :   long i, l = lg(F);
     529         [ +  + ]:         42 :   for(i=1; i<l; i++)
     530                 :            :   {
     531                 :         35 :     GEN R = gel(W, F[i]);
     532         [ -  + ]:         35 :     if (signe(R)==0) /* Already failed */
     533                 :          0 :       return NULL;
     534         [ -  + ]:         35 :     else if (signe(R)<0) /* Not yet tested */
     535                 :            :     {
     536                 :          0 :       setsigne(gel(W,F[i]),0);
     537                 :          0 :       R = Flxq_log_Coppersmith_d(W, cindex_Flx(F[i],r,p,T[1]), r, T, p, m);
     538         [ #  # ]:          0 :       if (!R) return NULL;
     539                 :            :     }
     540                 :         35 :     o = Fp_add(o, mulis(R, E[i]), m);
     541                 :            :   }
     542                 :          7 :   return gerepileuptoint(av, o);
     543                 :            : }
     544                 :            : 
     545                 :            : static GEN
     546                 :          7 : Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, GEN mo)
     547                 :            : {
     548                 :          7 :   pari_sp av = avma, av2;
     549                 :          7 :   long dg = degpol(g), k = r-1, m = maxss((dg-k)/2,0);
     550                 :          7 :   long i, j, l = dg-m, N;
     551                 :          7 :   GEN v = cgetg(k+m+1,t_MAT);
     552                 :          7 :   long dT = degpol(T);
     553                 :          7 :   long h = dT/p, d = dT-h*p;
     554                 :          7 :   GEN R = Flx_rem(Flx_shift(pol1_Flx(T[1]), dT), T, p);
     555                 :          7 :   GEN z = Flx_rem(Flx_shift(pol1_Flx(T[1]), h), g, p);
     556         [ +  + ]:         42 :   for(i=1; i<=k+m; i++)
     557                 :            :   {
     558                 :         35 :     gel(v,i) = Flx_to_Flv(Flx_shift(z,-l),m);
     559                 :         35 :     z = Flx_rem(Flx_shift(z,1),g,p);
     560                 :            :   }
     561                 :          7 :   v = Flm_ker(v,p);
     562         [ +  + ]:         35 :   for(i=1; i<=k; i++)
     563                 :         28 :     gel(v,i) = Flv_to_Flx(gel(v,i),T[1]);
     564                 :          7 :   N = upowuu(p,k);
     565                 :          7 :   av2 = avma;
     566         [ +  - ]:         28 :   for (i=1; i<N; i++)
     567                 :            :   {
     568                 :            :     GEN p0,q,qh,a,b;
     569                 :         28 :     ulong el = i;
     570                 :         28 :     avma = av2;
     571                 :         28 :     q = pol0_Flx(T[1]);
     572         [ +  + ]:        140 :     for (j=1; j<=k; j++)
     573                 :            :     {
     574                 :        112 :       ulong r = el % p;
     575                 :        112 :       el /= p;
     576         [ +  + ]:        112 :       if (r) q = Flx_add(q, Flx_Fl_mul(gel(v,j), r, p), p);
     577                 :            :     }
     578                 :         28 :     qh = Flx_shift(q, h);
     579                 :         28 :     p0 = Flx_rem(qh, g, p);
     580                 :         28 :     b = Flx_sub(Flx_mul(R, Flx_frob(q, p), p), Flx_shift(Flx_frob(p0, p), d), p);
     581 [ +  - ][ +  + ]:         28 :     if (lgpol(b)==0 || !Flx_is_smooth(b, r, p)) continue;
     582                 :          7 :     a = Flx_div(Flx_sub(qh, p0, p), g, p);
     583 [ -  + ][ #  # ]:          7 :     if (degpol(Flx_gcd(a, q, p)) &&  degpol(Flx_gcd(a, p0 ,p)))
     584                 :          0 :       continue;
     585 [ +  - ][ +  - ]:          7 :     if (!(lgpol(a)==0 || !Flx_is_smooth(a, r, p)))
     586                 :            :     {
     587                 :          7 :       GEN F = factorel(b, p);
     588                 :          7 :       GEN G = factorel(a, p);
     589                 :          7 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2*p), gel(G, 1));
     590                 :          7 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
     591                 :         14 :           zv_z_mul(gel(G, 2),-p));
     592                 :          7 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
     593                 :          7 :       GEN l  = Flxq_log_from_rel(W, R, r, T, p, mo);
     594         [ -  + ]:          7 :       if (!l) continue;
     595                 :          7 :       l = Fp_div(l,utoi(p),mo);
     596         [ -  + ]:          7 :       if (dg <= r)
     597                 :            :       {
     598                 :          0 :         affii(l,gel(W,g[2]));
     599         [ #  # ]:          0 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", g[2]);
     600                 :            :       }
     601                 :          7 :       return gerepileuptoint(av, l);
     602                 :            :     }
     603                 :            :   }
     604                 :          0 :   avma = av;
     605                 :          7 :   return NULL;
     606                 :            : }
     607                 :            : 
     608                 :            : static GEN
     609                 :         14 : Flxq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, GEN T, ulong p, GEN m)
     610                 :            : {
     611                 :         14 :   GEN b = polx_Flx(T[1]);
     612                 :         14 :   long AV = 0;
     613                 :         14 :   GEN g = a, bad = pol0_Flx(T[1]);
     614                 :            :   pari_timer ti;
     615                 :            :   while(1)
     616                 :            :   {
     617                 :            :     long i, l;
     618                 :            :     GEN V, F, E, Ao;
     619                 :         14 :     timer_start(&ti);
     620                 :         14 :     V = Flxq_log_find_rel(b, r2, T, p, &g, &AV);
     621         [ -  + ]:         14 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
     622                 :         14 :     F = gel(V,1); E = gel(V,2);
     623                 :         14 :     l = lg(F);
     624                 :         14 :     Ao = gen_0;
     625         [ +  + ]:        105 :     for(i=1; i<l; i++)
     626                 :            :     {
     627                 :         91 :       GEN Fi = cindex_Flx(F[i], r2, p, T[1]);
     628                 :            :       GEN R;
     629         [ +  + ]:         91 :       if (degpol(Fi) <= r)
     630                 :            :       {
     631         [ -  + ]:         84 :         if (signe(gel(W,F[i]))==0)
     632                 :          0 :           break;
     633         [ -  + ]:         84 :         else if (signe(gel(W,F[i]))<0)
     634                 :            :         {
     635                 :          0 :           setsigne(gel(W,F[i]),0);
     636                 :          0 :           R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,m);
     637                 :            :         } else
     638                 :         84 :           R = gel(W,F[i]);
     639                 :            :       }
     640                 :            :       else
     641                 :            :       {
     642         [ -  + ]:          7 :         if (Flx_equal(Fi,bad)) break;
     643                 :          7 :         R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,m);
     644         [ -  + ]:          7 :         if (!R) bad = Fi;
     645                 :            :       }
     646         [ -  + ]:         91 :       if (!R) break;
     647                 :         91 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
     648                 :            :     }
     649         [ +  - ]:         14 :     if (i==l) return subis(Ao,AV);
     650                 :          0 :   }
     651                 :            : }
     652                 :            : 
     653                 :            : 
     654                 :            : static GEN
     655                 :          7 : Flxq_log_index_Coppersmith(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
     656                 :            : {
     657                 :          7 :   pari_sp av = avma;
     658                 :          7 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
     659                 :            :   pari_timer ti;
     660         [ +  - ]:          7 :   double rf = p ==3 ? 1.2 : .9;
     661                 :          7 :   long n = degpol(T0), r = (long) sqrt(n*rf);
     662                 :            :   GEN T;
     663                 :          7 :   long r2 = 3*r/2;
     664                 :          7 :   long nbi = itos(ffsumnbirred(utoi(p), r)), nbrel=nbi*5/4;
     665         [ -  + ]:          7 :   if (DEBUGLEVEL)
     666                 :            :   {
     667                 :          0 :     err_printf("Coppersmith: Parameters r=%ld r2=%ld\n", r,r2);
     668                 :          0 :     err_printf("Coppersmith: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
     669                 :          0 :     timer_start(&ti);
     670                 :            :   }
     671                 :          7 :   T = smallirred_Flx(p,n,get_Flx_var(T0));
     672                 :          7 :   S = Flx_ffisom(T0,T,p);
     673                 :          7 :   a = Flx_Flxq_eval(a0, S, T, p);
     674                 :          7 :   b = Flx_Flxq_eval(b0, S, T, p);
     675         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
     676                 :          7 :   M = Flxq_log_Coppersmith(nbrel, r, T, p);
     677         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"relations");
     678                 :          7 :   W = check_kernel(r, M, nbi, 3*upowuu(p,r), T, p, m);
     679                 :          7 :   timer_start(&ti);
     680                 :          7 :   Ao = Flxq_log_Coppersmith_rec(W, r2, a, r, T, p, m);
     681         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
     682                 :          7 :   Bo = Flxq_log_Coppersmith_rec(W, r2, b, r, T, p, m);
     683         [ -  + ]:          7 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
     684                 :          7 :   e = Fp_div(Ao, Bo, m);
     685         [ -  + ]:          7 :   if (!Flx_equal(Flxq_pow(b0,e,T0,p),a0)) pari_err_BUG("Flxq_log");
     686                 :          7 :   return gerepileupto(av, e);
     687                 :            : }
     688                 :            : 
     689                 :            : GEN
     690                 :         21 : Flxq_log_index(GEN a, GEN b, GEN m, GEN T, ulong p)
     691                 :            : {
     692 [ +  + ][ +  - ]:         21 :   if (p==3 || (p==5 && degpol(T)>41))
                 [ -  + ]
     693                 :          7 :     return Flxq_log_index_Coppersmith(a, b, m, T, p);
     694                 :         21 :   else    return Flxq_log_index_cubic(a, b, m, T, p);
     695                 :            : }

Generated by: LCOV version 1.9