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; 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 : #include "pari.h"
15 : #include "paripriv.h"
16 :
17 : /*********************************************************************/
18 : /** **/
19 : /** GENERIC ABELIAN CHARACTERS **/
20 : /** **/
21 : /*********************************************************************/
22 : /* check whether G is a znstar */
23 : int
24 3365865 : checkznstar_i(GEN G)
25 : {
26 3365706 : return (typ(G) == t_VEC && lg(G) == 6
27 3365432 : && typ(znstar_get_N(G)) == t_INT
28 3365426 : && typ(znstar_get_faN(G)) == t_VEC
29 6731571 : && typ(gel(G,1)) == t_VEC && lg(gel(G,1)) == 3);
30 : }
31 :
32 : int
33 103513 : char_check(GEN cyc, GEN chi)
34 103513 : { return typ(chi) == t_VEC && lg(chi) == lg(cyc) && RgV_is_ZV(chi); }
35 :
36 : /* Shallow; return [ d[1], d[1]/d[2],...,d[1]/d[n] ] */
37 : GEN
38 212366 : cyc_normalize(GEN d)
39 : {
40 212366 : long i, l = lg(d);
41 : GEN C, D;
42 212366 : if (l == 1) return mkvec(gen_1);
43 212348 : D = cgetg(l, t_VEC); gel(D,1) = C = gel(d,1);
44 495821 : for (i = 2; i < l; i++) gel(D,i) = diviiexact(C, gel(d,i));
45 212348 : return D;
46 : }
47 :
48 : /* chi character [D,C] given by chi(g_i) = \zeta_D^C[i] for all i, return
49 : * [d,c] such that chi(g_i) = \zeta_d^c[i] for all i and d minimal */
50 : GEN
51 242775 : char_simplify(GEN D, GEN C)
52 : {
53 242775 : GEN d = D;
54 242775 : if (lg(C) == 1) d = gen_1;
55 : else
56 : {
57 242295 : GEN t = gcdii(d, ZV_content(C));
58 242295 : if (!equali1(t))
59 : {
60 166261 : long tc = typ(C);
61 166261 : C = ZC_Z_divexact(C, t); settyp(C, tc);
62 166261 : d = diviiexact(d, t);
63 : }
64 : }
65 242775 : return mkvec2(d,C);
66 : }
67 :
68 : /* Shallow; ncyc from cyc_normalize(): ncyc[1] = cyc[1],
69 : * ncyc[i] = cyc[i]/cyc[1] for i > 1; chi character on G ~ cyc.
70 : * Return [d,c] such that: chi( g_i ) = e(chi[i] / cyc[i]) = e(c[i]/ d) */
71 : GEN
72 241542 : char_normalize(GEN chi, GEN ncyc)
73 : {
74 241542 : long i, l = lg(chi);
75 241542 : GEN c = cgetg(l, t_VEC);
76 241542 : if (l > 1) {
77 241524 : gel(c,1) = gel(chi,1);
78 597901 : for (i = 2; i < l; i++) gel(c,i) = mulii(gel(chi,i), gel(ncyc,i));
79 : }
80 241542 : return char_simplify(gel(ncyc,1), c);
81 : }
82 :
83 : /* \chi(gen[i]) = zeta_D^chic[i])
84 : * denormalize: express chi(gen[i]) in terms of zeta_{cyc[i]} */
85 : GEN
86 179069 : char_denormalize(GEN cyc, GEN D, GEN chic)
87 : {
88 179069 : long i, l = lg(chic);
89 179069 : GEN chi = cgetg(l, t_VEC);
90 : /* \chi(gen[i]) = e(chic[i] / D) = e(chi[i] / cyc[i])
91 : * hence chi[i] = chic[i]cyc[i]/ D mod cyc[i] */
92 683574 : for (i = 1; i < l; ++i)
93 : {
94 504505 : GEN di = gel(cyc, i), t = diviiexact(mulii(di, gel(chic,i)), D);
95 504505 : gel(chi, i) = modii(t, di);
96 : }
97 179069 : return chi;
98 : }
99 :
100 : /* Called by function 's'. x is a group object affording ".cyc" method, and
101 : * chi an abelian character. Return NULL if the group is (Z/nZ)^* [special
102 : * case more character types allowed] and x.cyc otherwise */
103 : static GEN
104 437 : get_cyc(GEN x, GEN chi, const char *s)
105 : {
106 437 : switch(nftyp(x))
107 : {
108 365 : case typ_BIDZ:
109 365 : if (!zncharcheck(x, chi)) pari_err_TYPE(s, chi);
110 365 : return NULL;
111 0 : case typ_GCHAR:
112 0 : x = gchar_get_cyc(x);
113 0 : if (!is_vec_t(typ(chi)) || lg(chi) != lg(x) || !RgV_is_ZV(chi))
114 0 : pari_err_TYPE(s, chi); /* FIXME: handle norm component */
115 0 : return x;
116 72 : default:
117 72 : if (typ(x) != t_VEC || !RgV_is_ZV(x)) x = member_cyc(x);
118 72 : if (!char_check(x, chi)) pari_err_TYPE(s, chi);
119 72 : return x;
120 : }
121 : }
122 :
123 : /* conjugate character [ZV/ZC] */
124 : GEN
125 5622 : charconj(GEN cyc, GEN chi)
126 : {
127 : long i, l;
128 5622 : GEN z = cgetg_copy(chi, &l);
129 10070 : for (i = 1; i < l; i++)
130 : {
131 4448 : GEN c = gel(chi,i);
132 4448 : gel(z,i) = signe(c)? subii(gel(cyc,i), c): gen_0;
133 : }
134 5622 : return z;
135 : }
136 : GEN
137 24 : charconj0(GEN x, GEN chi)
138 : {
139 24 : GEN cyc = get_cyc(x, chi, "charconj");
140 24 : return cyc? charconj(cyc, chi): zncharconj(x, chi);
141 : }
142 :
143 : GEN
144 1189824 : charorder(GEN cyc, GEN x)
145 : {
146 1189824 : pari_sp av = avma;
147 1189824 : long i, l = lg(cyc);
148 1189824 : GEN f = gen_1;
149 3107750 : for (i = 1; i < l; i++)
150 1917926 : if (signe(gel(x,i)))
151 : {
152 1097108 : GEN c, o = gel(cyc,i);
153 1097108 : if (!signe(o))
154 0 : return gc_upto(av,mkoo());
155 1097108 : c = gcdii(o, gel(x,i));
156 1097108 : if (!is_pm1(c)) o = diviiexact(o,c);
157 1097108 : f = lcmii(f, o);
158 : }
159 1189824 : return gc_INT(av, f);
160 : }
161 : GEN
162 177 : charorder0(GEN x, GEN chi)
163 : {
164 177 : GEN cyc = get_cyc(x, chi, "charorder");
165 177 : return cyc? charorder(cyc, chi): zncharorder(x, chi);
166 : }
167 :
168 : /* chi character of abelian G: chi[i] = chi(z_i), where G = \oplus Z/cyc[i] z_i.
169 : * Return Ker chi */
170 : GEN
171 81992 : charker(GEN cyc, GEN chi)
172 : {
173 81992 : long i, l = lg(cyc);
174 : GEN nchi, ncyc, m, U;
175 :
176 81992 : if (l == 1) return cgetg(1,t_MAT); /* trivial subgroup */
177 81950 : ncyc = cyc_normalize(cyc);
178 81950 : nchi = char_normalize(chi, ncyc);
179 81950 : m = shallowconcat(gel(nchi,2), gel(nchi,1));
180 81950 : U = gel(ZV_extgcd(m), 2); setlg(U,l);
181 219970 : for (i = 1; i < l; i++) setlg(U[i], l);
182 81950 : return hnfmodid(U, cyc);
183 : }
184 : GEN
185 30 : charker0(GEN x, GEN chi)
186 : {
187 30 : GEN cyc = get_cyc(x, chi, "charker");
188 30 : return cyc? charker(cyc, chi): zncharker(x, chi);
189 : }
190 :
191 : GEN
192 174 : charpow(GEN cyc, GEN a, GEN N)
193 : {
194 : long i, l;
195 174 : GEN v = cgetg_copy(a, &l);
196 312 : for (i = 1; i < l; i++) gel(v,i) = Fp_mul(gel(a,i), N, gel(cyc,i));
197 174 : return v;
198 : }
199 : GEN
200 258962 : charmul(GEN cyc, GEN a, GEN b)
201 : {
202 : long i, l;
203 258962 : GEN v = cgetg_copy(a, &l);
204 1157786 : for (i = 1; i < l; i++) gel(v,i) = Fp_add(gel(a,i), gel(b,i), gel(cyc,i));
205 258962 : return v;
206 : }
207 : GEN
208 8754 : chardiv(GEN cyc, GEN a, GEN b)
209 : {
210 : long i, l;
211 8754 : GEN v = cgetg_copy(a, &l);
212 17616 : for (i = 1; i < l; i++) gel(v,i) = Fp_sub(gel(a,i), gel(b,i), gel(cyc,i));
213 8754 : return v;
214 : }
215 : GEN
216 54 : charpow0(GEN x, GEN a, GEN N)
217 : {
218 54 : GEN cyc = get_cyc(x, a, "charpow");
219 54 : return cyc? charpow(cyc, a, N): zncharpow(x, a, N);
220 : }
221 : GEN
222 116 : charmul0(GEN x, GEN a, GEN b)
223 : {
224 116 : const char *s = "charmul";
225 116 : GEN cyc = get_cyc(x, a, s);
226 116 : if (!cyc)
227 : {
228 116 : if (!zncharcheck(x, b)) pari_err_TYPE(s, b);
229 116 : return zncharmul(x, a, b);
230 : }
231 : else
232 : {
233 0 : if (!char_check(cyc, b)) pari_err_TYPE(s, b);
234 0 : return charmul(cyc, a, b);
235 : }
236 : }
237 : GEN
238 36 : chardiv0(GEN x, GEN a, GEN b)
239 : {
240 36 : const char *s = "chardiv";
241 36 : GEN cyc = get_cyc(x, a, s);
242 36 : if (!cyc)
243 : {
244 36 : if (!zncharcheck(x, b)) pari_err_TYPE(s, b);
245 36 : return znchardiv(x, a, b);
246 : }
247 : else
248 : {
249 0 : if (!char_check(cyc, b)) pari_err_TYPE(s, b);
250 0 : return chardiv(cyc, a, b);
251 : }
252 : }
253 :
254 : static GEN
255 2201923 : chareval_i(GEN nchi, GEN dlog, GEN z)
256 : {
257 2201923 : GEN o, q, r, b = gel(nchi,1);
258 2201923 : GEN a = FpV_dotproduct(gel(nchi,2), dlog, b);
259 : /* image is a/b in Q/Z */
260 2201923 : if (!z) return gdiv(a,b);
261 2201648 : if (typ(z) == t_INT)
262 : {
263 2191870 : q = dvmdii(z, b, &r);
264 2191870 : if (signe(r)) pari_err_TYPE("chareval", z);
265 2191870 : return mulii(a, q);
266 : }
267 : /* return z^(a*o/b), assuming z^o = 1 and b | o */
268 9778 : if (typ(z) != t_VEC || lg(z) != 3) pari_err_TYPE("chareval", z);
269 9778 : o = gel(z,2); if (typ(o) != t_INT) pari_err_TYPE("chareval", z);
270 9778 : q = dvmdii(o, b, &r); if (signe(r)) pari_err_TYPE("chareval", z);
271 9778 : q = mulii(a, q); /* in [0, o[ since a is reduced mod b */
272 9778 : z = gel(z,1);
273 9778 : if (typ(z) == t_VEC)
274 : {
275 8653 : if (itos_or_0(o) != lg(z)-1) pari_err_TYPE("chareval", z);
276 8653 : return gcopy(gel(z, itos(q)+1));
277 : }
278 : else
279 1125 : return gpow(z, q, DEFAULTPREC);
280 : }
281 :
282 : static GEN
283 1585 : not_coprime(GEN z)
284 1585 : { return (!z || typ(z) == t_INT)? gen_m1: gen_0; }
285 :
286 : static GEN
287 30 : get_chi(GEN cyc, GEN chi)
288 : {
289 30 : if (!char_check(cyc,chi)) pari_err_TYPE("chareval", chi);
290 30 : return char_normalize(chi, cyc_normalize(cyc));
291 : }
292 : /* G a bnr. FIXME: horribly inefficient to check that (x,N)=1, what to do ? */
293 : static int
294 36 : bnr_coprime(GEN G, GEN x)
295 : {
296 36 : GEN t, N = gel(bnr_get_mod(G), 1);
297 36 : if (typ(x) == t_INT) /* shortcut */
298 : {
299 12 : t = gcdii(gcoeff(N,1,1), x);
300 12 : if (equali1(t)) return 1;
301 0 : t = idealadd(G, N, x);
302 0 : return equali1(gcoeff(t,1,1));
303 : }
304 24 : x = idealnumden(G, x);
305 24 : t = idealadd(G, N, gel(x,1));
306 24 : if (!equali1(gcoeff(t,1,1))) return 0;
307 18 : t = idealadd(G, N, gel(x,2));
308 18 : return equali1(gcoeff(t,1,1));
309 : }
310 : GEN
311 3027 : chareval(GEN G, GEN chi, GEN x, GEN z)
312 : {
313 3027 : pari_sp av = avma;
314 : GEN nchi, L;
315 :
316 3027 : switch(nftyp(G))
317 : {
318 36 : case typ_BNR:
319 36 : if (!bnr_coprime(G, x)) return not_coprime(z);
320 24 : L = isprincipalray(G, x);
321 24 : nchi = get_chi(bnr_get_cyc(G), chi);
322 24 : break;
323 6 : case typ_BNF:
324 6 : L = isprincipal(G, x);
325 6 : nchi = get_chi(bnf_get_cyc(G), chi);
326 6 : break;
327 2973 : case typ_BIDZ:
328 2973 : if (checkznstar_i(G)) return gc_upto(av, znchareval(G, chi, x, z));
329 : /* don't implement chars on general bid: need an nf... */
330 : case typ_GCHAR:
331 6 : pari_err_TYPE("chareval [use gchareval to evaluate a grossencharacter]", G);
332 6 : default:
333 6 : pari_err_TYPE("chareval", G);
334 : return NULL;/* LCOV_EXCL_LINE */
335 : }
336 30 : return gc_upto(av, chareval_i(nchi, L, z));
337 : }
338 :
339 : /* nchi = [ord,D] a quasi-normalized character (ord may be a multiple of
340 : * the character order); return v such that v[n] = -1 if (n,N) > 1 else
341 : * chi(n) = e(v[n]/ord), 1 <= n <= N */
342 : GEN
343 49266 : ncharvecexpo(GEN G, GEN nchi)
344 : {
345 49266 : long N = itou(znstar_get_N(G)), ord = itou(gel(nchi,1)), i, j, l;
346 : GEN cyc, gen, d, t, t1, t2, t3, e, u, u1, u2, u3;
347 49266 : GEN D = gel(nchi,2), v = const_vecsmall(N,-1);
348 49266 : pari_sp av = avma;
349 49266 : if (typ(D) == t_COL) {
350 49266 : cyc = znstar_get_conreycyc(G);
351 49266 : gen = znstar_get_conreygen(G);
352 : } else {
353 0 : cyc = znstar_get_cyc(G);
354 0 : gen = znstar_get_gen(G);
355 : }
356 49266 : l = lg(cyc);
357 49266 : e = u = cgetg(N+1,t_VECSMALL);
358 49266 : d = t = cgetg(N+1,t_VECSMALL);
359 49266 : *++d = 1;
360 49266 : *++e = 0; v[*d] = *e;
361 94212 : for (i = 1; i < l; i++)
362 : {
363 44946 : ulong g = itou(gel(gen,i)), c = itou(gel(cyc,i)), x = itou(gel(D,i));
364 750824 : for (t1=t,u1=u,j=c-1; j; j--,t1=t2,u1=u2)
365 1507270 : for (t2=d,u2=e, t3=t1,u3=u1; t3<t2; )
366 : {
367 801392 : *++d = Fl_mul(*++t3, g, N);
368 801392 : *++e = Fl_add(*++u3, x, ord); v[*d] = *e;
369 : }
370 : }
371 49266 : set_avma(av); return v;
372 : }
373 :
374 : /*****************************************************************************/
375 :
376 : static ulong
377 210876 : lcmuu(ulong a, ulong b) { return (a/ugcd(a,b)) * b; }
378 : static ulong
379 83484 : zv_charorder(GEN cyc, GEN x)
380 : {
381 83484 : long i, l = lg(cyc);
382 83484 : ulong f = 1;
383 272102 : for (i = 1; i < l; i++)
384 188618 : if (x[i])
385 : {
386 127392 : ulong o = cyc[i];
387 127392 : f = lcmuu(f, o / ugcd(o, x[i]));
388 : }
389 83484 : return f;
390 : }
391 :
392 : /* N > 0 */
393 : GEN
394 471067 : coprimes_zv(ulong N)
395 : {
396 471067 : GEN v = const_vecsmall(N,1);
397 471067 : pari_sp av = avma;
398 471067 : GEN P = gel(factoru(N),1);
399 471067 : long i, l = lg(P);
400 1098350 : for (i = 1; i < l; i++)
401 : {
402 627283 : ulong p = P[i], j;
403 2910318 : for (j = p; j <= N; j += p) v[j] = 0;
404 : }
405 471067 : set_avma(av); return v;
406 : }
407 : /* cf zv_cyc_minimal: return k such that g*k is minimal (wrt lex) */
408 : long
409 39966 : zv_cyc_minimize(GEN cyc, GEN g, GEN coprime)
410 : {
411 39966 : pari_sp av = avma;
412 39966 : long d, k, e, i, maxi, k0, bestk, l = lg(g), o = lg(coprime)-1;
413 : GEN best, gk, gd;
414 : ulong t;
415 39966 : if (o == 1) return 1;
416 46446 : for (i = 1; i < l; i++)
417 46446 : if (g[i]) break;
418 39966 : if (g[i] == 1) return 1;
419 32934 : k0 = Fl_invgen(g[i], cyc[i], &t);
420 32934 : d = cyc[i] / (long)t;
421 32934 : if (k0 > 1) g = vecmoduu(Flv_Fl_mul(g, k0, cyc[i]), cyc);
422 43530 : for (i++; i < l; i++)
423 38358 : if (g[i]) break;
424 32934 : if (i == l) return k0;
425 27762 : cyc = vecslice(cyc,i,l-1);
426 27762 : g = vecslice(g, i,l-1);
427 27762 : e = cyc[1];
428 27762 : gd = Flv_Fl_mul(g, d, e);
429 27762 : bestk = 1; best = g; maxi = e/ugcd(d,e);
430 41694 : for (gk = g, k = d+1, i = 1; i < maxi; k += d, i++)
431 : {
432 13932 : long ko = k % o;
433 13932 : gk = Flv_add(gk, gd, e); if (!ko || !coprime[ko]) continue;
434 6306 : gk = vecmoduu(gk, cyc);
435 6306 : if (vecsmall_lexcmp(gk, best) < 0) { best = gk; bestk = k; }
436 : }
437 27762 : return gc_long(av, bestk == 1? k0: (long) Fl_mul(k0, bestk, o));
438 : }
439 : /* g of order o in abelian group G attached to cyc. Is g a minimal generator
440 : * [wrt lex order] of the cyclic subgroup it generates;
441 : * coprime = coprimes_zv(o) */
442 : long
443 83164 : zv_cyc_minimal(GEN cyc, GEN g, GEN coprime)
444 : {
445 83164 : pari_sp av = avma;
446 83164 : long i, maxi, d, k, e, l = lg(g), o = lg(coprime)-1; /* elt order */
447 : GEN gd, gk;
448 83164 : if (o == 1) return 1;
449 87881 : for (k = 1; k < l; k++)
450 87881 : if (g[k]) break;
451 83164 : if (g[k] == 1) return 1;
452 66017 : if (cyc[k] % g[k]) return 0;
453 66017 : d = cyc[k] / g[k]; /* > 1 */
454 80171 : for (k++; k < l; k++) /* skip following 0s */
455 80171 : if (g[k]) break;
456 66017 : if (k == l) return 1;
457 66017 : cyc = vecslice(cyc,k,l-1);
458 66017 : g = vecslice(g, k,l-1);
459 66017 : e = cyc[1];
460 : /* find k in (Z/e)^* such that g*k mod cyc is lexicographically minimal,
461 : * k = 1 mod d to fix the first nonzero entry */
462 66017 : gd = Flv_Fl_mul(g, d, e); maxi = e/ugcd(d,e);
463 111542 : for (gk = g, k = d+1, i = 1; i < maxi; i++, k += d)
464 : {
465 53280 : long ko = k % o;
466 53280 : gk = Flv_add(gk, gd, e); if (!coprime[ko]) continue;
467 27798 : gk = vecmoduu(gk, cyc);
468 27798 : if (vecsmall_lexcmp(gk, g) < 0) return gc_long(av,0);
469 : }
470 58262 : return gc_long(av,1);
471 : }
472 :
473 : static GEN
474 6817 : coprime_tables(long N)
475 : {
476 6817 : GEN D = divisorsu(N), v = const_vec(N, NULL);
477 6817 : long i, l = lg(D);
478 40327 : for (i = 1; i < l; i++) gel(v, D[i]) = coprimes_zv(D[i]);
479 6817 : return v;
480 : }
481 : /* enumerate all group elements, modulo (Z/cyc[1])^* */
482 : static GEN
483 6837 : cyc2elts_normal(GEN cyc, long maxord, GEN ORD)
484 : {
485 6837 : long i, n, o, N, j = 1;
486 : GEN z, vcoprime;
487 :
488 6837 : if (typ(cyc) != t_VECSMALL) cyc = vec_to_vecsmall(cyc);
489 6837 : n = lg(cyc)-1;
490 6837 : N = zv_prod(cyc);
491 6837 : z = cgetg(N+1, t_VEC);
492 6837 : if (1 <= maxord && (!ORD|| zv_search(ORD,1)))
493 6510 : gel(z,j++) = zero_zv(n);
494 6837 : if (n == 0) { setlg(z, j); return z; }
495 6817 : vcoprime = coprime_tables(cyc[1]);
496 19731 : for (i = n; i > 0; i--)
497 : {
498 12914 : GEN cyc0 = vecslice(cyc,i+1,n), pre = zero_zv(i);
499 12914 : GEN D = divisorsu(cyc[i]), C = cyc2elts(cyc0);
500 12914 : long s, t, lD = lg(D), nC = lg(C)-1; /* remove last element */
501 46535 : for (s = 1; s < lD-1; s++)
502 : {
503 33621 : long o0 = D[lD-s]; /* cyc[i] / D[s] */
504 33621 : if (o0 > maxord) continue;
505 32358 : pre[i] = D[s];
506 32358 : if (!ORD || zv_search(ORD,o0))
507 : {
508 32125 : GEN c = vecsmall_concat(pre, zero_zv(n-i));
509 32125 : gel(z,j++) = c;
510 : }
511 115842 : for (t = 1; t < nC; t++)
512 : {
513 83484 : GEN chi0 = gel(C,t);
514 83484 : o = lcmuu(o0, zv_charorder(cyc0,chi0));
515 83484 : if (o <= maxord && (!ORD || zv_search(ORD,o)))
516 : {
517 83164 : GEN c = vecsmall_concat(pre, chi0);
518 83164 : if (zv_cyc_minimal(cyc, c, gel(vcoprime,o))) gel(z,j++) = c;
519 : }
520 : }
521 : }
522 : }
523 6817 : setlg(z,j); return z;
524 : }
525 :
526 : GEN
527 8935 : chargalois(GEN G, GEN ORD)
528 : {
529 8935 : pari_sp av = avma;
530 : long maxord, i, l;
531 8935 : GEN v, cyc = (typ(G) == t_VEC && RgV_is_ZVpos(G))? G: member_cyc(G);
532 8935 : if (lg(cyc) == 1 && !ORD) retmkvec(cgetg(1,t_VEC));
533 6842 : maxord = itou(cyc_get_expo(cyc));
534 6842 : if (ORD)
535 368 : switch(typ(ORD))
536 : {
537 : long l;
538 30 : case t_VEC:
539 30 : ORD = ZV_to_zv(ORD);
540 342 : case t_VECSMALL:
541 342 : l = lg(ORD);
542 342 : if (l > 2)
543 : {
544 317 : ORD = leafcopy(ORD);
545 317 : vecsmall_sort(ORD);
546 : }
547 342 : if (l == 1) retgc_const(av, cgetg(1, t_VEC));
548 337 : maxord = minss(maxord, ORD[l-1]);
549 337 : break;
550 26 : case t_INT:
551 26 : maxord = minss(maxord, itos(ORD));
552 26 : ORD = NULL;
553 26 : break;
554 0 : default: pari_err_TYPE("chargalois", ORD);
555 : }
556 6837 : v = cyc2elts_normal(cyc, maxord, ORD); l = lg(v);
557 120881 : for(i = 1; i < l; i++) gel(v,i) = zv_to_ZV(gel(v,i));
558 6837 : return gc_upto(av, v);
559 : }
560 :
561 : /*********************************************************************/
562 : /** **/
563 : /** (Z/NZ)^* AND DIRICHLET CHARACTERS **/
564 : /** **/
565 : /*********************************************************************/
566 :
567 : GEN
568 112507 : znstar0(GEN N, long flag)
569 : {
570 112507 : GEN F = NULL, P, E, cyc, gen, mod, G;
571 : long i, i0, l, nbprimes;
572 112507 : pari_sp av = avma;
573 :
574 112507 : if (flag && flag != 1) pari_err_FLAG("znstar");
575 112507 : if ((F = check_arith_all(N,"znstar")))
576 : {
577 8596 : F = clean_Z_factor(F);
578 8596 : N = typ(N) == t_VEC? gel(N,1): factorback(F);
579 : }
580 112507 : if (!signe(N))
581 : {
582 15 : if (flag) pari_err_IMPL("znstar(0,1)");
583 10 : set_avma(av);
584 10 : retmkvec3(gen_2, mkvec(gen_2), mkvec(gen_m1));
585 : }
586 112492 : N = absi_shallow(N);
587 112492 : if (abscmpiu(N,2) <= 0)
588 : {
589 9172 : G = mkvec3(gen_1, cgetg(1,t_VEC), cgetg(1,t_VEC));
590 9172 : if (flag)
591 : {
592 9113 : GEN v = const_vec(6,cgetg(1,t_VEC));
593 9113 : gel(v,3) = cgetg(1,t_MAT);
594 18198 : F = equali1(N)? mkvec2(cgetg(1,t_COL),cgetg(1,t_VECSMALL))
595 9113 : : mkvec2(mkcol(gen_2), mkvecsmall(1));
596 9113 : G = mkvec5(mkvec2(N,mkvec(gen_0)), G, F, v, cgetg(1,t_MAT));
597 : }
598 9172 : return gc_GEN(av,G);
599 : }
600 103320 : if (!F) F = Z_factor(N);
601 103320 : P = gel(F,1); nbprimes = lg(P)-1;
602 103320 : E = ZV_to_nv( gel(F,2) );
603 103320 : switch(mod8(N))
604 : {
605 17443 : case 0:
606 17443 : P = shallowconcat(gen_2,P);
607 17443 : E = vecsmall_prepend(E, E[1]); /* add a copy of p=2 row */
608 17443 : i = 2; /* 2 generators at 2 */
609 17443 : break;
610 16562 : case 4:
611 16562 : i = 1; /* 1 generator at 2 */
612 16562 : break;
613 6012 : case 2: case 6:
614 6012 : P = vecsplice(P,1);
615 6012 : E = vecsplice(E,1); /* remove 2 */
616 6012 : i = 0; /* no generator at 2 */
617 6012 : break;
618 63303 : default:
619 63303 : i = 0; /* no generator at 2 */
620 63303 : break;
621 : }
622 103320 : l = lg(P);
623 103320 : cyc = cgetg(l,t_VEC);
624 103320 : gen = cgetg(l,t_VEC);
625 103320 : mod = cgetg(l,t_VEC);
626 : /* treat p=2 first */
627 103320 : if (i == 2)
628 : {
629 17443 : long v2 = E[1];
630 17443 : GEN q = int2n(v2);
631 17443 : gel(cyc,1) = gen_2;
632 17443 : gel(gen,1) = subiu(q,1); /* -1 */
633 17443 : gel(mod,1) = q;
634 17443 : gel(cyc,2) = int2n(v2-2);
635 17443 : gel(gen,2) = utoipos(5); /* Conrey normalization */
636 17443 : gel(mod,2) = q;
637 17443 : i0 = 3;
638 : }
639 85877 : else if (i == 1)
640 : {
641 16562 : gel(cyc,1) = gen_2;
642 16562 : gel(gen,1) = utoipos(3);
643 16562 : gel(mod,1) = utoipos(4);
644 16562 : i0 = 2;
645 : }
646 : else
647 69315 : i0 = 1;
648 : /* odd primes, fill remaining entries */
649 249714 : for (i = i0; i < l; i++)
650 : {
651 146394 : long e = E[i];
652 146394 : GEN p = gel(P,i), q = powiu(p, e-1), Q = mulii(p, q);
653 146394 : gel(cyc,i) = subii(Q, q); /* phi(p^e) */
654 146394 : gel(gen,i) = pgener_Zp(p);/* Conrey normalization, for e = 1 also */
655 146394 : gel(mod,i) = Q;
656 : }
657 : /* gen[i] has order cyc[i] and generates (Z/mod[i]Z)^* */
658 103320 : if (nbprimes > 1) /* lift generators to (Z/NZ)^*, = 1 mod N/mod[i] */
659 209388 : for (i=1; i<l; i++)
660 : {
661 150759 : GEN Q = gel(mod,i), g = gel(gen,i), qinv = Fp_inv(Q, diviiexact(N,Q));
662 150759 : g = addii(g, mulii(mulii(subsi(1,g),qinv),Q));
663 150759 : gel(gen,i) = modii(g, N);
664 : }
665 :
666 : /* cyc[i] > 1 and remain so in the loop, gen[i] = 1 mod (N/mod[i]) */
667 103320 : if (!flag)
668 : { /* update generators in place; about twice faster */
669 30699 : G = gen;
670 30890 : for (i=l-1; i>=2; i--)
671 : {
672 191 : GEN ci = gel(cyc,i), gi = gel(G,i);
673 : long j;
674 457 : for (j=i-1; j>=1; j--) /* we want cyc[i] | cyc[j] */
675 : {
676 266 : GEN cj = gel(cyc,j), gj, qj, v, d;
677 :
678 266 : d = bezout(ci,cj,NULL,&v); /* > 1 */
679 402 : if (absequalii(ci, d)) continue; /* ci | cj */
680 161 : if (absequalii(cj, d)) { /* cj | ci */
681 136 : swap(gel(G,j),gel(G,i));
682 136 : gi = gel(G,i);
683 136 : swap(gel(cyc,j),gel(cyc,i));
684 136 : ci = gel(cyc,i); continue;
685 : }
686 :
687 25 : qj = diviiexact(cj,d);
688 25 : gel(cyc,j) = mulii(ci,qj);
689 25 : gel(cyc,i) = d;
690 :
691 : /* [1,v*cj/d; 0,1]*[1,0;-1,1]*diag(cj,ci)*[ci/d,-v; cj/d,u]
692 : * = diag(lcm,gcd), with u ci + v cj = d */
693 25 : gj = gel(G,j);
694 : /* (gj, gi) *= [1,0; -1,1]^-1 */
695 25 : gj = Fp_mul(gj, gi, N); /* order ci*qj = lcm(ci,cj) */
696 : /* (gj,gi) *= [1,v*qj; 0,1]^-1 */
697 25 : togglesign_safe(&v);
698 25 : if (signe(v) < 0) v = modii(v,ci); /* >= 0 to avoid inversions */
699 25 : gel(G,i) = gi = Fp_mul(gi, Fp_pow(gj, mulii(qj, v), N), N);
700 25 : gel(G,j) = gj;
701 25 : ci = d; if (absequaliu(ci, 2)) break;
702 : }
703 : }
704 30699 : G = mkvec3(ZV_prod(cyc), cyc, FpV_to_mod(G,N));
705 : }
706 : else
707 : { /* keep matrices between generators, return an 'init' structure */
708 72621 : GEN D, U, Ui, fao = cgetg(l, t_VEC), lo = cgetg(l, t_VEC);
709 72621 : F = mkvec2(P, E);
710 72621 : D = ZV_snf_group(cyc,&U,&Ui);
711 239573 : for (i = 1; i < l; i++)
712 : {
713 166952 : GEN t = gen_0, p = gel(P,i), p_1 = subiu(p,1);
714 166952 : long e = E[i];
715 166952 : gel(fao,i) = get_arith_ZZM(p_1);
716 166952 : if (e >= 2 && !absequaliu(p,2))
717 : {
718 11084 : GEN q = gel(mod,i), g = Fp_pow(gel(gen,i),p_1,q);
719 11084 : if (e == 2)
720 9050 : t = Fp_inv(diviiexact(subiu(g,1), p), p);
721 : else
722 2034 : t = ginv(Qp_log(cvtop(g,p,e)));
723 : }
724 166952 : gel(lo,i) = t;
725 : }
726 72621 : G = cgetg(l, t_VEC);
727 239573 : for (i = 1; i < l; i++) gel(G,i) = FpV_factorback(gen, gel(Ui,i), N);
728 72621 : G = mkvec3(ZV_prod(D), D, G);
729 72621 : G = mkvec5(mkvec2(N,mkvec(gen_0)), G, F,
730 : mkvecn(6,mod,fao,Ui,gen,cyc,lo), U);
731 : }
732 103320 : return gc_GEN(av, G);
733 : }
734 : GEN
735 30700 : znstar(GEN N) { return znstar0(N, 0); }
736 :
737 : /* g has order 2^(e-2), g,h = 1 (mod 4); return x s.t. g^x = h (mod 2^e) */
738 : static GEN
739 813750 : Zideallog_2k(GEN h, GEN g, long e, GEN pe)
740 : {
741 813750 : GEN a = Fp_log(h, g, int2n(e-2), pe);
742 813750 : if (typ(a) != t_INT) return NULL;
743 813750 : return a;
744 : }
745 :
746 : /* ord = get_arith_ZZM(p-1), simplified form of znlog_rec: g is known
747 : * to be a primitive root mod p^e; lo = 1/log_p(g^(p-1)) */
748 : static GEN
749 1755556 : Zideallog_pk(GEN h, GEN g, GEN p, long e, GEN pe, GEN ord, GEN lo)
750 : {
751 1755556 : GEN gp = (e == 1)? g: modii(g, p);
752 1755556 : GEN hp = (e == 1)? h: modii(h, p);
753 1755556 : GEN a = Fp_log(hp, gp, ord, p);
754 1755556 : if (typ(a) != t_INT) return NULL;
755 1755550 : if (e > 1)
756 : { /* find a s.t. g^a = h (mod p^e), p odd prime, e > 0, (h,p) = 1 */
757 : /* use p-adic log: O(log p + e) mul*/
758 45667 : GEN b, p_1 = gel(ord,1);
759 45667 : h = Fp_mul(h, Fp_pow(g, negi(a), pe), pe);
760 : /* g,h = 1 mod p; compute b s.t. h = g^b */
761 45667 : if (e == 2) /* simpler */
762 39315 : b = Fp_mul(diviiexact(subiu(h,1), p), lo, p);
763 : else
764 6352 : b = padic_to_Q(gmul(Qp_log(cvtop(h, p, e)), lo));
765 45667 : a = addii(a, mulii(p_1, b));
766 : }
767 1755550 : return a;
768 : }
769 :
770 : int
771 783796 : znconrey_check(GEN cyc, GEN chi)
772 783796 : { return typ(chi) == t_COL && lg(chi) == lg(cyc) && RgV_is_ZV(chi); }
773 :
774 : int
775 181250 : zncharcheck(GEN G, GEN chi)
776 : {
777 181250 : switch(typ(chi))
778 : {
779 701 : case t_INT: return 1;
780 173248 : case t_COL: return znconrey_check(znstar_get_conreycyc(G), chi);
781 7301 : case t_VEC: return char_check(znstar_get_cyc(G), chi);
782 : }
783 0 : return 0;
784 : }
785 :
786 : GEN
787 128538 : znconreyfromchar_normalized(GEN bid, GEN chi)
788 : {
789 128538 : GEN nchi, U = znstar_get_U(bid);
790 128538 : long l = lg(chi);
791 128538 : if (l == 1) retmkvec2(gen_1,cgetg(1,t_VEC));
792 126440 : if (!RgV_is_ZV(chi) || lgcols(U) != l) pari_err_TYPE("lfunchiZ", chi);
793 126434 : nchi = char_normalize(chi, cyc_normalize(znstar_get_cyc(bid)));
794 126434 : gel(nchi,2) = ZV_ZM_mul(gel(nchi,2),U); return nchi;
795 : }
796 :
797 : GEN
798 119845 : znconreyfromchar(GEN bid, GEN chi)
799 : {
800 119845 : GEN nchi = znconreyfromchar_normalized(bid, chi);
801 119839 : GEN v = char_denormalize(znstar_get_conreycyc(bid), gel(nchi,1), gel(nchi,2));
802 119839 : settyp(v, t_COL); return v;
803 : }
804 :
805 : /* discrete log on canonical "primitive root" generators
806 : * Allow log(x) instead of x [usual discrete log on bid's generators] */
807 : GEN
808 2272507 : znconreylog(GEN bid, GEN x)
809 : {
810 2272507 : pari_sp av = avma;
811 : GEN N, L, F, P,E, y, pe, fao, gen, lo, cycg;
812 : long i, l;
813 2272507 : if (!checkznstar_i(bid)) pari_err_TYPE("znconreylog", bid);
814 2272501 : N = znstar_get_N(bid);
815 2272501 : if (abscmpiu(N, 2) <= 0)
816 : {
817 10624 : switch(typ(x))
818 : {
819 2289 : case t_INT: break;
820 5 : case t_INTMOD:
821 5 : if (!equalii(N, gel(x,1))) pari_err_TYPE("znconreylog", x);
822 0 : x = gel(x,2); break;
823 8325 : case t_COL:
824 : case t_VEC:
825 8325 : if (lg(x) != 1) pari_err_TYPE("znconreylog", x);
826 8315 : break;
827 5 : default: pari_err_TYPE("znconreylog", x);
828 : }
829 10604 : return cgetg(1, t_COL);
830 : }
831 2261877 : cycg = znstar_get_conreycyc(bid);
832 2261877 : switch(typ(x))
833 : {
834 : GEN Ui;
835 0 : case t_INTMOD:
836 0 : if (!equalii(N, gel(x,1))) pari_err_TYPE("znconreylog", x);
837 0 : x = gel(x,2); /* fall through */
838 2235291 : case t_INT:
839 2235291 : if (!signe(x)) pari_err_COPRIME("znconreylog", x, N);
840 2235285 : break;
841 29 : case t_COL: /* log_bid(x) */
842 29 : Ui = znstar_get_Ui(bid);
843 29 : if (!RgV_is_ZV(x) || lg(x) != lg(Ui)) pari_err_TYPE("znconreylog", x);
844 29 : return gc_upto(av, ZV_ZV_mod(ZM_ZC_mul(Ui,x), cycg));
845 26557 : case t_VEC:
846 26557 : return gc_GEN(av, znconreyfromchar(bid, x));
847 0 : default: pari_err_TYPE("znconreylog", x);
848 : }
849 2235285 : F = znstar_get_faN(bid); /* factor(N) */
850 2235285 : P = gel(F, 1); /* prime divisors of N */
851 2235285 : E = gel(F, 2); /* exponents */
852 2235285 : L = gel(bid,4);
853 2235285 : pe = znstar_get_pe(bid);
854 2235285 : fao = gel(L,2);
855 2235285 : gen = znstar_get_conreygen(bid); /* local generators of (Z/p^k)^* */
856 2235285 : lo = gel(L,6); /* 1/log_p((g_i)^(p_i-1)) */
857 :
858 2235285 : l = lg(gen); i = 1;
859 2235285 : y = cgetg(l, t_COL);
860 2235285 : if (!mod2(N) && !mod2(x)) pari_err_COPRIME("znconreylog", x, N);
861 2235274 : if (absequaliu(gel(P,1), 2) && E[1] >= 2)
862 : {
863 1079619 : if (E[1] == 2)
864 265869 : gel(y,i++) = mod4(x) == 1? gen_0: gen_1;
865 : else
866 : {
867 813750 : GEN a, x2, q2 = gel(pe,1);
868 813750 : x2 = modii(x, q2);
869 813750 : if (mod4(x) == 1) /* 1 or 5 mod 8*/
870 507668 : gel(y,i++) = gen_0;
871 : else /* 3 or 7 */
872 306082 : { gel(y,i++) = gen_1; x2 = subii(q2, x2); }
873 : /* x2 = 5^x mod q */
874 813750 : a = Zideallog_2k(x2, gel(gen,i), E[1], q2);
875 813750 : if (!a) pari_err_COPRIME("znconreylog", x, N);
876 813750 : gel(y, i++) = a;
877 : }
878 : }
879 3990824 : while (i < l)
880 : {
881 1755556 : GEN p = gel(P,i), q = gel(pe,i), xpe = modii(x, q);
882 1755556 : GEN a = Zideallog_pk(xpe, gel(gen,i), p, E[i], q, gel(fao,i), gel(lo,i));
883 1755556 : if (!a) pari_err_COPRIME("znconreylog", x, N);
884 1755550 : gel(y, i++) = a;
885 : }
886 2235268 : return gc_GEN(av, y);
887 : }
888 : GEN
889 19708 : Zideallog(GEN bid, GEN x)
890 : {
891 19708 : pari_sp av = avma;
892 19708 : GEN y = znconreylog(bid, x), U = znstar_get_U(bid);
893 19684 : return gc_upto(av, ZM_ZC_mul(U, y));
894 : }
895 : GEN
896 216 : znlog0(GEN h, GEN g, GEN o)
897 : {
898 216 : if (typ(g) == t_VEC)
899 : {
900 : GEN N;
901 45 : if (o) pari_err_TYPE("znlog [with znstar]", o);
902 45 : if (!checkznstar_i(g)) pari_err_TYPE("znlog", g);
903 45 : N = znstar_get_N(g);
904 45 : h = Rg_to_Fp(h,N);
905 40 : return Zideallog(g, h);
906 : }
907 171 : return znlog(h, g, o);
908 : }
909 :
910 : GEN
911 223513 : znconreyexp(GEN bid, GEN x)
912 : {
913 223513 : pari_sp av = avma;
914 : long i, l;
915 : GEN N, pe, gen, cycg, v, vmod;
916 : int e2;
917 223513 : if (!checkznstar_i(bid)) pari_err_TYPE("znconreyexp", bid);
918 223513 : cycg = znstar_get_conreycyc(bid);
919 223513 : switch(typ(x))
920 : {
921 17 : case t_VEC:
922 17 : x = znconreylog(bid, x);
923 17 : break;
924 223496 : case t_COL:
925 223496 : if (RgV_is_ZV(x) && lg(x) == lg(cycg)) break;
926 5 : default: pari_err_TYPE("znconreyexp",x);
927 : }
928 223508 : pe = znstar_get_pe(bid);
929 223508 : gen = znstar_get_conreygen(bid); /* local generators of (Z/p^k)^* */
930 223508 : cycg = znstar_get_conreycyc(bid);
931 223508 : l = lg(x); v = cgetg(l, t_VEC);
932 223508 : N = znstar_get_N(bid);
933 223508 : e2 = !mod8(N); /* 2 generators at p = 2 */
934 690504 : for (i = 1; i < l; i++)
935 : {
936 : GEN q, g, m;
937 466996 : if (i == 1 && e2) { gel(v,1) = NULL; continue; }
938 439349 : q = gel(pe,i);
939 439349 : g = gel(gen,i);
940 439349 : m = modii(gel(x,i), gel(cycg,i));
941 439349 : m = Fp_pow(g, m, q);
942 439349 : if (i == 2 && e2 && signe(gel(x,1))) m = Fp_neg(m, q);
943 439349 : gel(v,i) = mkintmod(m, q);
944 : }
945 223508 : if (e2) v = vecsplice(v, 1);
946 223508 : v = chinese1_coprime_Z(v);
947 223508 : vmod = gel(v,1);
948 223508 : v = gel(v,2);
949 223508 : if (mpodd(v) || mpodd(N)) return gc_GEN(av, v);
950 : /* handle N = 2 mod 4 */
951 197 : return gc_INT(av, addii(v, vmod));
952 : }
953 :
954 : /* Return Dirichlet character \chi_q(m,.), where bid = znstar(q);
955 : * m is either a t_INT, or a t_COL [Conrey logarithm] */
956 : GEN
957 40068 : znconreychar(GEN bid, GEN m)
958 : {
959 40068 : pari_sp av = avma;
960 : GEN c, d, nchi;
961 :
962 40068 : if (!checkznstar_i(bid)) pari_err_TYPE("znconreychar", bid);
963 40063 : switch(typ(m))
964 : {
965 0 : case t_INTMOD:
966 0 : if (!equalii(gel(m,1), znstar_get_N(bid)))
967 0 : pari_err_TYPE("znconreychar",m);
968 0 : m = gel(m,2); /* fall through */
969 40063 : case t_INT:
970 : case t_COL:
971 40063 : nchi = znconrey_normalized(bid,m); /* images of primroot gens */
972 40058 : break;
973 0 : default:
974 0 : pari_err_TYPE("znconreychar",m);
975 : return NULL;/*LCOV_EXCL_LINE*/
976 : }
977 40058 : d = gel(nchi,1);
978 40058 : c = ZV_ZM_mul(gel(nchi,2), znstar_get_Ui(bid)); /* images of bid gens */
979 40058 : return gc_GEN(av, char_denormalize(znstar_get_cyc(bid),d,c));
980 : }
981 :
982 : /* chi a t_INT or Conrey log describing a character. Return conductor, as an
983 : * integer if primitive; as a t_VEC [N,factor(N)] if not. Set *pm=m to the
984 : * attached primitive character: chi(g_i) = m[i]/ord(g_i)
985 : * Caller should use znconreylog_normalize(BID, m), once BID(conductor) is
986 : * computed (wasteful to do it here since BID is shared by many characters) */
987 : GEN
988 633966 : znconreyconductor(GEN bid, GEN chi, GEN *pm)
989 : {
990 633966 : pari_sp av = avma;
991 : GEN q, m, F, P, E;
992 : long i, j, l;
993 633966 : int e2, primitive = 1;
994 :
995 633966 : if (!checkznstar_i(bid)) pari_err_TYPE("znconreyconductor", bid);
996 633966 : if (typ(chi) == t_COL)
997 : {
998 610548 : if (!znconrey_check(znstar_get_conreycyc(bid), chi))
999 0 : pari_err_TYPE("znconreyconductor",chi);
1000 : }
1001 : else
1002 23418 : chi = znconreylog(bid, chi);
1003 633960 : l = lg(chi);
1004 633960 : F = znstar_get_faN(bid);
1005 633960 : P = gel(F,1);
1006 633960 : E = gel(F,2);
1007 633960 : if (l == 1)
1008 : {
1009 91787 : set_avma(av);
1010 91787 : if (pm) *pm = cgetg(1,t_COL);
1011 91787 : if (lg(P) == 1) return gen_1;
1012 16 : retmkvec2(gen_1, trivial_fact());
1013 : }
1014 542173 : P = leafcopy(P);
1015 542173 : E = leafcopy(E);
1016 542173 : m = cgetg(l, t_COL);
1017 542173 : e2 = (E[1] >= 3 && absequaliu(gel(P,1),2));
1018 542173 : i = j = 1;
1019 542173 : if (e2)
1020 : { /* two generators at p=2 */
1021 245334 : GEN a1 = gel(chi,1), a = gel(chi,2);
1022 245334 : i = 3;
1023 245334 : if (!signe(a))
1024 : {
1025 83945 : e2 = primitive = 0;
1026 83945 : if (signe(a1))
1027 : { /* lose one generator */
1028 38964 : E[1] = 2;
1029 38964 : gel(m,1) = a1;
1030 38964 : j = 2;
1031 : }
1032 : /* else lose both */
1033 : }
1034 : else
1035 : {
1036 161389 : long v = Z_pvalrem(a, gen_2, &a);
1037 161389 : if (v) { E[1] -= v; E[2] = E[1]; primitive = 0; }
1038 161389 : gel(m,1) = a1;
1039 161389 : gel(m,2) = a;
1040 161389 : j = 3;
1041 : }
1042 : }
1043 542173 : l = lg(P);
1044 1562900 : for (; i < l; i++)
1045 : {
1046 1020727 : GEN p = gel(P,i), a = gel(chi,i);
1047 : /* image of g_i in Q/Z is a/cycg[i], cycg[i] = order(g_i) */
1048 1020727 : if (!signe(a)) primitive = 0;
1049 : else
1050 : {
1051 799892 : long v = Z_pvalrem(a, p, &a);
1052 799892 : E[j] = E[i]; if (v) { E[j] -= v; primitive = 0; }
1053 799892 : gel(P,j) = gel(P,i);
1054 799892 : gel(m,j) = a; j++;
1055 : }
1056 : }
1057 542173 : setlg(m,j);
1058 542173 : setlg(P,j);
1059 542173 : setlg(E,j);
1060 542173 : if (pm) *pm = m; /* attached primitive character */
1061 542173 : if (primitive)
1062 : {
1063 255946 : q = znstar_get_N(bid);
1064 255946 : if (mod4(q) == 2) primitive = 0;
1065 : }
1066 542173 : if (!primitive)
1067 : {
1068 286892 : if (e2)
1069 : { /* remove duplicate p=2 row from factorization */
1070 98326 : P = vecsplice(P,1);
1071 98326 : E = vecsplice(E,1);
1072 : }
1073 286892 : E = zc_to_ZC(E);
1074 286892 : q = mkvec2(factorback2(P,E), mkmat2(P,E));
1075 : }
1076 542173 : return gc_all(av, pm? 2: 1, &q, pm);
1077 : }
1078 :
1079 : GEN
1080 10753 : zncharinduce(GEN G, GEN chi, GEN N)
1081 : {
1082 10753 : pari_sp av = avma;
1083 : GEN q, faq, P, E, Pq, Eq, CHI;
1084 : long i, j, l;
1085 : int e2;
1086 :
1087 10753 : if (!checkznstar_i(G)) pari_err_TYPE("zncharinduce", G);
1088 10753 : if (!zncharcheck(G, chi)) pari_err_TYPE("zncharinduce", chi);
1089 10753 : q = znstar_get_N(G);
1090 10753 : if (typ(chi) != t_COL) chi = znconreylog(G, chi);
1091 10753 : if (checkznstar_i(N))
1092 : {
1093 10618 : GEN faN = znstar_get_faN(N);
1094 10618 : P = gel(faN,1); l = lg(P);
1095 10618 : E = gel(faN,2);
1096 10618 : N = znstar_get_N(N);
1097 10618 : if (l > 2 && equalii(gel(P,1),gel(P,2)))
1098 : { /* remove duplicate 2 */
1099 2198 : l--;
1100 2198 : P = vecsplice(P,1);
1101 2198 : E = vecsplice(E,1);
1102 : }
1103 : }
1104 : else
1105 : {
1106 135 : GEN faN = check_arith_pos(N, "zncharinduce");
1107 135 : if (!faN) faN = Z_factor(N);
1108 : else
1109 0 : N = (typ(N) == t_VEC)? gel(N,1): factorback(faN);
1110 135 : P = gel(faN,1);
1111 135 : E = gel(faN,2);
1112 : }
1113 10753 : if (!dvdii(N,q)) pari_err_DOMAIN("zncharinduce", "N % q", "!=", gen_0, N);
1114 10748 : if (mod4(N) == 2)
1115 : { /* remove 2 */
1116 66 : if (lg(P) > 1 && absequaliu(gel(P,1), 2))
1117 : {
1118 32 : P = vecsplice(P,1);
1119 32 : E = vecsplice(E,1);
1120 : }
1121 66 : N = shifti(N,-1);
1122 : }
1123 10748 : l = lg(P);
1124 : /* q = N or q = 2N, N odd */
1125 10748 : if (cmpii(N,q) <= 0) return gc_GEN(av, chi);
1126 : /* N > 1 => l > 1*/
1127 10650 : if (typ(E) != t_VECSMALL) E = ZV_to_zv(E);
1128 10650 : e2 = (E[1] >= 3 && absequaliu(gel(P,1),2)); /* 2 generators at 2 mod N */
1129 10650 : if (ZV_equal0(chi))
1130 : {
1131 8086 : set_avma(av);
1132 8086 : return equali1(N)? cgetg(1, t_COL): zerocol(l+e2 - 1);
1133 : }
1134 :
1135 2564 : faq = znstar_get_faN(G);
1136 2564 : Pq = gel(faq,1);
1137 2564 : Eq = gel(faq,2);
1138 2564 : CHI = cgetg(l+e2, t_COL);
1139 2564 : i = j = 1;
1140 2564 : if (e2)
1141 : {
1142 986 : i = 2; j = 3;
1143 986 : if (absequaliu(gel(Pq,1), 2))
1144 : {
1145 846 : if (Eq[1] >= 3)
1146 : { /* 2 generators at 2 mod q */
1147 464 : gel(CHI,1) = gel(chi,1);
1148 464 : gel(CHI,2) = shifti(gel(chi,2), E[1]-Eq[1]);
1149 : }
1150 382 : else if (Eq[1] == 2)
1151 : { /* 1 generator at 2 mod q */
1152 382 : gel(CHI,1) = gel(chi,1);
1153 382 : gel(CHI,2) = gen_0;
1154 : }
1155 : else
1156 0 : gel(CHI,1) = gel(CHI,2) = gen_0;
1157 : }
1158 : else
1159 140 : gel(CHI,1) = gel(CHI,2) = gen_0;
1160 : }
1161 6628 : for (; i < l; i++,j++)
1162 : {
1163 4064 : GEN p = gel(P,i);
1164 4064 : long k = ZV_search(Pq, p);
1165 4064 : gel(CHI,j) = k? mulii(gel(chi,k), powiu(p, E[i]-Eq[k])): gen_0;
1166 : }
1167 2564 : return gc_GEN(av, CHI);
1168 : }
1169 :
1170 : /* m a Conrey log [on the canonical primitive roots], cycg the primitive
1171 : * roots orders */
1172 : GEN
1173 2282104 : znconreylog_normalize(GEN G, GEN m)
1174 : {
1175 2282104 : GEN cycg = znstar_get_conreycyc(G);
1176 : long i, l;
1177 2282104 : GEN d, M = cgetg_copy(m, &l);
1178 2282104 : if (typ(cycg) != t_VEC || lg(cycg) != l)
1179 0 : pari_err_TYPE("znconreylog_normalize",mkvec2(m,cycg));
1180 6007608 : for (i = 1; i < l; i++) gel(M,i) = gdiv(gel(m,i), gel(cycg,i));
1181 : /* m[i]: image of primroot generators g_i in Q/Z */
1182 2282104 : M = Q_remove_denom(M, &d);
1183 2282104 : return mkvec2(d? d: gen_1, M);
1184 : }
1185 :
1186 : /* return normalized character on Conrey generators attached to chi: Conrey
1187 : * label (t_INT), char on (SNF) G.gen* (t_VEC), or Conrey log (t_COL) */
1188 : GEN
1189 2276084 : znconrey_normalized(GEN G, GEN chi)
1190 : {
1191 2276084 : switch(typ(chi))
1192 : {
1193 301 : case t_INT: /* Conrey label */
1194 301 : return znconreylog_normalize(G, znconreylog(G, chi));
1195 2267090 : case t_COL: /* Conrey log */
1196 2267090 : if (!RgV_is_ZV(chi)) break;
1197 2267090 : return znconreylog_normalize(G, chi);
1198 8693 : case t_VEC: /* char on G.gen */
1199 8693 : if (!RgV_is_ZV(chi)) break;
1200 8693 : return znconreyfromchar_normalized(G, chi);
1201 : }
1202 0 : pari_err_TYPE("znchareval",chi);
1203 : return NULL;/* LCOV_EXCL_LINE */
1204 : }
1205 :
1206 : /* return 1 iff chi(-1) = -1, and 0 otherwise */
1207 : long
1208 169476 : zncharisodd(GEN G, GEN chi)
1209 : {
1210 : long i, l, s;
1211 : GEN N;
1212 169476 : if (!checkznstar_i(G)) pari_err_TYPE("zncharisodd", G);
1213 169476 : if (!zncharcheck(G, chi)) pari_err_TYPE("zncharisodd", chi);
1214 169476 : if (typ(chi) != t_COL) chi = znconreylog(G, chi);
1215 169476 : N = znstar_get_N(G);
1216 169476 : l = lg(chi);
1217 169476 : s = 0;
1218 169476 : if (!mod8(N))
1219 : {
1220 78318 : s = mpodd(gel(chi,1));
1221 78318 : i = 3;
1222 : }
1223 : else
1224 91158 : i = 1;
1225 461110 : for (; i < l; i++) s += mpodd(gel(chi,i));
1226 169476 : return odd(s);
1227 : }
1228 :
1229 : GEN
1230 726 : znchartokronecker(GEN G, GEN chi, long flag)
1231 : {
1232 726 : pari_sp av = avma;
1233 : long s;
1234 : GEN F, o;
1235 :
1236 726 : if (flag && flag != 1) pari_err_FLAG("znchartokronecker");
1237 726 : s = zncharisodd(G, chi)? -1: 1;
1238 726 : if (typ(chi) != t_COL) chi = znconreylog(G, chi);
1239 726 : o = zncharorder(G, chi);
1240 726 : if (abscmpiu(o,2) > 0) { set_avma(av); return gen_0; }
1241 498 : F = znconreyconductor(G, chi, NULL);
1242 498 : if (typ(F) == t_INT)
1243 : {
1244 402 : if (s < 0) F = negi(F);
1245 402 : return gc_INT(av, F);
1246 : }
1247 96 : F = gel(F,1);
1248 96 : F = (s < 0)? negi(F): icopy(F);
1249 96 : if (!flag)
1250 : {
1251 42 : GEN MF = znstar_get_faN(G), P = gel(MF,1);
1252 42 : long i, l = lg(P);
1253 120 : for (i = 1; i < l; i++)
1254 : {
1255 78 : GEN p = gel(P,i);
1256 78 : if (!dvdii(F,p)) F = mulii(F,sqri(p));
1257 : }
1258 : }
1259 96 : return gc_INT(av, F);
1260 : }
1261 :
1262 : /* (D/.) as a character mod N; assume |D| divides N and D = 0,1 mod 4*/
1263 : GEN
1264 260115 : znchar_quad(GEN G, GEN D)
1265 : {
1266 260115 : GEN cyc = znstar_get_conreycyc(G);
1267 260115 : GEN gen = znstar_get_conreygen(G);
1268 260115 : long i, l = lg(cyc);
1269 260115 : GEN chi = cgetg(l, t_COL);
1270 1159020 : for (i = 1; i < l; i++)
1271 : {
1272 898905 : long k = kronecker(D, gel(gen,i));
1273 898905 : gel(chi,i) = (k==1)? gen_0: shifti(gel(cyc,i), -1);
1274 : }
1275 260115 : return chi;
1276 : }
1277 :
1278 : GEN
1279 2851 : znchar(GEN D)
1280 : {
1281 2851 : pari_sp av = avma;
1282 : GEN G, chi;
1283 2851 : switch(typ(D))
1284 : {
1285 2175 : case t_INT:
1286 2175 : if (!signe(D) || Mod4(D) > 1) pari_err_DOMAIN("znstar","disc % 4",">", gen_1,D);
1287 2157 : G = znstar0(D,1);
1288 2157 : chi = mkvec2(G, znchar_quad(G,D));
1289 2157 : break;
1290 616 : case t_INTMOD:
1291 616 : G = znstar0(gel(D,1), 1);
1292 616 : chi = mkvec2(G, znconreylog(G, gel(D,2)));
1293 616 : break;
1294 48 : case t_VEC:
1295 48 : if (checkMF_i(D)) { chi = vecslice(MF_get_CHI(D),1,2); break; }
1296 42 : else if (checkmf_i(D)) { chi = vecslice(mf_get_CHI(D),1,2); break; }
1297 36 : if (lg(D) != 3) pari_err_TYPE("znchar", D);
1298 30 : G = gel(D,1);
1299 30 : if (!checkznstar_i(G)) pari_err_TYPE("znchar", D);
1300 24 : chi = gel(D,2);
1301 24 : if (typ(chi) == t_VEC && lg(chi) == 3 && is_vec_t(typ(gel(chi,2))))
1302 : { /* normalized character */
1303 6 : GEN n = gel(chi,1), chic = gel(chi,2);
1304 6 : GEN cyc = typ(chic)==t_VEC? znstar_get_cyc(G): znstar_get_conreycyc(G);
1305 6 : if (!char_check(cyc, chic)) pari_err_TYPE("znchar",D);
1306 6 : chi = char_denormalize(cyc, n, chic);
1307 : }
1308 24 : if (!zncharcheck(G, chi)) pari_err_TYPE("znchar", D);
1309 18 : chi = mkvec2(G,chi); break;
1310 12 : default:
1311 12 : pari_err_TYPE("znchar", D);
1312 : return NULL; /*LCOV_EXCL_LINE*/
1313 : }
1314 2803 : return gc_GEN(av, chi);
1315 : }
1316 :
1317 : /* G a znstar, not stack clean */
1318 : GEN
1319 2203466 : znchareval(GEN G, GEN chi, GEN n, GEN z)
1320 : {
1321 2203466 : GEN nchi, N = znstar_get_N(G);
1322 : /* avoid division by 0 */
1323 2203466 : if (typ(n) == t_FRAC && !equali1(gcdii(gel(n,2), N))) return not_coprime(z);
1324 2203461 : n = Rg_to_Fp(n, N);
1325 2203461 : if (!equali1(gcdii(n, N))) return not_coprime(z);
1326 : /* nchi: normalized character on Conrey generators */
1327 2201893 : nchi = znconrey_normalized(G, chi);
1328 2201893 : return chareval_i(nchi, znconreylog(G,n), z);
1329 : }
1330 :
1331 : /* G is a znstar, chi a Dirichlet character */
1332 : GEN
1333 4992 : zncharconj(GEN G, GEN chi)
1334 : {
1335 4992 : switch(typ(chi))
1336 : {
1337 6 : case t_INT: chi = znconreylog(G, chi); /* fall through */
1338 570 : case t_COL: return charconj(znstar_get_conreycyc(G), chi);
1339 4422 : case t_VEC: return charconj(znstar_get_cyc(G), chi);
1340 : }
1341 0 : pari_err_TYPE("zncharconj",chi);
1342 : return NULL; /*LCOV_EXCL_LINE*/
1343 : }
1344 :
1345 : /* G is a znstar, chi a Dirichlet character */
1346 : GEN
1347 337359 : zncharorder(GEN G, GEN chi)
1348 : {
1349 337359 : switch(typ(chi))
1350 : {
1351 17 : case t_INT: chi = znconreylog(G, chi); /*fall through*/
1352 332668 : case t_COL: return charorder(znstar_get_conreycyc(G), chi);
1353 4691 : case t_VEC: return charorder(znstar_get_cyc(G), chi);
1354 0 : default: pari_err_TYPE("zncharorder",chi);
1355 : return NULL; /* LCOV_EXCL_LINE */
1356 : }
1357 : }
1358 :
1359 : /* G is a znstar, chi a Dirichlet character */
1360 : GEN
1361 18 : zncharker(GEN G, GEN chi)
1362 : {
1363 18 : if (typ(chi) != t_VEC) chi = znconreychar(G, chi);
1364 18 : return charker(znstar_get_cyc(G), chi);
1365 : }
1366 :
1367 : /* G is a znstar, 'a' is a Dirichlet character */
1368 : GEN
1369 192 : zncharpow(GEN G, GEN a, GEN n)
1370 : {
1371 192 : switch(typ(a))
1372 : {
1373 18 : case t_INT: return Fp_pow(a, n, znstar_get_N(G));
1374 18 : case t_VEC: return charpow(znstar_get_cyc(G), a, n);
1375 156 : case t_COL: return charpow(znstar_get_conreycyc(G), a, n);
1376 0 : default: pari_err_TYPE("znchapow",a);
1377 : return NULL; /* LCOV_EXCL_LINE */
1378 : }
1379 : }
1380 : /* G is a znstar, 'a' and 'b' are Dirichlet character */
1381 : GEN
1382 258968 : zncharmul(GEN G, GEN a, GEN b)
1383 : {
1384 258968 : long ta = typ(a), tb = typ(b);
1385 258968 : if (ta == tb) switch(ta)
1386 : {
1387 6 : case t_INT: return Fp_mul(a, b, znstar_get_N(G));
1388 6 : case t_VEC: return charmul(znstar_get_cyc(G), a, b);
1389 258938 : case t_COL: return charmul(znstar_get_conreycyc(G), a, b);
1390 0 : default: pari_err_TYPE("zncharmul",a);
1391 : return NULL; /* LCOV_EXCL_LINE */
1392 : }
1393 18 : if (ta != t_COL) a = znconreylog(G, a);
1394 18 : if (tb != t_COL) b = znconreylog(G, b);
1395 18 : return charmul(znstar_get_conreycyc(G), a, b);
1396 : }
1397 :
1398 : /* G is a znstar, 'a' and 'b' are Dirichlet character */
1399 : GEN
1400 8760 : znchardiv(GEN G, GEN a, GEN b)
1401 : {
1402 8760 : long ta = typ(a), tb = typ(b);
1403 8760 : if (ta == tb) switch(ta)
1404 : {
1405 6 : case t_INT: return Fp_div(a, b, znstar_get_N(G));
1406 6 : case t_VEC: return chardiv(znstar_get_cyc(G), a, b);
1407 8730 : case t_COL: return chardiv(znstar_get_conreycyc(G), a, b);
1408 0 : default: pari_err_TYPE("znchardiv",a);
1409 : return NULL; /* LCOV_EXCL_LINE */
1410 : }
1411 18 : if (ta != t_COL) a = znconreylog(G, a);
1412 18 : if (tb != t_COL) b = znconreylog(G, b);
1413 18 : return chardiv(znstar_get_conreycyc(G), a, b);
1414 : }
1415 :
1416 : /* CHI mod N = \prod_p p^e; let CHI = \prod CHI_p, CHI_p mod p^e
1417 : * return \prod_{p | (Q,N)} CHI_p. E.g if Q = p, return chi_p */
1418 : GEN
1419 645 : znchardecompose(GEN G, GEN chi, GEN Q)
1420 : {
1421 : GEN c, P, E, F;
1422 : long l, lP, i;
1423 :
1424 645 : if (!checkznstar_i(G)) pari_err_TYPE("znchardecompose", G);
1425 645 : if (typ(Q) != t_INT) pari_err_TYPE("znchardecompose", Q);
1426 645 : if (typ(chi) == t_COL)
1427 480 : { if (!zncharcheck(G, chi)) pari_err_TYPE("znchardecompose", chi); }
1428 : else
1429 165 : chi = znconreylog(G, chi);
1430 645 : l = lg(chi); if (l == 1) return cgetg(1, t_VEC);
1431 640 : F = znstar_get_faN(G);
1432 640 : c = zerocol(l-1);
1433 640 : P = gel(F,1); /* prime divisors of N */
1434 640 : lP = lg(P);
1435 640 : E = gel(F,2); /* exponents */
1436 2022 : for (i = 1; i < lP; i++)
1437 : {
1438 1382 : GEN p = gel(P,i);
1439 1382 : if (i == 1 && equaliu(p,2) && E[1] >= 3)
1440 : {
1441 454 : if (!mpodd(Q))
1442 : {
1443 158 : gel(c,1) = icopy(gel(chi,1));
1444 158 : gel(c,2) = icopy(gel(chi,2));
1445 : }
1446 454 : i = 2; /* skip P[2] = P[1] = 2 */
1447 : }
1448 : else
1449 928 : if (dvdii(Q, p)) gel(c,i) = icopy(gel(chi,i));
1450 : }
1451 640 : return c;
1452 : }
1453 :
1454 : GEN
1455 18174 : zncharconductor(GEN G, GEN chi)
1456 : {
1457 18174 : pari_sp av = avma;
1458 18174 : GEN F = znconreyconductor(G, chi, NULL);
1459 18174 : if (typ(F) == t_INT) return F;
1460 9248 : return gc_GEN(av, gel(F,1));
1461 : }
1462 : GEN
1463 4731 : znchartoprimitive(GEN G, GEN chi)
1464 : {
1465 4731 : pari_sp av = avma;
1466 4731 : GEN chi0, F = znconreyconductor(G, chi, &chi0);
1467 4731 : if (typ(F) == t_INT)
1468 4546 : chi = mkvec2(G,chi);
1469 : else
1470 185 : chi = mkvec2(znstar0(F,1), chi0);
1471 4731 : return gc_GEN(av, chi);
1472 : }
|
