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 to exceed 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.18.0 lcov report (development 29815-a300ec5c34) Lines: 448 468 95.7 %
Date: 2024-12-25 09:08:54 Functions: 28 28 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; either version 2 of the License, or (at your option) any later
       8             : version. It is distributed in the hope that it will be useful, but WITHOUT
       9             : ANY WARRANTY WHATSOEVER.
      10             : 
      11             : Check the License for details. You should have received a copy of it, along
      12             : with the package; see the file 'COPYING'. If not, write to the Free Software
      13             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      14             : 
      15             : #include "pari.h"
      16             : #include "paripriv.h"
      17             : 
      18             : #define DEBUGLEVEL DEBUGLEVEL_fflog
      19             : 
      20             : /* Let [ be the following order on Fp: 0 [ p-1 [ 1 [ p-2 [ 2 .. [ p\2
      21             : and [[ the lexicographic extension of [ to Fp[T]. Compute the
      22             : isomorphism (Fp[X], [[) -> (N,<) on P */
      23             : 
      24             : static long
      25      391128 : Flx_cindex(GEN P, ulong p)
      26             : {
      27      391128 :   long d = degpol(P), i;
      28      391128 :   ulong s = 0, p2 = (p-1)>>1;
      29     1776951 :   for (i = 0; i <= d; ++i)
      30             :   {
      31     1385823 :     ulong x = P[d-i+2];
      32     1385823 :     if (x<=p2) x = 2*x; else x = 1+2*(p-1-x);
      33     1385823 :     s = p*s+x;
      34             :   }
      35      391128 :   return s;
      36             : }
      37             : 
      38             : /* Compute the polynomial immediately after t for the [[ order */
      39             : 
      40             : static void
      41      423709 : Flx_cnext(GEN t, ulong p)
      42             : {
      43             :   long i;
      44      423709 :   long p2 = p>>1;
      45      540244 :   for(i=2;;i++)
      46      540244 :     if (t[i]==p2)
      47      116535 :       t[i]=0;
      48             :     else
      49             :     {
      50      423709 :       t[i] = t[i]<p2 ? p-1-t[i]: p-t[i];
      51      423709 :       break;
      52             :     }
      53      423709 : }
      54             : 
      55             : static int
      56          28 : has_deg1_auto(GEN T, ulong p, ulong pi)
      57             : {
      58          28 :   long i, n = degpol(T);
      59          28 :   GEN a = polx_Flx(get_Flx_var(T));
      60         672 :   for (i=1; i<n; i++)
      61             :   {
      62         644 :     a = Flxq_powu_pre(a, p, T, p, pi);
      63         644 :     if (degpol(a)==1) return 1;
      64             :   }
      65          28 :   return 0;
      66             : }
      67             : 
      68             : static void
      69        1057 : smallirred_Flx_next(GEN a, long p, ulong pi)
      70             : {
      71             :   do
      72             :   {
      73             :     long i;
      74        1449 :     for(i=2;;i++)
      75        1449 :       if (++a[i]==p) a[i]=0;
      76        1057 :       else break;
      77        1057 :   } while (!Flx_is_irred(a, p) || has_deg1_auto(a,p,pi) );
      78          28 : }
      79             : 
      80             : /* Avoid automorphisms of degree 1 */
      81             : static GEN
      82          28 : smallirred_Flx(long p, ulong n, long sv, ulong pi)
      83             : {
      84          28 :   GEN a = zero_zv(n+2);
      85          28 :   a[1] = sv; a[3] = 1; a[n+2] = 1;
      86          28 :   smallirred_Flx_next(a, p, pi);
      87          28 :   return a;
      88             : }
      89             : 
      90             : struct Flxq_log_rel
      91             : {
      92             :   long nbrel;
      93             :   GEN rel;
      94             :   long nb;
      95             :   long r, off, nbmax, nbexp;
      96             :   ulong nbtest;
      97             : };
      98             : 
      99             : static GEN
     100        4657 : cindex_Flx(long c, long d, ulong p, long v)
     101             : {
     102        4657 :   GEN P = cgetg(d+3, t_VECSMALL);
     103             :   long i;
     104        4657 :   P[1] = v;
     105       31838 :   for (i = 0; i <= d; ++i)
     106             :   {
     107       27181 :     ulong x = c%p;
     108       27181 :     P[i+2] = (x&1) ? p-1-(x>>1) : x>>1;
     109       27181 :     c/=p;
     110             :   }
     111        4657 :   return Flx_renormalize(P, d+3);
     112             : }
     113             : 
     114             : static GEN
     115       10947 : factorel(GEN h, ulong p)
     116             : {
     117       10947 :   GEN F = Flx_factor(h, p);
     118       10948 :   GEN F1 = gel(F, 1), F2 = gel(F, 2);
     119       10948 :   long i, l1 = lg(F1)-1;
     120       10948 :   GEN p2 = cgetg(l1+1, t_VECSMALL);
     121       10948 :   GEN e2 = cgetg(l1+1, t_VECSMALL);
     122       51727 :   for (i = 1; i <= l1; ++i)
     123             :   {
     124       40780 :     p2[i] = Flx_cindex(gel(F1, i), p);
     125       40778 :     e2[i] = F2[i];
     126             :   }
     127       10947 :   return mkmat2(p2, e2);
     128             : }
     129             : 
     130             : static long
     131       74256 : Flx_addifsmooth3(pari_sp *av, struct Flxq_log_rel *r, GEN h, long u, long v, long w, ulong p)
     132             : {
     133       74256 :   long off = r->off;
     134       74256 :   r->nbtest++;
     135       74256 :   if (Flx_is_smooth(h, r->r, p))
     136             :   {
     137        5670 :     GEN z = factorel(h, p);
     138        5670 :     if (v<0)
     139        1225 :       z = mkmat2(vecsmall_append(gel(z,1),off+u),vecsmall_append(gel(z,2),-1));
     140             :     else
     141       13335 :       z = famatsmall_reduce(mkmat2(
     142        4445 :             vecsmall_concat(gel(z,1),mkvecsmall3(off+u,off+v,off+w)),
     143        4445 :             vecsmall_concat(gel(z,2),mkvecsmall3(-1,-1,-1))));
     144        5670 :     gel(r->rel,++r->nbrel) = gerepilecopy(*av,z);
     145        5670 :     if (DEBUGLEVEL && (r->nbrel&511UL)==0)
     146           0 :       err_printf("%ld%% ",r->nbrel*100/r->nbexp);
     147        5670 :     *av = avma;
     148       68586 :   } else set_avma(*av);
     149       74256 :   return r->nbrel==r->nb || r->nbrel==r->nbmax;
     150             : }
     151             : 
     152             : static void
     153      423756 : Flx_renormalize_inplace(GEN x, long lx)
     154             : {
     155             :   long i;
     156     4695563 :   for (i = lx-1; i>1; i--)
     157     4692870 :     if (x[i]) break;
     158      423756 :   setlg(x, i+1);
     159      423872 : }
     160             : 
     161             : /* Let T*X^e=C^3-R
     162             :  *  a+b+c = 0
     163             :  * (C+a)*(C+b)*(C+c) = C^3+ (a*b+a*c+b*c)*C+a*b*c
     164             :  *  = R + (a*b+a*c+b*c)*C+a*b*c
     165             :  *  = R + (a*b-c^2)*C+a*b*c */
     166             : static void
     167          14 : Flxq_log_cubic(struct Flxq_log_rel *r, GEN C, GEN R, ulong p, ulong pi)
     168             : {
     169          14 :   long l = lg(C);
     170          14 :   GEN a = zero_zv(l); /*We allocate one extra word to catch overflow*/
     171          14 :   GEN b = zero_zv(l);
     172          14 :   pari_sp av = avma;
     173             :   long i,j,k;
     174        2800 :   for(i=0; ; i++, Flx_cnext(a, p))
     175             :   {
     176        2800 :     Flx_renormalize_inplace(a, l+1);
     177        2800 :     r->nb++;
     178        2800 :     if (Flx_addifsmooth3(&av, r, Flx_add(a, C, p), i, -1, -1, p)) return;
     179       29400 :     for(j=2; j<=l; j++) b[j] = 0;
     180      353129 :     for(j=0; j<=i; j++, Flx_cnext(b, p))
     181             :     {
     182             :       GEN h,c;
     183             :       GEN pab,pabc,pabc2;
     184      350343 :       Flx_renormalize_inplace(b, l+1);
     185      350343 :       c = Flx_neg(Flx_add(a,b,p),p);
     186      350343 :       k = Flx_cindex(c, p);
     187      350343 :       if (k > j) continue;
     188       71456 :       pab  = Flx_mul_pre(a, b, p, pi);
     189       71456 :       pabc = Flx_mul_pre(pab,c,p,pi);
     190       71456 :       pabc2= Flx_sub(pab,Flx_sqr_pre(c,p,pi),p);
     191       71456 :       h = Flx_add(R,Flx_add(Flx_mul_pre(C,pabc2,p,pi),pabc,p), p);
     192       71456 :       h = Flx_normalize(h, p);
     193       71456 :       if (Flx_addifsmooth3(&av, r, h, i, j, k, p)) return;
     194             :     }
     195             :   }
     196             : }
     197             : 
     198             : static GEN
     199          58 : Flxq_log_find_rel(GEN b, long r, GEN T, ulong p, ulong pi, GEN *g, long *e)
     200             : {
     201          58 :   pari_sp av = avma;
     202             :   while (1)
     203        2122 :   {
     204             :     GEN M, z;
     205        2180 :     *g = Flxq_mul_pre(*g, b, T, p, pi); (*e)++;
     206        2180 :     M = Flx_halfgcd_all_pre(*g,T,p,pi,&z,NULL);
     207        2180 :     if (Flx_is_smooth_pre(gcoeff(M,1,1), r, p, pi)
     208         429 :      && Flx_is_smooth_pre(z, r, p, pi))
     209             :     {
     210          58 :       GEN F = factorel(z, p);
     211          58 :       GEN G = factorel(gcoeff(M,1,1), p);
     212          58 :       GEN rel = mkmat2(vecsmall_concat(gel(F, 1),gel(G, 1)),
     213          58 :           vecsmall_concat(gel(F, 2),zv_neg(gel(G, 2))));
     214          58 :       return gc_all(av,2,&rel,g);
     215             :     }
     216        2122 :     if (gc_needed(av,2))
     217             :     {
     218           0 :       if (DEBUGMEM>1) pari_warn(warnmem,"Flxq_log_find_rel");
     219           0 :       *g = gerepilecopy(av, *g);
     220             :     }
     221             :   }
     222             : }
     223             : 
     224             : /* Generalised Odlyzko formulae ( EUROCRYPT '84, LNCS 209, pp. 224-314, 1985. ) */
     225             : /* Return the number of monic, k smooth, degree n polynomials for k=1..r */
     226             : static GEN
     227        2233 : smoothness_vec(ulong p, long r, long n)
     228             : {
     229             :   long i,j,k;
     230        2233 :   GEN R = cgetg(r+1, t_VEC), pp = utoipos(p);
     231        2233 :   GEN V = cgetg(n+1, t_VEC);
     232       20496 :   for (j = 1; j <= n; ++j)
     233       18263 :     gel(V, j) =  binomialuu(p+j-1,j);
     234        2233 :   gel(R, 1) = gel(V, n);
     235        5341 :   for (k = 2; k <= r; ++k)
     236             :   {
     237        3108 :     GEN W = cgetg(n+1, t_VEC);
     238        3108 :     GEN Ik = ffnbirred(pp, k);
     239       36029 :     for (j = 1; j <= n; ++j)
     240             :     {
     241       32921 :       long l = j/k;
     242       32921 :       GEN s = gen_0;
     243       32921 :       pari_sp av2 = avma;
     244       32921 :       if (l*k == j)
     245             :       {
     246       10801 :         s = binomial(addiu(Ik,l-1), l);
     247       10801 :         l--;
     248             :       }
     249      119847 :       for (i = 0; i <= l; ++i)
     250       86926 :         s = addii(s, mulii(gel(V, j-k*i), binomial(addis(Ik,i-1), i)));
     251       32921 :       gel(W, j) = gerepileuptoint(av2, s);
     252             :     }
     253        3108 :     V = W;
     254        3108 :     gel(R, k) = gel(V, n);
     255             :   }
     256        2233 :   return R;
     257             : }
     258             : 
     259             : /* Solve N^2*pr/6 + N*prC = N+fb
     260             :    N^2*pr/6 + N*(prC-1) -fb = 0
     261             :  */
     262             : 
     263             : static GEN
     264        1729 : smooth_cost(GEN fb, GEN pr, GEN prC)
     265             : {
     266        1729 :   GEN a = gdivgu(pr,6);
     267        1729 :   GEN b = gsubgs(prC,1);
     268        1729 :   GEN c = gneg(fb);
     269        1729 :   GEN vD = gsqrt(gsub(gsqr(b),gmul2n(gmul(a,c),2)),BIGDEFAULTPREC);
     270        1729 :   return ceil_safe(gdiv(gsub(vD,b),gmul2n(a,1)));
     271             : }
     272             : 
     273             : /* Return best choice of r.
     274             :    We loop over d until there is sufficiently many triples (a,b,c) (a+b+c=0)
     275             :    of degree <=d with respect to the probability of smoothness of (a*b-c^2)*C
     276             :  */
     277             : 
     278             : static GEN
     279         315 : smooth_best(long p, long n, long *pt_r, long *pt_nb)
     280             : {
     281         315 :   pari_sp av = avma, av2;
     282         315 :   GEN bestc = NULL, pp = utoipos(p);
     283         315 :   long bestr = 0, bestFB = 0;
     284         315 :   long r,d, dC = (n+2)/3;
     285         819 :   for (r = 1; r < dC; ++r)
     286             :   {
     287         504 :     GEN fb = ffsumnbirred(pp, r);
     288         504 :     GEN smoothC = smoothness_vec(p,r,dC);
     289         504 :     GEN prC = gdiv(gel(smoothC,r), powuu(p,dC));
     290         504 :     ulong rels = 0;
     291         504 :     av2 = avma;
     292        2023 :     for(d=0; d<dC && rels < ULONG_MAX; d++)
     293             :     {
     294             :       GEN c;
     295        1729 :       long dt = dC+2*d;
     296        1729 :       GEN smooth = smoothness_vec(p,r,dt);
     297        1729 :       GEN pr = gdiv(gel(smooth,r), powuu(p,dt));
     298        1729 :       GEN FB = addii(fb,powuu(p,d));
     299        1729 :       GEN N = smooth_cost(subiu(FB,rels),pr,prC);
     300        1729 :       GEN Nmax = powuu(p,d+1);
     301        1729 :       if (gcmp(N,Nmax) >= 0)
     302             :       {
     303        1519 :         rels = itou_or_0(addui(rels, gceil(gmul(gdivgu(sqri(Nmax),6),pr))));
     304        1519 :         if (!rels) rels = ULONG_MAX;
     305        1519 :         set_avma(av2);
     306        1519 :         continue;
     307             :       }
     308         210 :       c = gdivgu(addii(powuu(p,2*d),sqri(N)),6);
     309         210 :       FB = addii(FB,N);
     310         210 :       if ((!bestc || gcmp(gmul2n(c,r), gmul2n(bestc,bestr)) < 0))
     311             :       {
     312         133 :         if (DEBUGLEVEL)
     313           0 :           err_printf("r=%ld d=%ld fb=%Ps early rels=%lu P=%.5Pe -> C=%.5Pe \n",
     314             :                       r, dt, FB, rels, pr, c);
     315         133 :         bestc = c;
     316         133 :         bestr = r;
     317         133 :         bestFB = itos_or_0(FB);
     318             :       }
     319         210 :       break;
     320             :     }
     321             :   }
     322         315 :   *pt_r=bestr;
     323         315 :   *pt_nb=bestFB;
     324         315 :   return bestc ? gerepileupto(av, gceil(bestc)): NULL;
     325             : }
     326             : 
     327             : static GEN
     328          28 : check_kernel(long r, GEN M, long nbi, long nbrow, GEN T, ulong p, ulong pi, GEN m)
     329             : {
     330          28 :   pari_sp av = avma;
     331          28 :   long N = 3*upowuu(p, r);
     332          28 :   GEN K = FpMs_leftkernel_elt(M, nbrow, m);
     333          28 :   long i, f=0, tbs;
     334          28 :   long lm = lgefint(m), u=1;
     335             :   GEN tab, g;
     336          28 :   GEN q = powuu(p,degpol(T));
     337          28 :   GEN idx = diviiexact(subiu(q,1),m);
     338             :   pari_timer ti;
     339          28 :   if (DEBUGLEVEL) timer_start(&ti);
     340         224 :   while (signe(gel(K,u))==0)
     341         196 :     u++;
     342          28 :   K = FpC_Fp_mul(K, Fp_inv(gel(K, u), m), m);
     343          28 :   g = Flxq_pow_pre(cindex_Flx(u, r, p, T[1]), idx, T, p, pi);
     344          28 :   tbs = maxss(1, expu(nbi/expi(m)));
     345          28 :   tab = Flxq_pow_init_pre(g, q, tbs, T, p, pi);
     346          28 :   setlg(K, N);
     347       46662 :   for (i=1; i<N; i++)
     348             :   {
     349       46634 :     GEN k = gel(K,i);
     350       46634 :     pari_sp av = avma;
     351       51027 :     long t = signe(k) && Flx_equal(Flxq_pow_table_pre(tab, k, T, p, pi),
     352        4393 :                                    Flxq_pow_pre(cindex_Flx(i,r,p,T[1]), idx, T, p, pi));
     353       46634 :     set_avma(av);
     354       46634 :     if (!t)
     355       42241 :       gel(K,i) = cgetineg(lm);
     356             :     else
     357        4393 :       f++;
     358             :   }
     359          28 :   if (DEBUGLEVEL) timer_printf(&ti,"found %ld/%ld logs", f, nbi);
     360          28 :   if (f < maxss(3,maxss(p/2,nbi/p))) return NULL; /* Not enough logs found */
     361          28 :   return gerepilecopy(av, K);
     362             : }
     363             : 
     364             : static GEN
     365          28 : Flxq_log_rec(GEN W, GEN a, long r, GEN T, ulong p, ulong pi, 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           1 :   {
     375             :     long i, l;
     376             :     GEN V, F, E, Ao;
     377          29 :     timer_start(&ti);
     378          29 :     V = Flxq_log_find_rel(b, r, T, p, pi, &g, &AV);
     379          29 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r);
     380          29 :     F = gel(V,1); E = gel(V,2);
     381          29 :     l = lg(F);
     382          29 :     Ao = gen_0;
     383         216 :     for(i=1; i<l; i++)
     384             :     {
     385         188 :       GEN R = gel(W,F[i]);
     386         188 :       if (signe(R)<=0)
     387           1 :         break;
     388         187 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
     389             :     }
     390          29 :     if (i==l) return subis(Ao,AV);
     391             :   }
     392             : }
     393             : 
     394             : static int
     395         301 : Flxq_log_use_index_cubic(GEN m, GEN T0, ulong p)
     396             : {
     397         301 :   pari_sp av = avma;
     398         301 :   long n = get_Flx_degree(T0), r, nb;
     399         301 :   GEN cost = smooth_best(p, n, &r, &nb);
     400         301 :   GEN cost_rho = sqrti(shifti(m,2));
     401         301 :   int use = (cost && gcmp(cost,cost_rho)<0);
     402         301 :   set_avma(av);
     403         301 :   return use;
     404             : }
     405             : 
     406             : static GEN
     407          14 : Flxq_log_index_cubic(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
     408             : {
     409          14 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
     410          14 :   long n = get_Flx_degree(T0), r, nb;
     411          14 :   pari_sp av = avma;
     412             :   struct Flxq_log_rel rel;
     413             :   long nbi;
     414             :   GEN W, M, S, T, a, b, Ao, Bo, e, C, R;
     415             :   pari_timer ti;
     416          14 :   GEN cost = smooth_best(p, n, &r, &nb);
     417          14 :   GEN cost_rho = sqrti(shifti(m,2));
     418          14 :   if (!cost || gcmp(cost,cost_rho)>=0) return gc_NULL(av);
     419          14 :   nbi = itos(ffsumnbirred(stoi(p), r));
     420          14 :   if (DEBUGLEVEL)
     421             :   {
     422           0 :     err_printf("Size FB=%ld, looking for %ld relations, %Ps tests needed\n", nbi, nb,cost);
     423           0 :     timer_start(&ti);
     424             :   }
     425          14 :   T = smallirred_Flx(p,n,get_Flx_var(T0), pi);
     426             :   for(;;)
     427             :   {
     428          14 :     S = Flx_ffisom(T0,T,p);
     429          14 :     a = Flx_Flxq_eval_pre(a0, S, T, p, pi);
     430          14 :     b = Flx_Flxq_eval_pre(b0, S, T, p, pi);
     431          14 :     C = Flx_shift(pol1_Flx(get_Flx_var(T)), (n+2)/3);
     432          14 :     R = Flxq_powu_pre(C,3,T,p,pi);
     433          14 :     if (DEBUGLEVEL)
     434           0 :       timer_printf(&ti," model change: %Ps",Flx_to_ZX(T));
     435          14 :     rel.nbmax=2*nb;
     436          14 :     M = cgetg(rel.nbmax+1, t_VEC);
     437          14 :     rel.rel = M;
     438          14 :     rel.nbrel = 0; rel.r = r; rel.off = 3*upowuu(p,r);
     439          14 :     rel.nb = nbi; rel.nbexp = nb; rel.nbtest=0;
     440          14 :     Flxq_log_cubic(&rel, C, R, p, pi);
     441          14 :     setlg(M,1+rel.nbrel);
     442          14 :     if (DEBUGLEVEL)
     443             :     {
     444           0 :       err_printf("\n");
     445           0 :       timer_printf(&ti," %ld relations, %ld generators (%ld tests)",rel.nbrel,rel.nb,rel.nbtest);
     446             :     }
     447          14 :     W = check_kernel(r, M, nbi, rel.off + rel.nb - nbi, T, p, pi, m);
     448          14 :     if (W) break;
     449           0 :     if (DEBUGLEVEL) timer_start(&ti);
     450           0 :     smallirred_Flx_next(T,p, pi);
     451             :   }
     452          14 :   if (DEBUGLEVEL) timer_start(&ti);
     453          14 :   Ao = Flxq_log_rec(W, a, r, T, p, pi, m);
     454          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
     455          14 :   Bo = Flxq_log_rec(W, b, r, T, p, pi, m);
     456          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
     457          14 :   e = Fp_div(Ao, Bo, m);
     458          14 :   if (!Flx_equal(Flxq_pow_pre(b0, e, T0, p, pi), a0)) pari_err_BUG("Flxq_log");
     459          14 :   return gerepileupto(av, e);
     460             : }
     461             : 
     462       19305 : INLINE GEN Flx_frob(GEN u, ulong p) { return Flx_inflate(u, p); }
     463             : 
     464             : static GEN
     465       32248 : rel_Coppersmith(long r, GEN u, GEN v, long h, GEN R, long d, ulong p, ulong pi)
     466             : {
     467             :   GEN a, b, F, G, M;
     468       32248 :   if (degpol(Flx_gcd_pre(u,v,p,pi))) return NULL;
     469       32197 :   a = Flx_add(Flx_shift(u, h), v, p);
     470       32281 :   if (lgpol(a)==0 || !Flx_is_smooth_pre(a, r, p, pi)) return NULL;
     471        8380 :   b = Flx_add(Flx_mul_pre(R, Flx_frob(u, p), p, pi),
     472             :               Flx_shift(Flx_frob(v, p),d), p);
     473        8411 :   if (!Flx_is_smooth_pre(b, r, p, pi)) return NULL;
     474        2524 :   F = factorel(a, p); G = factorel(b, p);
     475        5048 :   M = mkmat2(vecsmall_concat(gel(F, 1), vecsmall_append(gel(G, 1), 2*p)),
     476        5048 :              vecsmall_concat(zv_z_mul(gel(F, 2),p), vecsmall_append(zv_neg(gel(G, 2)),d)));
     477        2524 :   return famatsmall_reduce(M);
     478             : }
     479             : 
     480             : GEN
     481        1355 : Flxq_log_Coppersmith_worker(GEN u, long i, GEN V, GEN R)
     482             : {
     483        1355 :   long r = V[1], h = V[2], d = V[3], p = V[4], pi = V[5], dT = V[6];
     484        1355 :   pari_sp ltop = avma;
     485        1355 :   GEN v = zero_zv(dT+2);
     486        1356 :   GEN L = cgetg(2*i+1, t_VEC);
     487        1355 :   pari_sp av = avma;
     488             :   long j;
     489        1355 :   long nbtest=0, rel = 1;
     490        1355 :   ulong lu = Flx_lead(u), lv;
     491       70560 :   for (j=1; j<=i; j++)
     492             :   {
     493             :     GEN z;
     494       69205 :     Flx_cnext(v, p);
     495       69220 :     Flx_renormalize_inplace(v, dT+2);
     496       69339 :     lv = Flx_lead(v);
     497       69330 :     set_avma(av);
     498       69324 :     if (lu != 1 && lv != 1) continue;
     499       39904 :     if (degpol(Flx_gcd_pre(u, v, p, pi))!=0) continue;
     500       26879 :     if (lu==1)
     501             :     {
     502       14841 :       z = rel_Coppersmith(r, u, v, h, R, d, p, pi);
     503       14857 :       nbtest++;
     504       14857 :       if (z) { gel(L, rel++) = z; av = avma; }
     505             :     }
     506       26895 :     if (i==j) continue;
     507       26810 :     if (lv==1)
     508             :     {
     509       17399 :       z = rel_Coppersmith(r, v, u, h, R, d, p, pi);
     510       17442 :       nbtest++;
     511       17442 :       if (z) { gel(L, rel++) = z; av = avma; }
     512             :     }
     513             :   }
     514        1355 :   setlg(L,rel);
     515        1355 :   return gerepilecopy(ltop, mkvec2(stoi(nbtest), L));
     516             : }
     517             : 
     518             : static GEN
     519          14 : Flxq_log_Coppersmith(long nbrel, long r, GEN T, ulong p, ulong pi)
     520             : {
     521             :   pari_sp av;
     522          14 :   long dT = degpol(T);
     523          14 :   long h = dT/p, d = dT-(h*p);
     524          14 :   GEN R = Flx_sub(Flx_shift(pol1_Flx(T[1]), dT), T, p);
     525          14 :   GEN u = zero_zv(dT+2);
     526             :   GEN done;
     527          14 :   long nbtest = 0, rel = 0;
     528          14 :   GEN M = cgetg(nbrel+1, t_VEC);
     529          14 :   long i = 1;
     530          14 :   GEN worker = snm_closure(is_entry("_Flxq_log_Coppersmith_worker"),
     531             :                mkvec2(mkvecsmalln(6, r,h,d,p,pi,dT), R));
     532             :   struct pari_mt pt;
     533          14 :   long running, pending = 0, stop=0;
     534          14 :   if (DEBUGLEVEL) err_printf("Coppersmith (R = %ld): ",degpol(R));
     535          14 :   mt_queue_start(&pt, worker);
     536          14 :   av = avma;
     537        1400 :   while ((running = !stop) || pending)
     538             :   {
     539             :     GEN L;
     540             :     long l, j;
     541        1386 :     Flx_cnext(u, p);
     542        1386 :     Flx_renormalize_inplace(u, dT+2);
     543        1386 :     mt_queue_submit(&pt, 0, running ? mkvec2(u, stoi(i)): NULL);
     544        1386 :     done = mt_queue_get(&pt, NULL, &pending);
     545        1386 :     if (!done) continue;
     546        1356 :     L = gel(done, 2); nbtest += itos(gel(done,1));
     547        1356 :     l = lg(L);
     548        1356 :     if (l > 1)
     549             :     {
     550        3392 :       for (j=1; j<l; j++)
     551             :       {
     552        2465 :         if (rel>nbrel) break;
     553        2429 :         gel(M,++rel) = gel(L,j);
     554        2429 :         if (DEBUGLEVEL && (rel&511UL)==0)
     555           0 :           err_printf("%ld%%[%ld] ",rel*100/nbrel,i);
     556             :       }
     557         963 :       av = avma;
     558             :     }
     559         393 :     else set_avma(av);
     560        1356 :     if (rel>nbrel) stop = 1;
     561        1356 :     i++;
     562             :   }
     563          14 :   mt_queue_end(&pt);
     564          14 :   if (DEBUGLEVEL) err_printf(": %ld tests\n", nbtest);
     565          14 :   return M;
     566             : }
     567             : 
     568             : static GEN Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, ulong pi, GEN mo);
     569             : 
     570             : static GEN
     571          57 : Flxq_log_from_rel(GEN W, GEN rel, long r, GEN T, ulong p, ulong pi, GEN m)
     572             : {
     573          57 :   pari_sp av = avma;
     574          57 :   GEN F = gel(rel,1), E = gel(rel,2), o = gen_0;
     575          57 :   long i, l = lg(F);
     576         380 :   for(i=1; i<l; i++)
     577             :   {
     578         323 :     GEN R = gel(W, F[i]);
     579         323 :     if (signe(R)==0) /* Already failed */
     580           0 :       return NULL;
     581         323 :     else if (signe(R)<0) /* Not yet tested */
     582             :     {
     583           7 :       setsigne(gel(W,F[i]),0);
     584           7 :       R = Flxq_log_Coppersmith_d(W, cindex_Flx(F[i],r,p,T[1]), r, T, p, pi, m);
     585           7 :       if (!R) return NULL;
     586             :     }
     587         323 :     o = Fp_add(o, mulis(R, E[i]), m);
     588             :   }
     589          57 :   return gerepileuptoint(av, o);
     590             : }
     591             : 
     592             : static GEN
     593          58 : Flxq_log_Coppersmith_d(GEN W, GEN g, long r, GEN T, ulong p, ulong pi, GEN mo)
     594             : {
     595          58 :   pari_sp av = avma, av2;
     596          58 :   long dg = degpol(g), k = r-1, m = maxss((dg-k)/2,0);
     597          58 :   long i, j, l = dg-m, N;
     598          58 :   GEN v = cgetg(k+m+1,t_MAT);
     599          58 :   long dT = degpol(T);
     600          58 :   long h = dT/p, d = dT-h*p;
     601          58 :   GEN R = Flx_rem_pre(Flx_shift(pol1_Flx(T[1]), dT), T, p, pi);
     602          58 :   GEN z = Flx_rem_pre(Flx_shift(pol1_Flx(T[1]), h), g, p, pi);
     603         386 :   for(i=1; i<=k+m; i++)
     604             :   {
     605         328 :     gel(v,i) = Flx_to_Flv(Flx_shift(z,-l),m);
     606         328 :     z = Flx_rem_pre(Flx_shift(z,1),g,p,pi);
     607             :   }
     608          58 :   v = Flm_ker(v,p);
     609         328 :   for(i=1; i<=k; i++)
     610         270 :     gel(v,i) = Flv_to_Flx(gel(v,i),T[1]);
     611          58 :   N = upowuu(p,k);
     612          58 :   av2 = avma;
     613        1251 :   for (i=1; i<N; i++)
     614             :   {
     615             :     GEN p0,q,qh,a,b;
     616        1250 :     ulong el = i;
     617        1250 :     set_avma(av2);
     618        1250 :     q = pol0_Flx(T[1]);
     619        7256 :     for (j=1; j<=k; j++)
     620             :     {
     621        6006 :       ulong r = el % p;
     622        6006 :       el /= p;
     623        6006 :       if (r) q = Flx_add(q, Flx_Fl_mul(gel(v,j), r, p), p);
     624             :     }
     625        1250 :     qh = Flx_shift(q, h);
     626        1250 :     p0 = Flx_rem_pre(qh, g, p, pi);
     627        1250 :     b = Flx_sub(Flx_mul_pre(R, Flx_frob(q, p), p, pi),
     628             :                 Flx_shift(Flx_frob(p0, p), d), p);
     629        1250 :     if (lgpol(b)==0 || !Flx_is_smooth_pre(b, r, p, pi)) continue;
     630          64 :     a = Flx_div_pre(Flx_sub(qh, p0, p), g, p, pi);
     631          64 :     if (degpol(Flx_gcd_pre(a, q, p, pi)) && degpol(Flx_gcd_pre(a, p0, p, pi)))
     632           0 :       continue;
     633          64 :     if (!(lgpol(a)==0 || !Flx_is_smooth_pre(a, r, p, pi)))
     634             :     {
     635          57 :       GEN F = factorel(b, p);
     636          57 :       GEN G = factorel(a, p);
     637          57 :       GEN FG = vecsmall_concat(vecsmall_append(gel(F, 1), 2*p), gel(G, 1));
     638          57 :       GEN E  = vecsmall_concat(vecsmall_append(gel(F, 2), -d),
     639          57 :           zv_z_mul(gel(G, 2),-p));
     640          57 :       GEN R  = famatsmall_reduce(mkmat2(FG, E));
     641          57 :       GEN l  = Flxq_log_from_rel(W, R, r, T, p, pi, mo);
     642          57 :       if (!l) continue;
     643          57 :       l = Fp_divu(l,p,mo);
     644          57 :       if (dg <= r)
     645             :       {
     646           7 :         long idx = Flx_cindex(g, p);
     647           7 :         affii(l, gel(W, idx));
     648           7 :         if (DEBUGLEVEL>1) err_printf("Found %lu\n", idx);
     649             :       }
     650          57 :       return gerepileuptoint(av, l);
     651             :     }
     652             :   }
     653           1 :   set_avma(av);
     654           1 :   return NULL;
     655             : }
     656             : 
     657             : static GEN
     658          28 : Flxq_log_Coppersmith_rec(GEN W, long r2, GEN a, long r, GEN T, ulong p, ulong pi, GEN m)
     659             : {
     660          28 :   GEN b = polx_Flx(T[1]);
     661          28 :   long AV = 0;
     662          28 :   GEN g = a, bad = pol0_Flx(T[1]);
     663             :   pari_timer ti;
     664             :   while(1)
     665           1 :   {
     666             :     long i, l;
     667             :     GEN V, F, E, Ao;
     668          29 :     timer_start(&ti);
     669          29 :     V = Flxq_log_find_rel(b, r2, T, p, pi, &g, &AV);
     670          29 :     if (DEBUGLEVEL>1) timer_printf(&ti,"%ld-smooth element",r2);
     671          29 :     F = gel(V,1); E = gel(V,2);
     672          29 :     l = lg(F);
     673          29 :     Ao = gen_0;
     674         229 :     for(i=1; i<l; i++)
     675             :     {
     676         201 :       GEN Fi = cindex_Flx(F[i], r2, p, T[1]);
     677             :       GEN R;
     678         201 :       if (degpol(Fi) <= r)
     679             :       {
     680         150 :         if (signe(gel(W,F[i]))==0)
     681           0 :           break;
     682         150 :         else if (signe(gel(W,F[i]))<0)
     683             :         {
     684           0 :           setsigne(gel(W,F[i]),0);
     685           0 :           R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,pi,m);
     686             :         } else
     687         150 :           R = gel(W,F[i]);
     688             :       }
     689             :       else
     690             :       {
     691          51 :         if (Flx_equal(Fi,bad)) break;
     692          51 :         R = Flxq_log_Coppersmith_d(W,Fi,r,T,p,pi,m);
     693          51 :         if (!R) bad = Fi;
     694             :       }
     695         201 :       if (!R) break;
     696         200 :       Ao = Fp_add(Ao, mulis(R, E[i]), m);
     697             :     }
     698          29 :     if (i==l) return subis(Ao,AV);
     699             :   }
     700             : }
     701             : 
     702             : static GEN
     703          14 : Flxq_log_index_Coppersmith(GEN a0, GEN b0, GEN m, GEN T0, ulong p)
     704             : {
     705          14 :   ulong pi = SMALL_ULONG(p)? 0: get_Fl_red(p);
     706          14 :   pari_sp av = avma;
     707          14 :   GEN  M, S, a, b, Ao=NULL, Bo=NULL, W, e;
     708             :   pari_timer ti;
     709          14 :   double rf = p ==3 ? 1.2 : .9;
     710          14 :   long n = degpol(T0), r = (long) sqrt(n*rf);
     711             :   GEN T;
     712          14 :   long r2 = 3*r/2;
     713          14 :   long nbi = itos(ffsumnbirred(utoipos(p), r)), nbrel=nbi*5/4;
     714          14 :   if (DEBUGLEVEL)
     715             :   {
     716           0 :     err_printf("Coppersmith: Parameters r=%ld r2=%ld\n", r,r2);
     717           0 :     err_printf("Coppersmith: Size FB=%ld rel. needed=%ld\n", nbi, nbrel);
     718           0 :     timer_start(&ti);
     719             :   }
     720          14 :   T = smallirred_Flx(p,n,get_Flx_var(T0), pi);
     721          14 :   S = Flx_ffisom(T0,T,p);
     722          14 :   a = Flx_Flxq_eval_pre(a0, S, T, p, pi);
     723          14 :   b = Flx_Flxq_eval_pre(b0, S, T, p, pi);
     724          14 :   if (DEBUGLEVEL) timer_printf(&ti,"model change");
     725          14 :   M = Flxq_log_Coppersmith(nbrel, r, T, p, pi);
     726          14 :   if (DEBUGLEVEL) timer_printf(&ti,"relations");
     727          14 :   W = check_kernel(r, M, nbi, 3*upowuu(p,r), T, p, pi, m);
     728          14 :   timer_start(&ti);
     729          14 :   Ao = Flxq_log_Coppersmith_rec(W, r2, a, r, T, p, pi, m);
     730          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth element");
     731          14 :   Bo = Flxq_log_Coppersmith_rec(W, r2, b, r, T, p, pi, m);
     732          14 :   if (DEBUGLEVEL) timer_printf(&ti,"smooth generator");
     733          14 :   e = Fp_div(Ao, Bo, m);
     734          14 :   if (!Flx_equal(Flxq_pow_pre(b0,e,T0,p,pi), a0)) pari_err_BUG("Flxq_log");
     735          14 :   return gerepileupto(av, e);
     736             : }
     737             : 
     738             : GEN
     739          28 : Flxq_log_index(GEN a, GEN b, GEN m, GEN T, ulong p)
     740             : {
     741          28 :   long d = get_Flx_degree(T);
     742          28 :   if (p==3 || (p==5 && d>41))
     743          14 :     return Flxq_log_index_Coppersmith(a, b, m, T, p);
     744          14 :   else    return Flxq_log_index_cubic(a, b, m, T, p);
     745             : }
     746             : 
     747             : int
     748      164462 : Flxq_log_use_index(GEN m, GEN T, ulong p)
     749             : {
     750      164462 :   long d = get_Flx_degree(T);
     751      164462 :   if (p==3 || (p==5 && d>41))
     752       24367 :     return 1;
     753      140095 :   else if (d<=4 || d==6)
     754      139794 :     return 0;
     755             :   else
     756         301 :     return Flxq_log_use_index_cubic(m, T, p);
     757             : }

Generated by: LCOV version 1.16