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 - char.c (source / functions) Hit Total Coverage
Test: PARI/GP v2.12.1 lcov report (development 25819-e703fe1174) Lines: 807 830 97.2 %
Date: 2020-09-18 06:10:04 Functions: 63 63 100.0 %
Legend: Lines: hit not hit

          Line data    Source code
       1             : /* Copyright (C) 2000  The PARI group.
       2             : 
       3             : This file is part of the PARI/GP package.
       4             : 
       5             : PARI/GP is free software; you can redistribute it and/or modify it under the
       6             : terms of the GNU General Public License as published by the Free Software
       7             : Foundation. It is distributed in the hope that it will be useful, but WITHOUT
       8             : ANY WARRANTY WHATSOEVER.
       9             : 
      10             : Check the License for details. You should have received a copy of it, along
      11             : with the package; see the file 'COPYING'. If not, write to the Free Software
      12             : Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. */
      13             : #include "pari.h"
      14             : #include "paripriv.h"
      15             : 
      16             : /*********************************************************************/
      17             : /**                                                                 **/
      18             : /**                  GENERIC ABELIAN CHARACTERS                     **/
      19             : /**                                                                 **/
      20             : /*********************************************************************/
      21             : /* check whether G is a znstar */
      22             : int
      23     1752345 : checkznstar_i(GEN G)
      24             : {
      25     1752128 :   return (typ(G) == t_VEC && lg(G) == 6
      26     1752044 :       && typ(znstar_get_faN(G)) == t_VEC
      27     3504473 :       && typ(gel(G,1)) == t_VEC && lg(gel(G,1)) == 3);
      28             : }
      29             : 
      30             : int
      31       80220 : char_check(GEN cyc, GEN chi)
      32       80220 : { return typ(chi) == t_VEC && lg(chi) == lg(cyc) && RgV_is_ZV(chi); }
      33             : 
      34             : /* Shallow; return [ d[1],  d[1]/d[2],...,d[1]/d[n] ] */
      35             : GEN
      36      193599 : cyc_normalize(GEN d)
      37             : {
      38      193599 :   long i, l = lg(d);
      39             :   GEN C, D;
      40      193599 :   if (l == 1) return mkvec(gen_1);
      41      193585 :   D = cgetg(l, t_VEC); gel(D,1) = C = gel(d,1);
      42      433020 :   for (i = 2; i < l; i++) gel(D,i) = diviiexact(C, gel(d,i));
      43      193585 :   return D;
      44             : }
      45             : 
      46             : /* chi character [D,C] given by chi(g_i) = \zeta_D^C[i] for all i, return
      47             :  * [d,c] such that chi(g_i) = \zeta_d^c[i] for all i and d minimal */
      48             : GEN
      49      196924 : char_simplify(GEN D, GEN C)
      50             : {
      51      196924 :   GEN d = D;
      52      196924 :   if (lg(C) == 1) d = gen_1;
      53             :   else
      54             :   {
      55      196497 :     GEN t = gcdii(d, ZV_content(C));
      56      196497 :     if (!equali1(t))
      57             :     {
      58      138600 :       long tc = typ(C);
      59      138600 :       C = ZC_Z_divexact(C, t); settyp(C, tc);
      60      138600 :       d = diviiexact(d, t);
      61             :     }
      62             :   }
      63      196924 :   return mkvec2(d,C);
      64             : }
      65             : 
      66             : /* Shallow; ncyc from cyc_normalize(): ncyc[1] = cyc[1],
      67             :  * ncyc[i] = cyc[i]/cyc[1] for i > 1; chi character on G ~ cyc.
      68             :  * Return [d,c] such that: chi( g_i ) = e(chi[i] / cyc[i]) = e(c[i]/ d) */
      69             : GEN
      70      196203 : char_normalize(GEN chi, GEN ncyc)
      71             : {
      72      196203 :   long i, l = lg(chi);
      73      196203 :   GEN c = cgetg(l, t_VEC);
      74      196203 :   if (l > 1) {
      75      196189 :     gel(c,1) = gel(chi,1);
      76      436240 :     for (i = 2; i < l; i++) gel(c,i) = mulii(gel(chi,i), gel(ncyc,i));
      77             :   }
      78      196203 :   return char_simplify(gel(ncyc,1), c);
      79             : }
      80             : 
      81             : /* Called by function 's'. x is a group object affording ".cyc" method, and
      82             :  * chi an abelian character. Return NULL if the group is (Z/nZ)^* [special
      83             :  * case more character types allowed] and x.cyc otherwise */
      84             : static GEN
      85         490 : get_cyc(GEN x, GEN chi, const char *s)
      86             : {
      87         490 :   if (nftyp(x) == typ_BIDZ)
      88             :   {
      89         448 :     if (!zncharcheck(x, chi)) pari_err_TYPE(s, chi);
      90         448 :     return NULL;
      91             :   }
      92             :   else
      93             :   {
      94          42 :     if (typ(x) != t_VEC || !RgV_is_ZV(x)) x = member_cyc(x);
      95          42 :     if (!char_check(x, chi)) pari_err_TYPE(s, chi);
      96          42 :     return x;
      97             :   }
      98             : }
      99             : 
     100             : /* conjugate character [ZV/ZC] */
     101             : GEN
     102        3045 : charconj(GEN cyc, GEN chi)
     103             : {
     104             :   long i, l;
     105        3045 :   GEN z = cgetg_copy(chi, &l);
     106        6216 :   for (i = 1; i < l; i++)
     107             :   {
     108        3171 :     GEN c = gel(chi,i);
     109        3171 :     gel(z,i) = signe(c)? subii(gel(cyc,i), c): gen_0;
     110             :   }
     111        3045 :   return z;
     112             : }
     113             : GEN
     114          28 : charconj0(GEN x, GEN chi)
     115             : {
     116          28 :   GEN cyc = get_cyc(x, chi, "charconj");
     117          28 :   return cyc? charconj(cyc, chi): zncharconj(x, chi);
     118             : }
     119             : 
     120             : GEN
     121      378126 : charorder(GEN cyc, GEN x)
     122             : {
     123      378126 :   pari_sp av = avma;
     124      378126 :   long i, l = lg(cyc);
     125      378126 :   GEN f = gen_1;
     126     1608215 :   for (i = 1; i < l; i++)
     127     1230089 :     if (signe(gel(x,i)))
     128             :     {
     129      794122 :       GEN c, o = gel(cyc,i);
     130      794122 :       c = gcdii(o, gel(x,i));
     131      794122 :       if (!is_pm1(c)) o = diviiexact(o,c);
     132      794122 :       f = lcmii(f, o);
     133             :     }
     134      378126 :   return gerepileuptoint(av, f);
     135             : }
     136             : GEN
     137         168 : charorder0(GEN x, GEN chi)
     138             : {
     139         168 :   GEN cyc = get_cyc(x, chi, "charorder");
     140         168 :   return cyc? charorder(cyc, chi): zncharorder(x, chi);
     141             : }
     142             : 
     143             : /* chi character of abelian G: chi[i] = chi(z_i), where G = \oplus Z/cyc[i] z_i.
     144             :  * Return Ker chi */
     145             : GEN
     146       77196 : charker(GEN cyc, GEN chi)
     147             : {
     148       77196 :   long i, l = lg(cyc);
     149             :   GEN nchi, ncyc, m, U;
     150             : 
     151       77196 :   if (l == 1) return cgetg(1,t_MAT); /* trivial subgroup */
     152       77189 :   ncyc = cyc_normalize(cyc);
     153       77189 :   nchi = char_normalize(chi, ncyc);
     154       77189 :   m = shallowconcat(gel(nchi,2), gel(nchi,1));
     155       77189 :   U = gel(ZV_extgcd(m), 2); setlg(U,l);
     156      174314 :   for (i = 1; i < l; i++) setlg(U[i], l);
     157       77189 :   return hnfmodid(U, gel(ncyc,1));
     158             : }
     159             : GEN
     160          35 : charker0(GEN x, GEN chi)
     161             : {
     162          35 :   GEN cyc = get_cyc(x, chi, "charker");
     163          35 :   return cyc? charker(cyc, chi): zncharker(x, chi);
     164             : }
     165             : 
     166             : GEN
     167         168 : charpow(GEN cyc, GEN a, GEN N)
     168             : {
     169             :   long i, l;
     170         168 :   GEN v = cgetg_copy(a, &l);
     171         329 :   for (i = 1; i < l; i++) gel(v,i) = Fp_mul(gel(a,i), N, gel(cyc,i));
     172         168 :   return v;
     173             : }
     174             : GEN
     175      301840 : charmul(GEN cyc, GEN a, GEN b)
     176             : {
     177             :   long i, l;
     178      301840 :   GEN v = cgetg_copy(a, &l);
     179     1349852 :   for (i = 1; i < l; i++) gel(v,i) = Fp_add(gel(a,i), gel(b,i), gel(cyc,i));
     180      301840 :   return v;
     181             : }
     182             : GEN
     183        5047 : chardiv(GEN cyc, GEN a, GEN b)
     184             : {
     185             :   long i, l;
     186        5047 :   GEN v = cgetg_copy(a, &l);
     187       10913 :   for (i = 1; i < l; i++) gel(v,i) = Fp_sub(gel(a,i), gel(b,i), gel(cyc,i));
     188        5047 :   return v;
     189             : }
     190             : GEN
     191          63 : charpow0(GEN x, GEN a, GEN N)
     192             : {
     193          63 :   GEN cyc = get_cyc(x, a, "charpow");
     194          63 :   return cyc? charpow(cyc, a, N): zncharpow(x, a, N);
     195             : }
     196             : GEN
     197         154 : charmul0(GEN x, GEN a, GEN b)
     198             : {
     199         154 :   const char *s = "charmul";
     200         154 :   GEN cyc = get_cyc(x, a, s);
     201         154 :   if (!cyc)
     202             :   {
     203         154 :     if (!zncharcheck(x, b)) pari_err_TYPE(s, b);
     204         154 :     return zncharmul(x, a, b);
     205             :   }
     206             :   else
     207             :   {
     208           0 :     if (!char_check(cyc, b)) pari_err_TYPE(s, b);
     209           0 :     return charmul(cyc, a, b);
     210             :   }
     211             : }
     212             : GEN
     213          42 : chardiv0(GEN x, GEN a, GEN b)
     214             : {
     215          42 :   const char *s = "chardiv";
     216          42 :   GEN cyc = get_cyc(x, a, s);
     217          42 :   if (!cyc)
     218             :   {
     219          42 :     if (!zncharcheck(x, b)) pari_err_TYPE(s, b);
     220          42 :     return znchardiv(x, a, b);
     221             :   }
     222             :   else
     223             :   {
     224           0 :     if (!char_check(cyc, b)) pari_err_TYPE(s, b);
     225           0 :     return chardiv(cyc, a, b);
     226             :   }
     227             : }
     228             : 
     229             : static GEN
     230      890232 : chareval_i(GEN nchi, GEN dlog, GEN z)
     231             : {
     232      890232 :   GEN o, q, r, b = gel(nchi,1);
     233      890232 :   GEN a = FpV_dotproduct(gel(nchi,2), dlog, b);
     234             :   /* image is a/b in Q/Z */
     235      890232 :   if (!z) return gdiv(a,b);
     236      889854 :   if (typ(z) == t_INT)
     237             :   {
     238      886249 :     q = dvmdii(z, b, &r);
     239      886249 :     if (signe(r)) pari_err_TYPE("chareval", z);
     240      886249 :     return mulii(a, q);
     241             :   }
     242             :   /* return z^(a*o/b), assuming z^o = 1 and b | o */
     243        3605 :   if (typ(z) != t_VEC || lg(z) != 3) pari_err_TYPE("chareval", z);
     244        3605 :   o = gel(z,2); if (typ(o) != t_INT) pari_err_TYPE("chareval", z);
     245        3605 :   q = dvmdii(o, b, &r); if (signe(r)) pari_err_TYPE("chareval", z);
     246        3605 :   q = mulii(a, q); /* in [0, o[ since a is reduced mod b */
     247        3605 :   z = gel(z,1);
     248        3605 :   if (typ(z) == t_VEC)
     249             :   {
     250        1862 :     if (itos_or_0(o) != lg(z)-1) pari_err_TYPE("chareval", z);
     251        1862 :     return gcopy(gel(z, itos(q)+1));
     252             :   }
     253             :   else
     254        1743 :     return gpow(z, q, DEFAULTPREC);
     255             : }
     256             : 
     257             : static GEN
     258        1855 : not_coprime(GEN z)
     259        1855 : { return (!z || typ(z) == t_INT)? gen_m1: gen_0; }
     260             : 
     261             : static GEN
     262          35 : get_chi(GEN cyc, GEN chi)
     263             : {
     264          35 :   if (!char_check(cyc,chi)) pari_err_TYPE("chareval", chi);
     265          35 :   return char_normalize(chi, cyc_normalize(cyc));
     266             : }
     267             : /* G a bnr.  FIXME: horribly inefficient to check that (x,N)=1, what to do ? */
     268             : static int
     269          42 : bnr_coprime(GEN G, GEN x)
     270             : {
     271          42 :   GEN t, N = gel(bnr_get_mod(G), 1);
     272          42 :   if (typ(x) == t_INT) /* shortcut */
     273             :   {
     274          14 :     t = gcdii(gcoeff(N,1,1), x);
     275          14 :     if (equali1(t)) return 1;
     276           0 :     t = idealadd(G, N, x);
     277           0 :     return equali1(gcoeff(t,1,1));
     278             :   }
     279          28 :   x = idealnumden(G, x);
     280          28 :   t = idealadd(G, N, gel(x,1));
     281          28 :   if (!equali1(gcoeff(t,1,1))) return 0;
     282          21 :   t = idealadd(G, N, gel(x,2));
     283          21 :   return equali1(gcoeff(t,1,1));
     284             : }
     285             : GEN
     286        3598 : chareval(GEN G, GEN chi, GEN x, GEN z)
     287             : {
     288        3598 :   pari_sp av = avma;
     289             :   GEN nchi, L;
     290             : 
     291        3598 :   switch(nftyp(G))
     292             :   {
     293          42 :     case typ_BNR:
     294          42 :       if (!bnr_coprime(G, x)) return not_coprime(z);
     295          28 :       L = isprincipalray(G, x);
     296          28 :       nchi = get_chi(bnr_get_cyc(G), chi);
     297          28 :       break;
     298           7 :     case typ_BNF:
     299           7 :       L = isprincipal(G, x);
     300           7 :       nchi = get_chi(bnf_get_cyc(G), chi);
     301           7 :       break;
     302        3542 :     case typ_BIDZ:
     303        3542 :       if (checkznstar_i(G)) return gerepileupto(av, znchareval(G, chi, x, z));
     304             :       /* don't implement chars on general bid: need an nf... */
     305             :     default:
     306           7 :       pari_err_TYPE("chareval", G);
     307             :       return NULL;/* LCOV_EXCL_LINE */
     308             :   }
     309          35 :   return gerepileupto(av, chareval_i(nchi, L, z));
     310             : }
     311             : 
     312             : /* nchi = [ord,D] a quasi-normalized character (ord may be a multiple of
     313             :  * the character order); return v such that v[n] = -1 if (n,N) > 1 else
     314             :  * chi(n) = e(v[n]/ord), 1 <= n <= N */
     315             : GEN
     316       33040 : ncharvecexpo(GEN G, GEN nchi)
     317             : {
     318       33040 :   long N = itou(znstar_get_N(G)), ord = itou(gel(nchi,1)), i, j, l;
     319             :   GEN cyc, gen, d, t, t1, t2, t3, e, u, u1, u2, u3;
     320       33040 :   GEN D = gel(nchi,2), v = const_vecsmall(N,-1);
     321       33040 :   pari_sp av = avma;
     322       33040 :   if (typ(D) == t_COL) {
     323       33040 :     cyc = znstar_get_conreycyc(G);
     324       33040 :     gen = znstar_get_conreygen(G);
     325             :   } else {
     326           0 :     cyc = znstar_get_cyc(G);
     327           0 :     gen = znstar_get_gen(G);
     328             :   }
     329       33040 :   l = lg(cyc);
     330       33040 :   e = u = cgetg(N+1,t_VECSMALL);
     331       33040 :   d = t = cgetg(N+1,t_VECSMALL);
     332       33040 :   *++d = 1;
     333       33040 :   *++e = 0; v[*d] = *e;
     334       70420 :   for (i = 1; i < l; i++)
     335             :   {
     336       37380 :     ulong g = itou(gel(gen,i)), c = itou(gel(cyc,i)), x = itou(gel(D,i));
     337      534856 :     for (t1=t,u1=u,j=c-1; j; j--,t1=t2,u1=u2)
     338     1101604 :       for (t2=d,u2=e, t3=t1,u3=u1; t3<t2; )
     339             :       {
     340      604128 :         *++d = Fl_mul(*++t3, g, N);
     341      604128 :         *++e = Fl_add(*++u3, x, ord); v[*d] = *e;
     342             :       }
     343             :   }
     344       33040 :   set_avma(av); return v;
     345             : }
     346             : 
     347             : /*****************************************************************************/
     348             : 
     349             : static ulong
     350      191016 : lcmuu(ulong a, ulong b) { return (a/ugcd(a,b)) * b; }
     351             : static ulong
     352       78274 : zv_charorder(GEN cyc, GEN x)
     353             : {
     354       78274 :   long i, l = lg(cyc);
     355       78274 :   ulong f = 1;
     356      244412 :   for (i = 1; i < l; i++)
     357      166138 :     if (x[i])
     358             :     {
     359      112742 :       ulong o = cyc[i];
     360      112742 :       f = lcmuu(f, o / ugcd(o, x[i]));
     361             :     }
     362       78274 :   return f;
     363             : }
     364             : 
     365             : /* N > 0 */
     366             : GEN
     367       95158 : coprimes_zv(ulong N)
     368             : {
     369       95158 :   GEN v = const_vecsmall(N,1);
     370       95158 :   pari_sp av = avma;
     371       95158 :   GEN P = gel(factoru(N),1);
     372       95158 :   long i, l = lg(P);
     373      227493 :   for (i = 1; i < l; i++)
     374             :   {
     375      132335 :     ulong p = P[i], j;
     376      873166 :     for (j = p; j <= N; j += p) v[j] = 0;
     377             :   }
     378       95158 :   set_avma(av); return v;
     379             : }
     380             : /* cf zv_cyc_minimal: return k such that g*k is minimal (wrt lex) */
     381             : long
     382       45766 : zv_cyc_minimize(GEN cyc, GEN g, GEN coprime)
     383             : {
     384       45766 :   pari_sp av = avma;
     385       45766 :   long d, k, e, i, maxi, k0, bestk, l = lg(g), o = lg(coprime)-1;
     386             :   GEN best, gk, gd;
     387             :   ulong t;
     388       45766 :   if (o == 1) return 1;
     389       53207 :   for (i = 1; i < l; i++)
     390       53207 :     if (g[i]) break;
     391       45766 :   if (g[i] == 1) return 1;
     392       37730 :   k0 = Fl_invgen(g[i], cyc[i], &t);
     393       37730 :   d = cyc[i] / (long)t;
     394       37730 :   if (k0 > 1) g = vecmoduu(Flv_Fl_mul(g, k0, cyc[i]), cyc);
     395       49931 :   for (i++; i < l; i++)
     396       44044 :     if (g[i]) break;
     397       37730 :   if (i == l) return k0;
     398       31843 :   cyc = vecslice(cyc,i,l-1);
     399       31843 :   g   = vecslice(g,  i,l-1);
     400       31843 :   e = cyc[1];
     401       31843 :   gd = Flv_Fl_mul(g, d, e);
     402       31843 :   bestk = 1; best = g; maxi = e/ugcd(d,e);
     403       47810 :   for (gk = g, k = d+1, i = 1; i < maxi; k += d, i++)
     404             :   {
     405       15967 :     long ko = k % o;
     406       15967 :     gk = Flv_add(gk, gd, e); if (!ko || !coprime[ko]) continue;
     407        7252 :     gk = vecmoduu(gk, cyc);
     408        7252 :     if (vecsmall_lexcmp(gk, best) < 0) { best = gk; bestk = k; }
     409             :   }
     410       31843 :   return gc_long(av, bestk == 1? k0: (long) Fl_mul(k0, bestk, o));
     411             : }
     412             : /* g of order o in abelian group G attached to cyc. Is g a minimal generator
     413             :  * [wrt lex order] of the cyclic subgroup it generates;
     414             :  * coprime = coprimes_zv(o) */
     415             : long
     416       77826 : zv_cyc_minimal(GEN cyc, GEN g, GEN coprime)
     417             : {
     418       77826 :   pari_sp av = avma;
     419       77826 :   long i, maxi, d, k, e, l = lg(g), o = lg(coprime)-1; /* elt order */
     420             :   GEN gd, gk;
     421       77826 :   if (o == 1) return 1;
     422       82824 :   for (k = 1; k < l; k++)
     423       82824 :     if (g[k]) break;
     424       77826 :   if (g[k] == 1) return 1;
     425       60207 :   if (cyc[k] % g[k]) return 0;
     426       60207 :   d = cyc[k] / g[k]; /* > 1 */
     427       75600 :   for (k++; k < l; k++) /* skip following 0s */
     428       75600 :     if (g[k]) break;
     429       60207 :   if (k == l) return 1;
     430       60207 :   cyc = vecslice(cyc,k,l-1);
     431       60207 :   g   = vecslice(g,  k,l-1);
     432       60207 :   e = cyc[1];
     433             :   /* find k in (Z/e)^* such that g*k mod cyc is lexicographically minimal,
     434             :    * k = 1 mod d to fix the first non-zero entry */
     435       60207 :   gd = Flv_Fl_mul(g, d, e); maxi = e/ugcd(d,e);
     436       89418 :   for (gk = g, k = d+1, i = 1; i < maxi; i++, k += d)
     437             :   {
     438       33481 :     long ko = k % o;
     439       33481 :     gk = Flv_add(gk, gd, e); if (!coprime[ko]) continue;
     440       13699 :     gk = vecmoduu(gk, cyc);
     441       13699 :     if (vecsmall_lexcmp(gk, g) < 0) return gc_long(av,0);
     442             :   }
     443       55937 :   return gc_long(av,1);
     444             : }
     445             : 
     446             : static GEN
     447        5362 : coprime_tables(long N)
     448             : {
     449        5362 :   GEN D = divisorsu(N), v = const_vec(N, NULL);
     450        5362 :   long i, l = lg(D);
     451       36351 :   for (i = 1; i < l; i++) gel(v, D[i]) = coprimes_zv(D[i]);
     452        5362 :   return v;
     453             : }
     454             : /* enumerate all group elements, modulo (Z/cyc[1])^* */
     455             : static GEN
     456        5362 : cyc2elts_normal(GEN cyc, long maxord, GEN ORD)
     457             : {
     458        5362 :   long i, n, o, N, j = 1;
     459             :   GEN z, vcoprime;
     460             : 
     461        5362 :   if (typ(cyc) != t_VECSMALL) cyc = gtovecsmall(cyc);
     462        5362 :   n = lg(cyc)-1;
     463        5362 :   if (n == 0) return cgetg(1, t_VEC);
     464        5362 :   N = zv_prod(cyc);
     465        5362 :   z = cgetg(N+1, t_VEC);
     466        5362 :   if (1 <= maxord && (!ORD|| zv_search(ORD,1)))
     467        4984 :     gel(z,j++) = zero_zv(n);
     468        5362 :   vcoprime = coprime_tables(cyc[1]);
     469       17563 :   for (i = n; i > 0; i--)
     470             :   {
     471       12201 :     GEN cyc0 = vecslice(cyc,i+1,n), pre = zero_zv(i);
     472       12201 :     GEN D = divisorsu(cyc[i]), C = cyc2elts(cyc0);
     473       12201 :     long s, t, lD = lg(D), nC = lg(C)-1; /* remove last element */
     474       45486 :     for (s = 1; s < lD-1; s++)
     475             :     {
     476       33285 :       long o0 = D[lD-s]; /* cyc[i] / D[s] */
     477       33285 :       if (o0 > maxord) continue;
     478       31794 :       pre[i] = D[s];
     479       31794 :       if (!ORD || zv_search(ORD,o0))
     480             :       {
     481       31493 :         GEN c = vecsmall_concat(pre, zero_zv(n-i));
     482       31493 :         gel(z,j++) = c;
     483             :       }
     484      110068 :       for (t = 1; t < nC; t++)
     485             :       {
     486       78274 :         GEN chi0 = gel(C,t);
     487       78274 :         o = lcmuu(o0, zv_charorder(cyc0,chi0));
     488       78274 :         if (o <= maxord && (!ORD || zv_search(ORD,o)))
     489             :         {
     490       77826 :           GEN c = vecsmall_concat(pre, chi0);
     491       77826 :           if (zv_cyc_minimal(cyc, c, gel(vcoprime,o))) gel(z,j++) = c;
     492             :         }
     493             :       }
     494             :     }
     495             :   }
     496        5362 :   setlg(z,j); return z;
     497             : }
     498             : 
     499             : GEN
     500        5803 : chargalois(GEN G, GEN ORD)
     501             : {
     502        5803 :   pari_sp av = avma;
     503             :   long maxord, i, l;
     504        5803 :   GEN v, cyc = (typ(G) == t_VEC && RgV_is_ZVpos(G))? G: member_cyc(G);
     505        5803 :   if (lg(cyc) == 1) retmkvec(cgetg(1,t_VEC));
     506        5362 :   maxord = itou(cyc_get_expo(cyc));
     507        5362 :   if (ORD && gequal0(ORD)) ORD = NULL;
     508        5362 :   if (ORD)
     509         406 :     switch(typ(ORD))
     510             :     {
     511             :       long l;
     512          21 :       case t_VEC:
     513          21 :         ORD = ZV_to_zv(ORD);
     514         385 :       case t_VECSMALL:
     515         385 :         ORD = leafcopy(ORD);
     516         385 :         vecsmall_sort(ORD);
     517         385 :         l = lg(ORD);
     518         385 :         if (l == 1) return cgetg(1, t_VECSMALL);
     519         385 :         maxord = minss(maxord, ORD[l-1]);
     520         385 :         break;
     521          21 :       case t_INT:
     522          21 :         maxord = minss(maxord, itos(ORD));
     523          21 :         ORD = NULL;
     524          21 :         break;
     525           0 :       default: pari_err_TYPE("chargalois", ORD);
     526             :     }
     527        5362 :   v = cyc2elts_normal(cyc, maxord, ORD); l = lg(v);
     528      115395 :   for(i = 1; i < l; i++) gel(v,i) = zv_to_ZV(gel(v,i));
     529        5362 :   return gerepileupto(av, v);
     530             : }
     531             : 
     532             : /*********************************************************************/
     533             : /**                                                                 **/
     534             : /**                  (Z/NZ)^* AND DIRICHLET CHARACTERS              **/
     535             : /**                                                                 **/
     536             : /*********************************************************************/
     537             : 
     538             : GEN
     539       78505 : znstar0(GEN N, long flag)
     540             : {
     541       78505 :   GEN F = NULL, P, E, cyc, gen, mod, G;
     542             :   long i, i0, l, nbprimes;
     543       78505 :   pari_sp av = avma;
     544             : 
     545       78505 :   if (flag && flag != 1) pari_err_FLAG("znstar");
     546       78505 :   if ((F = check_arith_all(N,"znstar")))
     547             :   {
     548        9534 :     F = clean_Z_factor(F);
     549        9534 :     N = typ(N) == t_VEC? gel(N,1): factorback(F);
     550             :   }
     551       78505 :   if (!signe(N))
     552             :   {
     553          21 :     if (flag) pari_err_IMPL("znstar(0,1)");
     554          14 :     set_avma(av);
     555          14 :     retmkvec3(gen_2, mkvec(gen_2), mkvec(gen_m1));
     556             :   }
     557       78484 :   N = absi_shallow(N);
     558       78484 :   if (abscmpiu(N,2) <= 0)
     559             :   {
     560        7651 :     G = mkvec3(gen_1, cgetg(1,t_VEC), cgetg(1,t_VEC));
     561        7651 :     if (flag)
     562             :     {
     563        7623 :       GEN v = const_vec(6,cgetg(1,t_VEC));
     564        7623 :       gel(v,3) = cgetg(1,t_MAT);
     565       15239 :       F = equali1(N)? mkvec2(cgetg(1,t_COL),cgetg(1,t_VECSMALL))
     566        7623 :                     : mkvec2(mkcol(gen_2), mkvecsmall(1));
     567        7623 :       G = mkvec5(mkvec2(N,mkvec(gen_0)), G, F, v, cgetg(1,t_MAT));
     568             :     }
     569        7651 :     return gerepilecopy(av,G);
     570             :   }
     571       70833 :   if (!F) F = Z_factor(N);
     572       70833 :   P = gel(F,1); nbprimes = lg(P)-1;
     573       70833 :   E = ZV_to_nv( gel(F,2) );
     574       70833 :   switch(mod8(N))
     575             :   {
     576       19061 :     case 0:
     577       19061 :       P = shallowconcat(gen_2,P);
     578       19061 :       E = vecsmall_prepend(E, E[1]); /* add a copy of p=2 row */
     579       19061 :       i = 2; /* 2 generators at 2 */
     580       19061 :       break;
     581       14203 :     case 4:
     582       14203 :       i = 1; /* 1 generator at 2 */
     583       14203 :       break;
     584        6895 :     case 2: case 6:
     585        6895 :       P = vecsplice(P,1);
     586        6895 :       E = vecsplice(E,1); /* remove 2 */
     587        6895 :       i = 0; /* no generator at 2 */
     588        6895 :       break;
     589       30674 :     default:
     590       30674 :       i = 0; /* no generator at 2 */
     591       30674 :       break;
     592             :   }
     593       70833 :   l = lg(P);
     594       70833 :   cyc = cgetg(l,t_VEC);
     595       70833 :   gen = cgetg(l,t_VEC);
     596       70833 :   mod = cgetg(l,t_VEC);
     597             :   /* treat p=2 first */
     598       70833 :   if (i == 2)
     599             :   {
     600       19061 :     long v2 = E[1];
     601       19061 :     GEN q = int2n(v2);
     602       19061 :     gel(cyc,1) = gen_2;
     603       19061 :     gel(gen,1) = subiu(q,1); /* -1 */
     604       19061 :     gel(mod,1) = q;
     605       19061 :     gel(cyc,2) = int2n(v2-2);
     606       19061 :     gel(gen,2) = utoipos(5); /* Conrey normalization */
     607       19061 :     gel(mod,2) = q;
     608       19061 :     i0 = 3;
     609             :   }
     610       51772 :   else if (i == 1)
     611             :   {
     612       14203 :     gel(cyc,1) = gen_2;
     613       14203 :     gel(gen,1) = utoipos(3);
     614       14203 :     gel(mod,1) = utoipos(4);
     615       14203 :     i0 = 2;
     616             :   }
     617             :   else
     618       37569 :     i0 = 1;
     619             :   /* odd primes, fill remaining entries */
     620      181468 :   for (i = i0; i < l; i++)
     621             :   {
     622      110635 :     long e = E[i];
     623      110635 :     GEN p = gel(P,i), q = powiu(p, e-1), Q = mulii(p, q);
     624      110635 :     gel(cyc,i) = subii(Q, q); /* phi(p^e) */
     625      110635 :     gel(gen,i) = pgener_Zp(p);/* Conrey normalization, for e = 1 also */
     626      110635 :     gel(mod,i) = Q;
     627             :   }
     628             :   /* gen[i] has order cyc[i] and generates (Z/mod[i]Z)^* */
     629       70833 :   if (nbprimes > 1) /* lift generators to (Z/NZ)^*, = 1 mod N/mod[i] */
     630      193872 :     for (i=1; i<l; i++)
     631             :     {
     632      141967 :       GEN Q = gel(mod,i), g = gel(gen,i), qinv = Fp_inv(Q, diviiexact(N,Q));
     633      141967 :       g = addii(g, mulii(mulii(subsi(1,g),qinv),Q));
     634      141967 :       gel(gen,i) = modii(g, N);
     635             :     }
     636             : 
     637             :   /* cyc[i] > 1 and remain so in the loop, gen[i] = 1 mod (N/mod[i]) */
     638       70833 :   if (!flag)
     639             :   { /* update generators in place; about twice faster */
     640        6447 :     G = gen;
     641        6594 :     for (i=l-1; i>=2; i--)
     642             :     {
     643         147 :       GEN ci = gel(cyc,i), gi = gel(G,i);
     644             :       long j;
     645         364 :       for (j=i-1; j>=1; j--) /* we want cyc[i] | cyc[j] */
     646             :       {
     647         217 :         GEN cj = gel(cyc,j), gj, qj, v, d;
     648             : 
     649         217 :         d = bezout(ci,cj,NULL,&v); /* > 1 */
     650         322 :         if (absequalii(ci, d)) continue; /* ci | cj */
     651         126 :         if (absequalii(cj, d)) { /* cj | ci */
     652         105 :           swap(gel(G,j),gel(G,i));
     653         105 :           gi = gel(G,i);
     654         105 :           swap(gel(cyc,j),gel(cyc,i));
     655         105 :           ci = gel(cyc,i); continue;
     656             :         }
     657             : 
     658          21 :         qj = diviiexact(cj,d);
     659          21 :         gel(cyc,j) = mulii(ci,qj);
     660          21 :         gel(cyc,i) = d;
     661             : 
     662             :         /* [1,v*cj/d; 0,1]*[1,0;-1,1]*diag(cj,ci)*[ci/d,-v; cj/d,u]
     663             :          * = diag(lcm,gcd), with u ci + v cj = d */
     664          21 :         gj = gel(G,j);
     665             :         /* (gj, gi) *= [1,0; -1,1]^-1 */
     666          21 :         gj = Fp_mul(gj, gi, N); /* order ci*qj = lcm(ci,cj) */
     667             :         /* (gj,gi) *= [1,v*qj; 0,1]^-1 */
     668          21 :         togglesign_safe(&v);
     669          21 :         if (signe(v) < 0) v = modii(v,ci); /* >= 0 to avoid inversions */
     670          21 :         gel(G,i) = gi = Fp_mul(gi, Fp_pow(gj, mulii(qj, v), N), N);
     671          21 :         gel(G,j) = gj;
     672          21 :         ci = d; if (absequaliu(ci, 2)) break;
     673             :       }
     674             :     }
     675        6447 :     G = mkvec3(ZV_prod(cyc), cyc, FpV_to_mod(G,N));
     676             :   }
     677             :   else
     678             :   { /* keep matrices between generators, return an 'init' structure */
     679       64386 :     GEN D, U, Ui, fao = cgetg(l, t_VEC), lo = cgetg(l, t_VEC);
     680       64386 :     F = mkvec2(P, E);
     681       64386 :     D = ZV_snf_group(cyc,&U,&Ui);
     682      220752 :     for (i = 1; i < l; i++)
     683             :     {
     684      156366 :       GEN t = gen_0, p = gel(P,i), p_1 = subiu(p,1);
     685      156366 :       long e = E[i];
     686      156366 :       gel(fao,i) = get_arith_ZZM(p_1);
     687      156366 :       if (e >= 2 && !absequaliu(p,2))
     688             :       {
     689       12663 :         GEN q = gel(mod,i), g = Fp_pow(gel(gen,i),p_1,q);
     690       12663 :         if (e == 2)
     691       10318 :           t = Fp_inv(diviiexact(subiu(g,1), p), p);
     692             :         else
     693        2345 :           t = ginv(Qp_log(cvtop(g,p,e)));
     694             :       }
     695      156366 :       gel(lo,i) = t;
     696             :     }
     697       64386 :     G = cgetg(l, t_VEC);
     698      220752 :     for (i = 1; i < l; i++) gel(G,i) = FpV_factorback(gen, gel(Ui,i), N);
     699       64386 :     G = mkvec3(ZV_prod(D), D, G);
     700       64386 :     G = mkvec5(mkvec2(N,mkvec(gen_0)), G, F,
     701             :                mkvecn(6,mod,fao,Ui,gen,cyc,lo), U);
     702             :   }
     703       70833 :   return gerepilecopy(av, G);
     704             : }
     705             : GEN
     706        6405 : znstar(GEN N) { return znstar0(N, 0); }
     707             : 
     708             : /* g has order 2^(e-2), g,h = 1 (mod 4); return x s.t. g^x = h (mod 2^e) */
     709             : static GEN
     710      220661 : Zideallog_2k(GEN h, GEN g, long e, GEN pe)
     711             : {
     712      220661 :   GEN a = Fp_log(h, g, int2n(e-2), pe);
     713      220661 :   if (typ(a) != t_INT) return NULL;
     714      220661 :   return a;
     715             : }
     716             : 
     717             : /* ord = get_arith_ZZM(p-1), simplified form of znlog_rec: g is known
     718             :  * to be a primitive root mod p^e; lo = 1/log_p(g^(p-1)) */
     719             : static GEN
     720      758065 : Zideallog_pk(GEN h, GEN g, GEN p, long e, GEN pe, GEN ord, GEN lo)
     721             : {
     722      758065 :   GEN gp = (e == 1)? g: modii(g, p);
     723      758065 :   GEN hp = (e == 1)? h: modii(h, p);
     724      758065 :   GEN a = Fp_log(hp, gp, ord, p);
     725      758065 :   if (typ(a) != t_INT) return NULL;
     726      758058 :   if (e > 1)
     727             :   { /* find a s.t. g^a = h (mod p^e), p odd prime, e > 0, (h,p) = 1 */
     728             :     /* use p-adic log: O(log p + e) mul*/
     729       31213 :     GEN b, p_1 = gel(ord,1);
     730       31213 :     h = Fp_mul(h, Fp_pow(g, negi(a), pe), pe);
     731             :     /* g,h = 1 mod p; compute b s.t. h = g^b */
     732       31213 :     if (e == 2) /* simpler */
     733       24304 :       b = Fp_mul(diviiexact(subiu(h,1), p), lo, p);
     734             :     else
     735        6909 :       b = padic_to_Q(gmul(Qp_log(cvtop(h, p, e)), lo));
     736       31213 :     a = addii(a, mulii(p_1, b));
     737             :   }
     738      758058 :   return a;
     739             : }
     740             : 
     741             : int
     742      692811 : znconrey_check(GEN cyc, GEN chi)
     743      692811 : { return typ(chi) == t_COL && lg(chi) == lg(cyc) && RgV_is_ZV(chi); }
     744             : 
     745             : int
     746      189217 : zncharcheck(GEN G, GEN chi)
     747             : {
     748      189217 :   switch(typ(chi))
     749             :   {
     750         875 :     case t_INT: return 1;
     751      186578 :     case t_COL: return znconrey_check(znstar_get_conreycyc(G), chi);
     752        1764 :     case t_VEC: return char_check(znstar_get_cyc(G), chi);
     753             :   }
     754           0 :   return 0;
     755             : }
     756             : 
     757             : GEN
     758      113470 : znconreyfromchar_normalized(GEN bid, GEN chi)
     759             : {
     760      113470 :   GEN nchi, U = znstar_get_U(bid);
     761      113470 :   long l = lg(chi);
     762      113470 :   if (l == 1) retmkvec2(gen_1,cgetg(1,t_VEC));
     763      113015 :   if (!RgV_is_ZV(chi) || lgcols(U) != l) pari_err_TYPE("lfunchiZ", chi);
     764      113008 :   nchi = char_normalize(chi, cyc_normalize(znstar_get_cyc(bid)));
     765      113008 :   gel(nchi,2) = ZV_ZM_mul(gel(nchi,2),U); return nchi;
     766             : }
     767             : 
     768             : GEN
     769      111552 : znconreyfromchar(GEN bid, GEN chi)
     770             : {
     771      111552 :   GEN nchi = znconreyfromchar_normalized(bid, chi);
     772      111545 :   GEN v = char_denormalize(znstar_get_conreycyc(bid), gel(nchi,1), gel(nchi,2));
     773      111545 :   settyp(v, t_COL); return v;
     774             : }
     775             : 
     776             : /* discrete log on canonical "primitive root" generators
     777             :  * Allow log(x) instead of x [usual discrete log on bid's generators] */
     778             : GEN
     779      920423 : znconreylog(GEN bid, GEN x)
     780             : {
     781      920423 :   pari_sp av = avma;
     782             :   GEN N, L, F, P,E, y, pe, fao, gen, lo, cycg;
     783             :   long i, l;
     784      920423 :   if (!checkznstar_i(bid)) pari_err_TYPE("znconreylog", bid);
     785      920423 :   N = znstar_get_N(bid);
     786      920423 :   if (typ(N) != t_INT) pari_err_TYPE("znconreylog", N);
     787      920416 :   if (abscmpiu(N, 2) <= 0) return cgetg(1, t_COL);
     788      917602 :   cycg = znstar_get_conreycyc(bid);
     789      917602 :   switch(typ(x))
     790             :   {
     791             :     GEN Ui;
     792      914081 :     case t_INT:
     793      914081 :       if (!signe(x)) pari_err_COPRIME("znconreylog", x, N);
     794      914074 :       break;
     795          35 :     case t_COL: /* log_bid(x) */
     796          35 :       Ui = znstar_get_Ui(bid);
     797          35 :       if (!RgV_is_ZV(x) || lg(x) != lg(Ui)) pari_err_TYPE("znconreylog", x);
     798          35 :       return gerepileupto(av, vecmodii(ZM_ZC_mul(Ui,x), cycg));
     799        3486 :     case t_VEC:
     800        3486 :       return gerepilecopy(av, znconreyfromchar(bid, x));
     801           0 :     default: pari_err_TYPE("znconreylog", x);
     802             :   }
     803      914074 :   F = znstar_get_faN(bid); /* factor(N) */
     804      914074 :   P = gel(F, 1); /* prime divisors of N */
     805      914074 :   E = gel(F, 2); /* exponents */
     806      914074 :   L = gel(bid,4);
     807      914074 :   pe = znstar_get_pe(bid);
     808      914074 :   fao = gel(L,2);
     809      914074 :   gen = znstar_get_conreygen(bid); /* local generators of (Z/p^k)^* */
     810      914074 :   lo = gel(L,6); /* 1/log_p((g_i)^(p_i-1)) */
     811             : 
     812      914074 :   l = lg(gen); i = 1;
     813      914074 :   y = cgetg(l, t_COL);
     814      914074 :   if (!mod2(N) && !mod2(x)) pari_err_COPRIME("znconreylog", x, N);
     815      914060 :   if (absequaliu(gel(P,1), 2) && E[1] >= 2)
     816             :   {
     817      444990 :     if (E[1] == 2)
     818      224329 :       gel(y,i++) = mod4(x) == 1? gen_0: gen_1;
     819             :     else
     820             :     {
     821      220661 :       GEN a, x2, q2 = gel(pe,1);
     822      220661 :       x2 = modii(x, q2);
     823      220661 :       if (mod4(x) == 1) /* 1 or 5 mod 8*/
     824      149618 :         gel(y,i++) = gen_0;
     825             :       else /* 3 or 7 */
     826       71043 :       { gel(y,i++) = gen_1; x2 = subii(q2, x2); }
     827             :       /* x2 = 5^x mod q */
     828      220661 :       a = Zideallog_2k(x2, gel(gen,i), E[1], q2);
     829      220661 :       if (!a) pari_err_COPRIME("znconreylog", x, N);
     830      220661 :       gel(y, i++) = a;
     831             :     }
     832             :   }
     833     1672118 :   while (i < l)
     834             :   {
     835      758065 :     GEN p = gel(P,i), q = gel(pe,i), xpe = modii(x, q);
     836      758065 :     GEN a = Zideallog_pk(xpe, gel(gen,i), p, E[i], q, gel(fao,i), gel(lo,i));
     837      758065 :     if (!a) pari_err_COPRIME("znconreylog", x, N);
     838      758058 :     gel(y, i++) = a;
     839             :   }
     840      914053 :   return gerepilecopy(av, y);
     841             : }
     842             : GEN
     843        6720 : Zideallog(GEN bid, GEN x)
     844             : {
     845        6720 :   pari_sp av = avma;
     846        6720 :   GEN y = znconreylog(bid, x), U = znstar_get_U(bid);
     847        6692 :   return gerepileupto(av, ZM_ZC_mul(U, y));
     848             : }
     849             : GEN
     850         294 : znlog0(GEN h, GEN g, GEN o)
     851             : {
     852         294 :   if (typ(g) == t_VEC)
     853             :   {
     854             :     GEN N;
     855          56 :     if (o) pari_err_TYPE("znlog [with znstar]", o);
     856          56 :     if (!checkznstar_i(g)) pari_err_TYPE("znlog", g);
     857          56 :     N = znstar_get_N(g);
     858          56 :     h = Rg_to_Fp(h,N);
     859          49 :     return Zideallog(g, h);
     860             :   }
     861         238 :   return znlog(h, g, o);
     862             : }
     863             : 
     864             : GEN
     865       75789 : znconreyexp(GEN bid, GEN x)
     866             : {
     867       75789 :   pari_sp av = avma;
     868             :   long i, l;
     869             :   GEN N, pe, gen, cycg, v, vmod;
     870             :   int e2;
     871       75789 :   if (!checkznstar_i(bid)) pari_err_TYPE("znconreyexp", bid);
     872       75789 :   cycg = znstar_get_conreycyc(bid);
     873       75789 :   switch(typ(x))
     874             :   {
     875          21 :     case t_VEC:
     876          21 :       x = znconreylog(bid, x);
     877          21 :       break;
     878       75768 :     case t_COL:
     879       75768 :       if (RgV_is_ZV(x) && lg(x) == lg(cycg)) break;
     880           7 :     default: pari_err_TYPE("znconreyexp",x);
     881             :   }
     882       75782 :   pe = znstar_get_pe(bid);
     883       75782 :   gen = znstar_get_conreygen(bid); /* local generators of (Z/p^k)^* */
     884       75782 :   cycg = znstar_get_conreycyc(bid);
     885       75782 :   l = lg(x); v = cgetg(l, t_VEC);
     886       75782 :   N = znstar_get_N(bid);
     887       75782 :   e2 = !mod8(N); /* 2 generators at p = 2 */
     888      245455 :   for (i = 1; i < l; i++)
     889             :   {
     890             :     GEN q, g, m;
     891      169673 :     if (i == 1 && e2) { gel(v,1) = NULL; continue; }
     892      153867 :     q = gel(pe,i);
     893      153867 :     g = gel(gen,i);
     894      153867 :     m = modii(gel(x,i), gel(cycg,i));
     895      153867 :     m = Fp_pow(g, m, q);
     896      153867 :     if (i == 2 && e2 && signe(gel(x,1))) m = Fp_neg(m, q);
     897      153867 :     gel(v,i) = mkintmod(m, q);
     898             :   }
     899       75782 :   if (e2) v = vecsplice(v, 1);
     900       75782 :   v = chinese1_coprime_Z(v);
     901       75782 :   vmod = gel(v,1);
     902       75782 :   v = gel(v,2);
     903       75782 :   if (mpodd(v) || mpodd(N)) return gerepilecopy(av, v);
     904             :   /* handle N = 2 mod 4 */
     905         231 :   return gerepileuptoint(av, addii(v, vmod));
     906             : }
     907             : 
     908             : /* Return Dirichlet character \chi_q(m,.), where bid = znstar(q);
     909             :  * m is either a t_INT, or a t_COL [Conrey logarithm] */
     910             : GEN
     911       45906 : znconreychar(GEN bid, GEN m)
     912             : {
     913       45906 :   pari_sp av = avma;
     914             :   GEN c, d, nchi;
     915             : 
     916       45906 :   if (!checkznstar_i(bid)) pari_err_TYPE("znconreychar", bid);
     917       45899 :   switch(typ(m))
     918             :   {
     919       45899 :     case t_COL:
     920             :     case t_INT:
     921       45899 :       nchi = znconrey_normalized(bid,m); /* images of primroot gens */
     922       45892 :       break;
     923           0 :     default:
     924           0 :       pari_err_TYPE("znconreychar",m);
     925             :       return NULL;/*LCOV_EXCL_LINE*/
     926             :   }
     927       45892 :   d = gel(nchi,1);
     928       45892 :   c = ZV_ZM_mul(gel(nchi,2), znstar_get_Ui(bid)); /* images of bid gens */
     929       45892 :   return gerepilecopy(av, char_denormalize(znstar_get_cyc(bid),d,c));
     930             : }
     931             : 
     932             : /* chi a t_INT or Conrey log describing a character. Return conductor, as an
     933             :  * integer if primitive; as a t_VEC [N,factor(N)] if not. Set *pm=m to the
     934             :  * attached primitive character: chi(g_i) = m[i]/ord(g_i)
     935             :  * Caller should use znconreylog_normalize(BID, m), once BID(conductor) is
     936             :  * computed (wasteful to do it here since BID is shared by many characters) */
     937             : GEN
     938      509138 : znconreyconductor(GEN bid, GEN chi, GEN *pm)
     939             : {
     940      509138 :   pari_sp av = avma;
     941             :   GEN q, m, F, P, E;
     942             :   long i, j, l;
     943      509138 :   int e2, primitive = 1;
     944             : 
     945      509138 :   if (!checkznstar_i(bid)) pari_err_TYPE("znconreyconductor", bid);
     946      509138 :   if (typ(chi) == t_COL)
     947             :   {
     948      506233 :     if (!znconrey_check(znstar_get_conreycyc(bid), chi))
     949           0 :       pari_err_TYPE("znconreyconductor",chi);
     950             :   }
     951             :   else
     952        2905 :     chi = znconreylog(bid, chi);
     953      509131 :   l = lg(chi);
     954      509131 :   F = znstar_get_faN(bid);
     955      509131 :   P = gel(F,1);
     956      509131 :   E = gel(F,2);
     957      509131 :   if (l == 1)
     958             :   {
     959       92974 :     set_avma(av);
     960       92974 :     if (pm) *pm = cgetg(1,t_COL);
     961       92974 :     if (lg(P) == 1) return gen_1;
     962          14 :     retmkvec2(gen_1, trivial_fact());
     963             :   }
     964      416157 :   P = leafcopy(P);
     965      416157 :   E = leafcopy(E);
     966      416157 :   m = cgetg(l, t_COL);
     967      416157 :   e2 = (E[1] >= 3 && absequaliu(gel(P,1),2));
     968      416157 :   i = j = 1;
     969      416157 :   if (e2)
     970             :   { /* two generators at p=2 */
     971      268499 :     GEN a1 = gel(chi,1), a = gel(chi,2);
     972      268499 :     i = 3;
     973      268499 :     if (!signe(a))
     974             :     {
     975       93170 :       e2 =  primitive = 0;
     976       93170 :       if (signe(a1))
     977             :       { /* lose one generator */
     978       43099 :         E[1] = 2;
     979       43099 :         gel(m,1) = a1;
     980       43099 :         j = 2;
     981             :       }
     982             :       /* else lose both */
     983             :     }
     984             :     else
     985             :     {
     986      175329 :       long v = Z_pvalrem(a, gen_2, &a);
     987      175329 :       if (v) { E[1] -= v; E[2] = E[1]; primitive = 0; }
     988      175329 :       gel(m,1) = a1;
     989      175329 :       gel(m,2) = a;
     990      175329 :       j = 3;
     991             :     }
     992             :   }
     993      416157 :   l = lg(P);
     994     1191323 :   for (; i < l; i++)
     995             :   {
     996      775166 :     GEN p = gel(P,i), a = gel(chi,i);
     997             :     /* image of g_i in Q/Z is a/cycg[i], cycg[i] = order(g_i) */
     998      775166 :     if (!signe(a)) primitive = 0;
     999             :     else
    1000             :     {
    1001      561918 :       long v = Z_pvalrem(a, p, &a);
    1002      561918 :       E[j] = E[i]; if (v) { E[j] -= v; primitive = 0; }
    1003      561918 :       gel(P,j) = gel(P,i);
    1004      561918 :       gel(m,j) = a; j++;
    1005             :     }
    1006             :   }
    1007      416157 :   setlg(m,j);
    1008      416157 :   setlg(P,j);
    1009      416157 :   setlg(E,j);
    1010      416157 :   if (pm) *pm = m; /* attached primitive  character */
    1011      416157 :   if (primitive)
    1012             :   {
    1013      131376 :     q = znstar_get_N(bid);
    1014      131376 :     if (mod4(q) == 2) primitive = 0;
    1015             :   }
    1016      416157 :   if (!primitive)
    1017             :   {
    1018      285558 :     if (e2)
    1019             :     { /* remove duplicate p=2 row from factorization */
    1020      110810 :       P = vecsplice(P,1);
    1021      110810 :       E = vecsplice(E,1);
    1022             :     }
    1023      285558 :     E = zc_to_ZC(E);
    1024      285558 :     q = mkvec2(factorback2(P,E), mkmat2(P,E));
    1025             :   }
    1026      416157 :   gerepileall(av, pm? 2: 1, &q, pm);
    1027      416157 :   return q;
    1028             : }
    1029             : 
    1030             : GEN
    1031        7616 : zncharinduce(GEN G, GEN chi, GEN N)
    1032             : {
    1033        7616 :   pari_sp av = avma;
    1034             :   GEN q, faq, P, E, Pq, Eq, CHI;
    1035             :   long i, j, l;
    1036             :   int e2;
    1037             : 
    1038        7616 :   if (!checkznstar_i(G)) pari_err_TYPE("zncharinduce", G);
    1039        7616 :   if (!zncharcheck(G, chi)) pari_err_TYPE("zncharinduce", chi);
    1040        7616 :   q = znstar_get_N(G);
    1041        7616 :   if (typ(chi) != t_COL) chi = znconreylog(G, chi);
    1042        7616 :   if (checkznstar_i(N))
    1043             :   {
    1044        7427 :     GEN faN = znstar_get_faN(N);
    1045        7427 :     P = gel(faN,1); l = lg(P);
    1046        7427 :     E = gel(faN,2);
    1047        7427 :     N = znstar_get_N(N);
    1048        7427 :     if (l > 2 && equalii(gel(P,1),gel(P,2)))
    1049             :     { /* remove duplicate 2 */
    1050        2114 :       l--;
    1051        2114 :       P = vecsplice(P,1);
    1052        2114 :       E = vecsplice(E,1);
    1053             :     }
    1054             :   }
    1055             :   else
    1056             :   {
    1057         189 :     GEN faN = check_arith_pos(N, "zncharinduce");
    1058         189 :     if (!faN) faN = Z_factor(N);
    1059             :     else
    1060           0 :       N = (typ(N) == t_VEC)? gel(N,1): factorback(faN);
    1061         189 :     P = gel(faN,1);
    1062         189 :     E = gel(faN,2);
    1063             :   }
    1064        7616 :   if (!dvdii(N,q)) pari_err_DOMAIN("zncharinduce", "N % q", "!=", gen_0, N);
    1065        7609 :   if (mod4(N) == 2)
    1066             :   { /* remove 2 */
    1067          70 :     if (lg(P) > 1 && absequaliu(gel(P,1), 2))
    1068             :     {
    1069          28 :       P = vecsplice(P,1);
    1070          28 :       E = vecsplice(E,1);
    1071             :     }
    1072          70 :     N = shifti(N,-1);
    1073             :   }
    1074        7609 :   l = lg(P);
    1075             :   /* q = N or q = 2N, N odd */
    1076        7609 :   if (cmpii(N,q) <= 0) return gerepilecopy(av, chi);
    1077             :   /* N > 1 => l > 1*/
    1078        7490 :   if (typ(E) != t_VECSMALL) E = ZV_to_zv(E);
    1079        7490 :   e2 = (E[1] >= 3 && absequaliu(gel(P,1),2)); /* 2 generators at 2 mod N */
    1080        7490 :   if (ZV_equal0(chi))
    1081             :   {
    1082        5012 :     set_avma(av);
    1083        5012 :     return equali1(N)? cgetg(1, t_COL): zerocol(l+e2 - 1);
    1084             :   }
    1085             : 
    1086        2478 :   faq = znstar_get_faN(G);
    1087        2478 :   Pq = gel(faq,1);
    1088        2478 :   Eq = gel(faq,2);
    1089        2478 :   CHI = cgetg(l+e2, t_COL);
    1090        2478 :   i = j = 1;
    1091        2478 :   if (e2)
    1092             :   {
    1093         861 :     i = 2; j = 3;
    1094         861 :     if (absequaliu(gel(Pq,1), 2))
    1095             :     {
    1096         693 :       if (Eq[1] >= 3)
    1097             :       { /* 2 generators at 2 mod q */
    1098         364 :         gel(CHI,1) = gel(chi,1);
    1099         364 :         gel(CHI,2) = shifti(gel(chi,2), E[1]-Eq[1]);
    1100             :       }
    1101         329 :       else if (Eq[1] == 2)
    1102             :       { /* 1 generator at 2 mod q */
    1103         329 :         gel(CHI,1) = gel(chi,1);
    1104         329 :         gel(CHI,2) = gen_0;
    1105             :       }
    1106             :       else
    1107           0 :         gel(CHI,1) = gel(CHI,2) = gen_0;
    1108             :     }
    1109             :     else
    1110         168 :       gel(CHI,1) = gel(CHI,2) = gen_0;
    1111             :   }
    1112        6699 :   for (; i < l; i++,j++)
    1113             :   {
    1114        4221 :     GEN p = gel(P,i);
    1115        4221 :     long k = ZV_search(Pq, p);
    1116        4221 :     gel(CHI,j) = k? mulii(gel(chi,k), powiu(p, E[i]-Eq[k])): gen_0;
    1117             :   }
    1118        2478 :   return gerepilecopy(av, CHI);
    1119             : }
    1120             : 
    1121             : /* m a Conrey log [on the canonical primitive roots], cycg the primitive
    1122             :  * roots orders */
    1123             : GEN
    1124      966994 : znconreylog_normalize(GEN G, GEN m)
    1125             : {
    1126      966994 :   GEN cycg = znstar_get_conreycyc(G);
    1127             :   long i, l;
    1128      966994 :   GEN d, M = cgetg_copy(m, &l);
    1129      966994 :   if (typ(cycg) != t_VEC || lg(cycg) != l)
    1130           0 :     pari_err_TYPE("znconreylog_normalize",mkvec2(m,cycg));
    1131     2503704 :   for (i = 1; i < l; i++) gel(M,i) = gdiv(gel(m,i), gel(cycg,i));
    1132             :   /* m[i]: image of primroot generators g_i in Q/Z */
    1133      966994 :   M = Q_remove_denom(M, &d);
    1134      966994 :   return mkvec2(d? d: gen_1, M);
    1135             : }
    1136             : 
    1137             : /* return normalized character on Conrey generators attached to chi: Conrey
    1138             :  * label (t_INT), char on (SNF) G.gen* (t_VEC), or Conrey log (t_COL) */
    1139             : GEN
    1140      954674 : znconrey_normalized(GEN G, GEN chi)
    1141             : {
    1142      954674 :   switch(typ(chi))
    1143             :   {
    1144         420 :     case t_INT: /* Conrey label */
    1145         420 :       return znconreylog_normalize(G, znconreylog(G, chi));
    1146      952336 :     case t_COL: /* Conrey log */
    1147      952336 :       if (!RgV_is_ZV(chi)) break;
    1148      952336 :       return znconreylog_normalize(G, chi);
    1149        1918 :     case t_VEC: /* char on G.gen */
    1150        1918 :       if (!RgV_is_ZV(chi)) break;
    1151        1918 :       return znconreyfromchar_normalized(G, chi);
    1152             :   }
    1153           0 :   pari_err_TYPE("znchareval",chi);
    1154             :   return NULL;/* LCOV_EXCL_LINE */
    1155             : }
    1156             : 
    1157             : /* return 1 iff chi(-1) = -1, and 0 otherwise */
    1158             : long
    1159      180369 : zncharisodd(GEN G, GEN chi)
    1160             : {
    1161             :   long i, l, s;
    1162             :   GEN N;
    1163      180369 :   if (!checkznstar_i(G)) pari_err_TYPE("zncharisodd", G);
    1164      180369 :   if (!zncharcheck(G, chi)) pari_err_TYPE("zncharisodd", chi);
    1165      180369 :   if (typ(chi) != t_COL) chi = znconreylog(G, chi);
    1166      180369 :   N = znstar_get_N(G);
    1167      180369 :   l = lg(chi);
    1168      180369 :   s = 0;
    1169      180369 :   if (!mod8(N))
    1170             :   {
    1171       89747 :     s = mpodd(gel(chi,1));
    1172       89747 :     i = 3;
    1173             :   }
    1174             :   else
    1175       90622 :     i = 1;
    1176      505939 :   for (; i < l; i++) s += mpodd(gel(chi,i));
    1177      180369 :   return odd(s);
    1178             : }
    1179             : 
    1180             : GEN
    1181         847 : znchartokronecker(GEN G, GEN chi, long flag)
    1182             : {
    1183         847 :   pari_sp av = avma;
    1184             :   long s;
    1185             :   GEN F, o;
    1186             : 
    1187         847 :   if (flag && flag != 1) pari_err_FLAG("znchartokronecker");
    1188         847 :   s = zncharisodd(G, chi)? -1: 1;
    1189         847 :   if (typ(chi) != t_COL) chi = znconreylog(G, chi);
    1190         847 :   o = zncharorder(G, chi);
    1191         847 :   if (abscmpiu(o,2) > 0) { set_avma(av); return gen_0; }
    1192         581 :   F = znconreyconductor(G, chi, NULL);
    1193         581 :   if (typ(F) == t_INT)
    1194             :   {
    1195         469 :     if (s < 0) F = negi(F);
    1196         469 :     return gerepileuptoint(av, F);
    1197             :   }
    1198         112 :   F = gel(F,1);
    1199         112 :   F = (s < 0)? negi(F): icopy(F);
    1200         112 :   if (!flag)
    1201             :   {
    1202          49 :     GEN MF = znstar_get_faN(G), P = gel(MF,1);
    1203          49 :     long i, l = lg(P);
    1204         140 :     for (i = 1; i < l; i++)
    1205             :     {
    1206          91 :       GEN p = gel(P,i);
    1207          91 :       if (!dvdii(F,p)) F = mulii(F,sqri(p));
    1208             :     }
    1209             :   }
    1210         112 :   return gerepileuptoint(av, F);
    1211             : }
    1212             : 
    1213             : /* (D/.) as a character mod N; assume |D| divides N and D = 0,1 mod 4*/
    1214             : GEN
    1215      303142 : znchar_quad(GEN G, GEN D)
    1216             : {
    1217      303142 :   GEN cyc = znstar_get_conreycyc(G);
    1218      303142 :   GEN gen = znstar_get_conreygen(G);
    1219      303142 :   long i, l = lg(cyc);
    1220      303142 :   GEN chi = cgetg(l, t_COL);
    1221     1351203 :   for (i = 1; i < l; i++)
    1222             :   {
    1223     1048061 :     long k = kronecker(D, gel(gen,i));
    1224     1048061 :     gel(chi,i) = (k==1)? gen_0: shifti(gel(cyc,i), -1);
    1225             :   }
    1226      303142 :   return chi;
    1227             : }
    1228             : 
    1229             : GEN
    1230        3178 : znchar(GEN D)
    1231             : {
    1232        3178 :   pari_sp av = avma;
    1233             :   GEN G, chi;
    1234        3178 :   switch(typ(D))
    1235             :   {
    1236        2436 :     case t_INT:
    1237        2436 :       if (!signe(D) || Mod4(D) > 1) pari_err_TYPE("znchar", D);
    1238        2415 :       G = znstar0(D,1);
    1239        2415 :       chi = mkvec2(G, znchar_quad(G,D));
    1240        2415 :       break;
    1241         672 :     case t_INTMOD:
    1242         672 :       G = znstar0(gel(D,1), 1);
    1243         672 :       chi = mkvec2(G, znconreylog(G, gel(D,2)));
    1244         672 :       break;
    1245          56 :     case t_VEC:
    1246          56 :       if (checkMF_i(D)) { chi = vecslice(MF_get_CHI(D),1,2); break; }
    1247          49 :       else if (checkmf_i(D)) { chi = vecslice(mf_get_CHI(D),1,2); break; }
    1248          42 :       if (lg(D) != 3) pari_err_TYPE("znchar", D);
    1249          35 :       G = gel(D,1);
    1250          35 :       if (!checkznstar_i(G)) pari_err_TYPE("znchar", D);
    1251          28 :       chi = gel(D,2);
    1252          28 :       if (typ(chi) == t_VEC && lg(chi) == 3 && is_vec_t(typ(gel(chi,2))))
    1253             :       { /* normalized character */
    1254           7 :         GEN n = gel(chi,1), chic = gel(chi,2);
    1255           7 :         GEN cyc = typ(chic)==t_VEC? znstar_get_cyc(G): znstar_get_conreycyc(G);
    1256           7 :         if (!char_check(cyc, chic)) pari_err_TYPE("znchar",D);
    1257           7 :         chi = char_denormalize(cyc, n, chic);
    1258             :       }
    1259          28 :       if (!zncharcheck(G, chi)) pari_err_TYPE("znchar", D);
    1260          21 :       chi = mkvec2(G,chi); break;
    1261          14 :     default:
    1262          14 :       pari_err_TYPE("znchar", D);
    1263             :       return NULL; /*LCOV_EXCL_LINE*/
    1264             :   }
    1265        3122 :   return gerepilecopy(av, chi);
    1266             : }
    1267             : 
    1268             : /* G a znstar, not stack clean */
    1269             : GEN
    1270      892038 : znchareval(GEN G, GEN chi, GEN n, GEN z)
    1271             : {
    1272      892038 :   GEN nchi, N = znstar_get_N(G);
    1273             :   /* avoid division by 0 */
    1274      892038 :   if (typ(n) == t_FRAC && !equali1(gcdii(gel(n,2), N))) return not_coprime(z);
    1275      892031 :   n = Rg_to_Fp(n, N);
    1276      892031 :   if (!equali1(gcdii(n, N))) return not_coprime(z);
    1277             :   /* nchi: normalized character on Conrey generators */
    1278      890197 :   nchi = znconrey_normalized(G, chi);
    1279      890197 :   return chareval_i(nchi, znconreylog(G,n), z);
    1280             : }
    1281             : 
    1282             : /* G is a znstar, chi a Dirichlet character */
    1283             : GEN
    1284        1120 : zncharconj(GEN G, GEN chi)
    1285             : {
    1286        1120 :   switch(typ(chi))
    1287             :   {
    1288           7 :     case t_INT: chi = znconreylog(G, chi); /* fall through */
    1289         259 :     case t_COL: return charconj(znstar_get_conreycyc(G), chi);
    1290         861 :     case t_VEC: return charconj(znstar_get_cyc(G), chi);
    1291             :   }
    1292           0 :   pari_err_TYPE("zncharconj",chi);
    1293             :   return NULL; /*LCOV_EXCL_LINE*/
    1294             : }
    1295             : 
    1296             : /* G is a znstar, chi a Dirichlet character */
    1297             : GEN
    1298      375235 : zncharorder(GEN G,  GEN chi)
    1299             : {
    1300      375235 :   switch(typ(chi))
    1301             :   {
    1302          21 :     case t_INT: chi = znconreylog(G, chi); /*fall through*/
    1303      374059 :     case t_COL: return charorder(znstar_get_conreycyc(G), chi);
    1304        1176 :     case t_VEC: return charorder(znstar_get_cyc(G), chi);
    1305           0 :     default: pari_err_TYPE("zncharorder",chi);
    1306             :              return NULL; /* LCOV_EXCL_LINE */
    1307             :   }
    1308             : }
    1309             : 
    1310             : /* G is a znstar, chi a Dirichlet character */
    1311             : GEN
    1312          21 : zncharker(GEN G, GEN chi)
    1313             : {
    1314          21 :   if (typ(chi) != t_VEC) chi = znconreychar(G, chi);
    1315          21 :   return charker(znstar_get_cyc(G), chi);
    1316             : }
    1317             : 
    1318             : /* G is a znstar, 'a' is a Dirichlet character */
    1319             : GEN
    1320         189 : zncharpow(GEN G, GEN a, GEN n)
    1321             : {
    1322         189 :   switch(typ(a))
    1323             :   {
    1324          21 :     case t_INT: return Fp_pow(a, n, znstar_get_N(G));
    1325          21 :     case t_VEC: return charpow(znstar_get_cyc(G), a, n);
    1326         147 :     case t_COL: return charpow(znstar_get_conreycyc(G), a, n);
    1327           0 :     default: pari_err_TYPE("znchapow",a);
    1328             :              return NULL; /* LCOV_EXCL_LINE */
    1329             :   }
    1330             : }
    1331             : /* G is a znstar, 'a' and 'b' are Dirichlet character */
    1332             : GEN
    1333      301847 : zncharmul(GEN G, GEN a, GEN b)
    1334             : {
    1335      301847 :   long ta = typ(a), tb = typ(b);
    1336      301847 :   if (ta == tb) switch(ta)
    1337             :   {
    1338           7 :     case t_INT: return Fp_mul(a, b, znstar_get_N(G));
    1339           7 :     case t_VEC: return charmul(znstar_get_cyc(G), a, b);
    1340      301812 :     case t_COL: return charmul(znstar_get_conreycyc(G), a, b);
    1341           0 :     default: pari_err_TYPE("zncharmul",a);
    1342             :              return NULL; /* LCOV_EXCL_LINE */
    1343             :   }
    1344          21 :   if (ta != t_COL) a = znconreylog(G, a);
    1345          21 :   if (tb != t_COL) b = znconreylog(G, b);
    1346          21 :   return charmul(znstar_get_conreycyc(G), a, b);
    1347             : }
    1348             : 
    1349             : /* G is a znstar, 'a' and 'b' are Dirichlet character */
    1350             : GEN
    1351        5054 : znchardiv(GEN G, GEN a, GEN b)
    1352             : {
    1353        5054 :   long ta = typ(a), tb = typ(b);
    1354        5054 :   if (ta == tb) switch(ta)
    1355             :   {
    1356           7 :     case t_INT: return Fp_div(a, b, znstar_get_N(G));
    1357           7 :     case t_VEC: return chardiv(znstar_get_cyc(G), a, b);
    1358        5019 :     case t_COL: return chardiv(znstar_get_conreycyc(G), a, b);
    1359           0 :     default: pari_err_TYPE("znchardiv",a);
    1360             :              return NULL; /* LCOV_EXCL_LINE */
    1361             :   }
    1362          21 :   if (ta != t_COL) a = znconreylog(G, a);
    1363          21 :   if (tb != t_COL) b = znconreylog(G, b);
    1364          21 :   return chardiv(znstar_get_conreycyc(G), a, b);
    1365             : }
    1366             : 
    1367             : /* CHI mod N = \prod_p p^e; let CHI = \prod CHI_p, CHI_p mod p^e
    1368             :  * return \prod_{p | (Q,N)} CHI_p. E.g if Q = p, return chi_p */
    1369             : GEN
    1370         784 : znchardecompose(GEN G, GEN chi, GEN Q)
    1371             : {
    1372             :   GEN c, P, E, F;
    1373             :   long l, lP, i;
    1374             : 
    1375         784 :   if (!checkznstar_i(G)) pari_err_TYPE("znchardecompose", G);
    1376         784 :   if (typ(Q) != t_INT) pari_err_TYPE("znchardecompose", Q);
    1377         784 :   if (typ(chi) == t_COL)
    1378         560 :   { if (!zncharcheck(G, chi)) pari_err_TYPE("znchardecompose", chi); }
    1379             :   else
    1380         224 :     chi = znconreylog(G, chi);
    1381         784 :   l = lg(chi);
    1382         784 :   F = znstar_get_faN(G);
    1383         784 :   c = zerocol(l-1);
    1384         784 :   P = gel(F,1); /* prime divisors of N */
    1385         784 :   lP = lg(P);
    1386         784 :   E = gel(F,2); /* exponents */
    1387        2471 :   for (i = 1; i < lP; i++)
    1388             :   {
    1389        1687 :     GEN p = gel(P,i);
    1390        1687 :     if (i == 1 && equaliu(p,2) && E[1] >= 3)
    1391             :     {
    1392         567 :       if (!mpodd(Q))
    1393             :       {
    1394         203 :         gel(c,1) = icopy(gel(chi,1));
    1395         203 :         gel(c,2) = icopy(gel(chi,2));
    1396             :       }
    1397         567 :       i = 2; /* skip P[2] = P[1] = 2 */
    1398             :     }
    1399             :     else
    1400        1120 :       if (dvdii(Q, p)) gel(c,i) = icopy(gel(chi,i));
    1401             :   }
    1402         784 :   return c;
    1403             : }
    1404             : 
    1405             : GEN
    1406        1078 : zncharconductor(GEN G, GEN chi)
    1407             : {
    1408        1078 :   pari_sp av = avma;
    1409        1078 :   GEN F = znconreyconductor(G, chi, NULL);
    1410        1078 :   if (typ(F) == t_INT) return F;
    1411         217 :   return gerepilecopy(av, gel(F,1));
    1412             : }
    1413             : GEN
    1414        1253 : znchartoprimitive(GEN G, GEN chi)
    1415             : {
    1416        1253 :   pari_sp av = avma;
    1417        1253 :   GEN chi0, F = znconreyconductor(G, chi, &chi0);
    1418        1253 :   if (typ(F) == t_INT)
    1419        1008 :     chi = mkvec2(G,chi);
    1420             :   else
    1421         245 :     chi = mkvec2(znstar0(F,1), chi0);
    1422        1253 :   return gerepilecopy(av, chi);
    1423             : }

Generated by: LCOV version 1.13