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 - Flxq_log.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.10.0 lcov report (development 19832-7f23dbb) Lines: 445 474 93.9 %
Date: 2016-12-08 05:49:22 Functions: 29 29 100.0 %
Legend: Lines: hit not hit

          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      378918 : Flx_cindex(GEN P, ulong p)
      23             : {
      24      378918 :   long d = degpol(P), i;
      25      378918 :   ulong s = 0, p2 = (p-1)>>1;
      26     1712807 :   for (i = 0; i <= d; ++i)
      27             :   {
      28     1333889 :     ulong x = P[d-i+2];
      29     1333889 :     if (x<=p2) x = 2*x; else x = 1+2*(p-1-x);
      30     1333889 :     s = p*s+x;
      31             :   }
      32      378918 :   return s;
      33             : }
      34             : 
      35             : /* Compute the polynomial immediately after t for the [[ order */
      36             : 
      37             : static void
      38      371681 : Flx_cnext(GEN t, ulong p)
      39             : {
      40             :   long i;
      41      371681 :   long p2 = p>>1;
      42      463890 :   for(i=2;;i++)
      43      463890 :     if (t[i]==p2)
      44       92209 :       t[i]=0;
      45             :     else
      46             :     {
      47      371681 :       t[i] = t[i]<p2 ? p-1-t[i]: p-t[i];
      48      371681 :       break;
      49       92209 :     }
      50      371681 : }
      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         756 :     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        3294 : cindex_Flx(long c, long d, ulong p, long v)
      98             : {
      99        3294 :   GEN P = cgetg(d+3, t_VECSMALL);
     100             :   long i;
     101        3294 :   P[1] = v;
     102       20627 :   for (i = 0; i <= d; ++i)
     103             :   {
     104       17333 :     ulong x = c%p;
     105       17333 :     P[i+2] = (x&1) ? p-1-(x>>1) : x>>1;
     106       17333 :     c/=p;
     107             :   }
     108        3294 :   return Flx_renormalize(P, d+3);
     109             : }
     110             : 
     111             : static GEN
     112        7322 : factorel(GEN h, ulong p)
     113             : {
     114        7322 :   GEN F = Flx_factcantor(h, p, 0);
     115        7322 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
     116        7322 :   long i, l1 = lg(F1)-1;
     117        7322 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
     118        7322 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
     119       35897 :   for (i = 1; i <= l1; ++i)
     120             :   {
     121       28575 :     p2[i] = Flx_cindex(gel(F1, i), p);
     122       28575 :     e2[i] = F2[i];
     123             :   }
     124        7322 :   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       13335 :       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      371710 : Flx_renormalize_inplace(GEN x, long lx)
     151             : {
     152             :   long i;
     153     3114421 :   for (i = lx-1; i>1; i--)
     154     3111657 :     if (x[i]) break;
     155      371710 :   setlg(x, i+1);
     156      371715 : }
     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             :   long i,j,k;
     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        2800 :     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 :       if (Flx_addifsmooth3(&av, r, h, i, j, k, p)) return;
     193             :     }
     194        2786 :   }
     195             : }
     196             : 
     197             : static GEN
     198          60 : Flxq_log_find_rel(GEN b, long r, GEN T, ulong p, GEN *g, long *e)
     199             : {
     200          60 :   pari_sp av = avma;
     201             :   while (1)
     202             :   {
     203             :     GEN M;
     204        4142 :     *g = Flxq_mul(*g, b, T, p); (*e)++;
     205        4142 :     M = Flx_halfgcd(*g,T,p);
     206        4142 :     if (Flx_is_smooth(gcoeff(M,1,1), r, p))
     207             :     {
     208         670 :       GEN z = Flx_add(Flx_mul(gcoeff(M,1,1),*g,p), Flx_mul(gcoeff(M,1,2),T,p),p);
     209         670 :       if (Flx_is_smooth(z, r, p))
     210             :       {
     211          60 :         GEN F = factorel(z, p);
     212          60 :         GEN G = factorel(gcoeff(M,1,1), p);
     213         120 :         GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
     214         120 :                          vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
     215         120 :         gerepileall(av,2,g,&rel); return rel;
     216             :       }
     217             :     }
     218        4082 :     if (gc_needed(av,2))
     219             :     {
     220           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"Flxq_log_find_rel");
     221           0 :       *g = gerepilecopy(av, *g);
     222             :     }
     223        4082 :   }
     224             : }
     225             : 
     226             : /* Generalised Odlyzko formulae ( EUROCRYPT '84, LNCS 209, pp. 224-314, 1985. ) */
     227             : /* Return the number of monic, k smooth, degree n polynomials for k=1..r */
     228             : static GEN
     229        1708 : smoothness_vec(ulong p, long r, long n)
     230             : {
     231             :   long i,j,k;
     232        1708 :   GEN R = cgetg(r+1, t_VEC);
     233        1708 :   GEN V = cgetg(n+1, t_VEC);
     234       18571 :   for (j = 1; j <= n; ++j)
     235       16863 :     gel(V, j) =  binomialuu(p+j-1,j);
     236        1708 :   gel(R, 1) = gel(V, n);
     237        4816 :   for (k = 2; k <= r; ++k)
     238             :   {
     239        3108 :     GEN W = cgetg(n+1, t_VEC);
     240        3108 :     GEN Ik = ffnbirred(utoi(p),k);
     241       36029 :     for (j = 1; j <= n; ++j)
     242             :     {
     243       32921 :       long l = j/k;
     244       32921 :       GEN s = gen_0;
     245       32921 :       pari_sp av2 = avma;
     246       32921 :       if (l*k == j)
     247             :       {
     248       10801 :         s = binomial(addis(Ik,l-1), l);
     249       10801 :         l--;
     250             :       }
     251      119847 :       for (i = 0; i <= l; ++i)
     252       86926 :         s = addii(s, mulii(gel(V, j-k*i), binomial(addis(Ik,i-1), i)));
     253       32921 :       gel(W, j) = gerepileuptoint(av2, s);
     254             :     }
     255        3108 :     V = W;
     256        3108 :     gel(R, k) = gel(V, n);
     257             :   }
     258        1708 :   return R;
     259             : }
     260             : 
     261             : /* Solve N^2*pr/6 + N*prC = N+fb
     262             :    N^2*pr/6 + N*(prC-1) -fb = 0
     263             :  */
     264             : 
     265             : static GEN
     266        1379 : smooth_cost(GEN fb, GEN pr, GEN prC)
     267             : {
     268        1379 :   GEN a = gdivgs(pr,6);
     269        1379 :   GEN b = gsubgs(prC,1);
     270        1379 :   GEN c = gneg(fb);
     271        1379 :   GEN vD = gsqrt(gsub(gsqr(b),gmul2n(gmul(a,c),2)),BIGDEFAULTPREC);
     272        1379 :   return ceil_safe(gdiv(gsub(vD,b),gmul2n(a,1)));
     273             : }
     274             : 
     275             : /* Return best choice of r.
     276             :    We loop over d until there is sufficiently many triples (a,b,c) (a+b+c=0)
     277             :    of degree <=d with respect to the probability of smoothness of (a*b-c^2)*C
     278             :  */
     279             : 
     280             : static GEN
     281         140 : smooth_best(long p, long n, long *pt_r, long *pt_nb)
     282             : {
     283         140 :   pari_sp av = avma, av2;
     284         140 :   GEN bestc = NULL;
     285         140 :   long bestr = 0, bestFB = 0;
     286         140 :   long r,d, dC = (n+2)/3;
     287         469 :   for (r = 1; r < dC; ++r)
     288             :   {
     289         329 :     GEN fb = ffsumnbirred(utoi(p), r);
     290         329 :     GEN smoothC = smoothness_vec(p,r,dC);
     291         329 :     GEN prC = gdiv(gel(smoothC,r), powuu(p,dC));
     292         329 :     ulong rels = 0;
     293         329 :     av2 = avma;
     294        2954 :     for(d=0; d<dC && rels < ULONG_MAX; d++)
     295             :     {
     296             :       GEN c;
     297        1379 :       long dt = dC+2*d;
     298        1379 :       GEN smooth = smoothness_vec(p,r,dt);
     299        1379 :       GEN pr = gdiv(gel(smooth,r), powuu(p,dt));
     300        1379 :       GEN FB = addii(fb,powuu(p,d));
     301        1379 :       GEN N = smooth_cost(subiu(FB,rels),pr,prC);
     302        1379 :       GEN Nmax = powuu(p,d+1);
     303        1379 :       if (gcmp(N,Nmax) >= 0)
     304             :       {
     305        1148 :         rels = itou_or_0(addui(rels, gceil(gmul(gdivgs(sqri(Nmax),6),pr))));
     306        1148 :         if (!rels) rels = ULONG_MAX;
     307        1148 :         avma = av2;
     308        1148 :         continue;
     309             :       }
     310         231 :       c = gdivgs(addii(powuu(p,2*d),sqri(N)),6);
     311         231 :       FB = addii(FB,N);
     312         231 :       if ((!bestc || gcmp(gmul2n(c,r), gmul2n(bestc,bestr)) < 0))
     313             :       {
     314         154 :         if (DEBUGLEVEL)
     315           0 :           err_printf("r=%ld d=%ld fb=%Ps early rels=%lu P=%.5Pe -> C=%.5Pe \n",
     316             :                       r, dt, FB, rels, pr, c);
     317         154 :         bestc = c;
     318         154 :         bestr = r;
     319         154 :         bestFB = itos_or_0(FB);
     320             :       }
     321         231 :       break;
     322             :     }
     323             :   }
     324         140 :   *pt_r=bestr;
     325         140 :   *pt_nb=bestFB;
     326         140 :   return bestc ? gerepileupto(av, gceil(bestc)): NULL;
     327             : }
     328             : 
     329             : static GEN
     330          21 : check_kernel(long r, GEN M, long nbi, long nbrow, GEN T, ulong p, GEN m)
     331             : {
     332          21 :   pari_sp av = avma;
     333          21 :   long N = 3*upowuu(p, r);
     334          21 :   GEN K = FpMs_leftkernel_elt(M, nbrow, m);
     335          21 :   long i, f=0;
     336          21 :   long lm = lgefint(m), u=1;
     337             :   GEN g;
     338          21 :   GEN idx = diviiexact(subis(powuu(p,degpol(T)),1),m);
     339             :   pari_timer ti;
     340          21 :   if (DEBUGLEVEL) timer_start(&ti);
     341         203 :   while (signe(gel(K,u))==0)
     342         161 :    u++;
     343          21 :   K = FpC_Fp_mul(K, Fp_inv(gel(K, u), m), m);
     344          21 :   g = Flxq_pow(cindex_Flx(u, r, p, T[1]), idx, T, p);
     345          21 :   setlg(K, N);
     346       31353 :   for (i=1; i<N; i++)
     347             :   {
     348       31332 :     GEN k = gel(K,i);
     349       31332 :     pari_sp av = avma;
     350       34473 :     long t = signe(k) && Flx_equal(Flxq_pow(g, k, T, p),
     351        3141 :                                    Flxq_pow(cindex_Flx(i,r,p,T[1]), idx, T, p));
     352       31332 :     avma = av;
     353       31332 :     if (!t)
     354       28191 :       gel(K,i) = cgetineg(lm);
     355             :     else
     356        3141 :       f++;
     357             :   }
     358          21 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
     359          21 :   if (f < maxss(3,maxss(p/2,nbi/p))) return NULL; /* Not enough logs found */
     360          21 :   return gerepilecopy(av, K);
     361             : }
     362             : 
     363             : static GEN
     364          28 : Flxq_log_rec(GEN W, GEN a, long r, GEN T, ulong p, GEN m)
     365             : {
     366          28 :   long AV = 0, u = 1;
     367          28 :   GEN g = a, b;
     368             :   pari_timer ti;
     369         308 :   while (!equali1(gel(W,u)))
     370         252 :    u++;
     371          28 :   b = cindex_Flx(u, r, p, T[1]);
     372             :   while(1)
     373             :   {
     374             :     long i, l;
     375             :     GEN V, F, E, Ao;
     376          43 :     timer_start(&ti);
     377          43 :     V = Flxq_log_find_rel(b, r, T, p, &g, &AV);
     378          43 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r);
     379          43 :     F = gel(V,1); E = gel(V,2);
     380          43 :     l = lg(F);
     381          43 :     Ao = gen_0;
     382         317 :     for(i=1; i<l; i++)
     383             :     {
     384         289 :       GEN R = gel(W,F[i]);
     385         289 :       if (signe(R)<=0)
     386          15 :         break;
     387         274 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
     388             :     }
     389          71 :     if (i==l) return subis(Ao,AV);
     390          15 :   }
     391             : }
     392             : 
     393             : static int
     394         126 : Flxq_log_use_index_cubic(GEN m, GEN T0, ulong p)
     395             : {
     396         126 :   pari_sp av = avma;
     397         126 :   long n = get_Flx_degree(T0), r, nb;
     398         126 :   GEN cost = smooth_best(p, n, &r, &nb);
     399         126 :   GEN cost_rho = sqrti(shifti(m,2));
     400         126 :   int use = (cost && gcmp(cost,cost_rho)<0);
     401         126 :   avma = av;
     402         126 :   return use;
     403             : }
     404             : 
     405             : static GEN
     406          14 : Flxq_log_index_cubic(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
     407             : {
     408          14 :   long n = get_Flx_degree(T0), r, nb;
     409          14 :   pari_sp av = avma;
     410             :   struct Flxq_log_rel rel;
     411             :   long nbi;
     412             :   GEN W, M, S, T, a, b, Ao, Bo, e, C, R;
     413             :   pari_timer ti;
     414          14 :   GEN cost = smooth_best(p, n, &r, &nb);
     415          14 :   GEN cost_rho = sqrti(shifti(m,2));
     416          14 :   if (!cost || gcmp(cost,cost_rho)>=0) { avma = av; return NULL; }
     417          14 :   nbi = itos(ffsumnbirred(stoi(p), r));
     418          14 :   if (DEBUGLEVEL)
     419             :   {
     420           0 :     err_printf("Size FB=%ld, looking for %ld relations, %Ps tests needed\n", nbi, nb,cost);
     421           0 :     timer_start(&ti);
     422             :   }
     423          14 :   T = smallirred_Flx(p,n,get_Flx_var(T0));
     424             :   for(;;)
     425             :   {
     426          14 :     S = Flx_ffisom(T0,T,p);
     427          14 :     a = Flx_Flxq_eval(a0, S, T, p);
     428          14 :     b = Flx_Flxq_eval(b0, S, T, p);
     429          14 :     C = Flx_shift(pol1_Flx(get_Flx_var(T)), (n+2)/3);
     430          14 :     R = Flxq_powu(C,3,T,p);
     431          14 :     if (DEBUGLEVEL)
     432           0 :       timer_printf(&ti," model change: %Ps",Flx_to_ZX(T));
     433          14 :     rel.nbmax=2*nb;
     434          14 :     M = cgetg(rel.nbmax+1, t_VEC);
     435          14 :     rel.rel = M;
     436          14 :     rel.nbrel = 0; rel.r = r; rel.off = 3*upowuu(p,r);
     437          14 :     rel.nb = nbi; rel.nbexp = nb; rel.nbtest=0;
     438          14 :     Flxq_log_cubic(&rel, C, R, p);
     439          14 :     setlg(M,1+rel.nbrel);
     440          14 :     if (DEBUGLEVEL)
     441             :     {
     442           0 :       err_printf("\n");
     443           0 :       timer_printf(&ti," %ld relations, %ld generators (%ld tests)",rel.nbrel,rel.nb,rel.nbtest);
     444             :     }
     445          14 :     W = check_kernel(r, M, nbi, rel.off + rel.nb - nbi, T, p, m);
     446          14 :     if (W) break;
     447           0 :     if (DEBUGLEVEL) timer_start(&ti);
     448           0 :     smallirred_Flx_next(T,p);
     449           0 :   }
     450          14 :   if (DEBUGLEVEL) timer_start(&ti);
     451          14 :   Ao = Flxq_log_rec(W, a, r, T, p, m);
     452          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
     453          14 :   Bo = Flxq_log_rec(W, b, r, T, p, m);
     454          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
     455          14 :   e = Fp_div(Ao, Bo, m);
     456          14 :   if (!Flx_equal(Flxq_pow(b0, e, T0, p), a0)) pari_err_BUG("Flxq_log");
     457          14 :   return gerepileupto(av, e);
     458             : }
     459             : 
     460        7333 : INLINE GEN Flx_frob(GEN u, ulong p) { return Flx_inflate(u, p); }
     461             : 
     462             : static GEN
     463        8676 : rel_Coppersmith(long r, GEN u, GEN v, long h, GEN R, long d, ulong p)
     464             : {
     465             :   GEN a, b, F, G, M;
     466        8676 :   if (degpol(Flx_gcd(u,v,p))) return NULL;
     467        8677 :   a = Flx_add(Flx_shift(u, h), v, p);
     468        8678 :   if (lgpol(a)==0 || !Flx_is_smooth(a, r, p)) return NULL;
     469        3435 :   b = Flx_add(Flx_mul(R, Flx_frob(u, p), p), Flx_shift(Flx_frob(v, p),d), p);
     470        3436 :   if (!Flx_is_smooth(b, r, p)) return NULL;
     471         747 :   F = factorel(a, p); G = factorel(b, p);
     472        1494 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2*p)),
     473        1494 :              vecsmall_concat(zv_z_mul(gel(F, 2),p), vecsmall_append(zv_neg(gel(G, 2)),d)));
     474         747 :   return famatsmall_reduce(M);
     475             : }
     476             : 
     477             : static GEN
     478         747 : vec_append_grow(GEN z, long i, GEN x)
     479             : {
     480         747 :   long n = lg(z)-1;
     481         747 :   if (i > n)
     482             :   {
     483           0 :     n <<= 1;
     484           0 :     z = vec_lengthen(z,n);
     485             :   }
     486         747 :   gel(z,i) = x;
     487         747 :   return z;
     488             : }
     489             : 
     490             : GEN
     491         497 : Flxq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
     492             : {
     493         497 :   long r = V[1], h = V[2], d = V[3], p = V[4], dT = V[5];
     494         497 :   pari_sp ltop = avma;
     495         497 :   GEN v = zero_zv(dT+2);
     496         503 :   GEN L = cgetg(17, t_VEC);
     497         503 :   pari_sp av = avma;
     498             :   long j;
     499         503 :   long nbtest=0, rel = 1;
     500         503 :   ulong lu = Flx_lead(u), lv;
     501       18551 :   for (j=1; j<=i; j++)
     502             :   {
     503             :     GEN z;
     504       18047 :     Flx_cnext(v, p);
     505       18048 :     Flx_renormalize_inplace(v, dT+2);
     506       18054 :     lv = Flx_lead(v);
     507       18050 :     avma = av;
     508       18050 :     if (lu != 1 && lv != 1) continue;
     509       10782 :     if (degpol(Flx_gcd(u, v, p))!=0) continue;
     510        7229 :     if (lu==1)
     511             :     {
     512        4415 :       z = rel_Coppersmith(r, u, v, h, R, d, p);
     513        4417 :       nbtest++;
     514        4417 :       if (z) { L = vec_append_grow(L, rel++, z); av = avma; }
     515             :     }
     516        7231 :     if (i==j) continue;
     517        7191 :     if (lv==1)
     518             :     {
     519        4263 :       z = rel_Coppersmith(r, v, u, h, R, d, p);
     520        4264 :       nbtest++;
     521        4264 :       if (z) { L = vec_append_grow(L, rel++, z); av = avma; }
     522             :     }
     523             :   }
     524         504 :   setlg(L,rel);
     525         504 :   return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
     526             : }
     527             : 
     528             : static GEN
     529           7 : Flxq_log_Coppersmith(long nbrel, long r, GEN T, ulong p)
     530             : {
     531             :   pari_sp av;
     532           7 :   long dT = degpol(T);
     533           7 :   long h = dT/p, d = dT-(h*p);
     534           7 :   GEN R = Flx_sub(Flx_shift(pol1_Flx(T[1]), dT), T, p);
     535           7 :   GEN u = zero_zv(dT+2);
     536             :   GEN done;
     537           7 :   long nbtest = 0, rel = 0;
     538           7 :   GEN M = cgetg(nbrel+1, t_VEC);
     539           7 :   long i = 1;
     540           7 :   GEN worker = snm_closure(is_entry("_Flxq_log_Coppersmith_worker"),
     541             :                mkvec2(mkvecsmall5(r,h,d,p,dT), R));
     542             :   struct pari_mt pt;
     543           7 :   long running, pending = 0, stop=0;
     544           7 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",degpol(R));
     545           7 :   mt_queue_start(&pt, worker);
     546           7 :   av = avma;
     547         533 :   while ((running = !stop) || pending)
     548             :   {
     549             :     GEN L;
     550             :     long l, j;
     551         519 :     Flx_cnext(u, p);
     552         519 :     Flx_renormalize_inplace(u, dT+2);
     553         519 :     mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
     554         519 :     done = mt_queue_get(&pt, NULL, &pending);
     555         519 :     if (!done) continue;
     556         504 :     L = gel(done, 2); nbtest += itos(gel(done,1));
     557         504 :     l = lg(L);
     558         504 :     if (l > 1)
     559             :     {
     560        1017 :       for (j=1; j<l; j++)
     561             :       {
     562         724 :         if (rel>nbrel) break;
     563         707 :         gel(M,++rel) = gel(L,j);
     564         707 :         if (DEBUGLEVEL && (rel&511UL)==0)
     565           0 :           err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
     566             :       }
     567         310 :       av = avma;
     568             :     }
     569         194 :     else avma = av;
     570         504 :     if (rel>nbrel) stop = 1;
     571         504 :     i++;
     572             :   }
     573           7 :   mt_queue_end(&pt);
     574           7 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
     575           7 :   return M;
     576             : }
     577             : 
     578             : static GEN Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, GEN mo);
     579             : 
     580             : static GEN
     581          19 : Flxq_log_from_rel(GEN W, GEN rel, long r, GEN T, ulong p, GEN m)
     582             : {
     583          19 :   pari_sp av = avma;
     584          19 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
     585          19 :   long i, l = lg(F);
     586         118 :   for(i=1; i<l; i++)
     587             :   {
     588          99 :     GEN R = gel(W, F[i]);
     589          99 :     if (signe(R)==0) /* Already failed */
     590           0 :       return NULL;
     591          99 :     else if (signe(R)<0) /* Not yet tested */
     592             :     {
     593           0 :       setsigne(gel(W,F[i]),0);
     594           0 :       R = Flxq_log_Coppersmith_d(W, cindex_Flx(F[i],r,p,T[1]), r, T, p, m);
     595           0 :       if (!R) return NULL;
     596             :     }
     597          99 :     o = Fp_add(o, mulis(R, E[i]), m);
     598             :   }
     599          19 :   return gerepileuptoint(av, o);
     600             : }
     601             : 
     602             : static GEN
     603          20 : Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, GEN mo)
     604             : {
     605          20 :   pari_sp av = avma, av2;
     606          20 :   long dg = degpol(g), k = r-1, m = maxss((dg-k)/2,0);
     607          20 :   long i, j, l = dg-m, N;
     608          20 :   GEN v = cgetg(k+m+1,t_MAT);
     609          20 :   long dT = degpol(T);
     610          20 :   long h = dT/p, d = dT-h*p;
     611          20 :   GEN R = Flx_rem(Flx_shift(pol1_Flx(T[1]), dT), T, p);
     612          20 :   GEN z = Flx_rem(Flx_shift(pol1_Flx(T[1]), h), g, p);
     613         120 :   for(i=1; i<=k+m; i++)
     614             :   {
     615         100 :     gel(v,i) = Flx_to_Flv(Flx_shift(z,-l),m);
     616         100 :     z = Flx_rem(Flx_shift(z,1),g,p);
     617             :   }
     618          20 :   v = Flm_ker(v,p);
     619         100 :   for(i=1; i<=k; i++)
     620          80 :     gel(v,i) = Flv_to_Flx(gel(v,i),T[1]);
     621          20 :   N = upowuu(p,k);
     622          20 :   av2 = avma;
     623         232 :   for (i=1; i<N; i++)
     624             :   {
     625             :     GEN p0,q,qh,a,b;
     626         231 :     ulong el = i;
     627         231 :     avma = av2;
     628         231 :     q = pol0_Flx(T[1]);
     629        1155 :     for (j=1; j<=k; j++)
     630             :     {
     631         924 :       ulong r = el % p;
     632         924 :       el /= p;
     633         924 :       if (r) q = Flx_add(q, Flx_Fl_mul(gel(v,j), r, p), p);
     634             :     }
     635         231 :     qh = Flx_shift(q, h);
     636         231 :     p0 = Flx_rem(qh, g, p);
     637         231 :     b = Flx_sub(Flx_mul(R, Flx_frob(q, p), p), Flx_shift(Flx_frob(p0, p), d), p);
     638         231 :     if (lgpol(b)==0 || !Flx_is_smooth(b, r, p)) continue;
     639          19 :     a = Flx_div(Flx_sub(qh, p0, p), g, p);
     640          19 :     if (degpol(Flx_gcd(a, q, p)) &&  degpol(Flx_gcd(a, p0 ,p)))
     641           0 :       continue;
     642          19 :     if (!(lgpol(a)==0 || !Flx_is_smooth(a, r, p)))
     643             :     {
     644          19 :       GEN F = factorel(b, p);
     645          19 :       GEN G = factorel(a, p);
     646          19 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2*p), gel(G, 1));
     647          38 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
     648          38 :           zv_z_mul(gel(G, 2),-p));
     649          19 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
     650          19 :       GEN l  = Flxq_log_from_rel(W, R, r, T, p, mo);
     651          19 :       if (!l) continue;
     652          19 :       l = Fp_div(l,utoi(p),mo);
     653          19 :       if (dg <= r)
     654             :       {
     655           0 :         long idx = Flx_cindex(g, p);
     656           0 :         affii(l, gel(W, idx));
     657           0 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", idx);
     658             :       }
     659          19 :       return gerepileuptoint(av, l);
     660             :     }
     661             :   }
     662           1 :   avma = av;
     663           1 :   return NULL;
     664             : }
     665             : 
     666             : static GEN
     667          14 : Flxq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, GEN T, ulong p, GEN m)
     668             : {
     669          14 :   GEN b = polx_Flx(T[1]);
     670          14 :   long AV = 0;
     671          14 :   GEN g = a, bad = pol0_Flx(T[1]);
     672             :   pari_timer ti;
     673             :   while(1)
     674             :   {
     675             :     long i, l;
     676             :     GEN V, F, E, Ao;
     677          17 :     timer_start(&ti);
     678          17 :     V = Flxq_log_find_rel(b, r2, T, p, &g, &AV);
     679          17 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
     680          17 :     F = gel(V,1); E = gel(V,2);
     681          17 :     l = lg(F);
     682          17 :     Ao = gen_0;
     683         118 :     for(i=1; i<l; i++)
     684             :     {
     685         104 :       GEN Fi = cindex_Flx(F[i], r2, p, T[1]);
     686             :       GEN R;
     687         104 :       if (degpol(Fi) <= r)
     688             :       {
     689          82 :         if (signe(gel(W,F[i]))==0)
     690           0 :           break;
     691          82 :         else if (signe(gel(W,F[i]))<0)
     692             :         {
     693           0 :           setsigne(gel(W,F[i]),0);
     694           0 :           R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,m);
     695             :         } else
     696          82 :           R = gel(W,F[i]);
     697             :       }
     698             :       else
     699             :       {
     700          22 :         if (Flx_equal(Fi,bad)) break;
     701          20 :         R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,m);
     702          20 :         if (!R) bad = Fi;
     703             :       }
     704         102 :       if (!R) break;
     705         101 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
     706             :     }
     707          31 :     if (i==l) return subis(Ao,AV);
     708           3 :   }
     709             : }
     710             : 
     711             : static GEN
     712           7 : Flxq_log_index_Coppersmith(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
     713             : {
     714           7 :   pari_sp av = avma;
     715           7 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
     716             :   pari_timer ti;
     717           7 :   double rf = p ==3 ? 1.2 : .9;
     718           7 :   long n = degpol(T0), r = (long) sqrt(n*rf);
     719             :   GEN T;
     720           7 :   long r2 = 3*r/2;
     721           7 :   long nbi = itos(ffsumnbirred(utoi(p), r)), nbrel=nbi*5/4;
     722           7 :   if (DEBUGLEVEL)
     723             :   {
     724           0 :     err_printf("Coppersmith: Parameters r=%ld r2=%ld\n", r,r2);
     725           0 :     err_printf("Coppersmith: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
     726           0 :     timer_start(&ti);
     727             :   }
     728           7 :   T = smallirred_Flx(p,n,get_Flx_var(T0));
     729           7 :   S = Flx_ffisom(T0,T,p);
     730           7 :   a = Flx_Flxq_eval(a0, S, T, p);
     731           7 :   b = Flx_Flxq_eval(b0, S, T, p);
     732           7 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
     733           7 :   M = Flxq_log_Coppersmith(nbrel, r, T, p);
     734           7 :   if (DEBUGLEVEL) timer_printf(&ti,"relations");
     735           7 :   W = check_kernel(r, M, nbi, 3*upowuu(p,r), T, p, m);
     736           7 :   timer_start(&ti);
     737           7 :   Ao = Flxq_log_Coppersmith_rec(W, r2, a, r, T, p, m);
     738           7 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
     739           7 :   Bo = Flxq_log_Coppersmith_rec(W, r2, b, r, T, p, m);
     740           7 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
     741           7 :   e = Fp_div(Ao, Bo, m);
     742           7 :   if (!Flx_equal(Flxq_pow(b0,e,T0,p),a0)) pari_err_BUG("Flxq_log");
     743           7 :   return gerepileupto(av, e);
     744             : }
     745             : 
     746             : GEN
     747          21 : Flxq_log_index(GEN a, GEN b, GEN m, GEN T, ulong p)
     748             : {
     749          21 :   long d = get_Flx_degree(T);
     750          21 :   if (p==3 || (p==5 && d>41))
     751           7 :     return Flxq_log_index_Coppersmith(a, b, m, T, p);
     752          14 :   else    return Flxq_log_index_cubic(a, b, m, T, p);
     753             : }
     754             : 
     755             : int
     756       31009 : Flxq_log_use_index(GEN m, GEN T, ulong p)
     757             : {
     758       31009 :   long d = get_Flx_degree(T);
     759       31009 :   if (p==3 || (p==5 && d>41))
     760        7399 :     return 1;
     761       23610 :   else if (d<=4 || d==6)
     762       23484 :     return 0;
     763             :   else
     764         126 :     return Flxq_log_use_index_cubic(m, T, p);
     765             : }

Generated by: LCOV version 1.11