In addition to znorder and znlog, other functions compute the order of an element or discrete logarithms in a finite abelian group: ellorder and elllog (the rational points on an elliptic curve defined over a finite field), fforder and fflog (the multiplicative group of a finite field), etc.

All such functions allow an optional argument specifying an integer N, representing the order of the group. (The order functions also allows any nonzero multiple of the order, with a minor loss of efficiency.) That optional "order factorization" argument allow the same formats as arithmetic functions:

* t_INT: the integer N,

* t_MAT: the factorization fa = factor(N),

* t_VEC: this is the preferred format and provides both the integer N and its factorization in a two-component vector [N, fa].

When the group is fixed and many orders or discrete logarithms will be computed, it is more efficient to initialize this data once and pass it to the relevant functions, as in

  ? p = nextprime(10^30);
  ? v = [p-1, factor(p-1)]; \\ data for discrete log & order computations
  ? znorder(Mod(2,p), v)
  %3 = 500000000000000000000000000028
  ? g = znprimroot(p);
  ? znlog(2, g, v)
  %5 = 543038070904014908801878611374

* a character on the abelian group ⨁ _j (ℤ/d_jℤ) g_j is given by a row vector χ = [a₁,...,a_n] of integers 0 ≤ a_i < d_i such that χ(g_j) = e(a_j / d_j) for all j, with the standard notation e(x) := exp(2iπ x). In other words, χ(∏_j g_j^n_j) = e(∑_j a_j n_j / d_j).

This will be generalized to more general abelian groups in later sections (Hecke characters), but in the present case of (ℤ/Nℤ)^*, there is a useful alternate convention : namely, it is not necessary to impose the SNF condition and we can use Chinese remainders instead. If N = ∏ p^e_p is the factorization of N into primes, the so-called Conrey generators of G are the generators of the (ℤ/p^e_pℤ)^* lifted to (ℤ/Nℤ)^* by requesting that they be congruent to 1 modulo N/p^e_p (for p odd we take the smallest positive primitive root mod p², and for p = 2 we take -1 if e₂ > 1 and additionally 5 if e₂ > 2). We can again write G = ⨁ _{i ≤ n} (ℤ/D_iℤ) G_i, where again ∏_i D_i = φ(N). These generators don't satisfy the SNF condition in general since their orders are now (p-1)p^e_p-1 for p odd; for p = 2, the generator -1 has order 2 and 5 has order 2^e₂-2 (e₂ > 2). Nevertheless, any m ∈ (ℤ/Nℤ)^* can be uniquely decomposed as m = ∏_j G_i^m_i for some m_i modulo D_i and we can define a character by χ(G_j) = e(m_j / D_j) for all j.

* The column vector of the m_j, 0 ≤ m_j < D_j is called the Conrey logarithm of m (discrete logarithm in terms of the Conrey generators). Note that discrete logarithms in PARI/GP are always expressed as t_COLs.

* The attached character is called the Conrey character attached to m.

To sum up a Dirichlet character can be defined by a t_INTMOD Mod(m, N), a t_INT lift (the Conrey label m), a t_COL (the Conrey logarithm of m, in terms of the Conrey generators) or a t_VEC (in terms of the SNF generators). The t_COL format, i.e. Conrey logarithms, is the preferred (fastest) representation.

Concretely, this works as follows:

G = znstar(N, 1) initializes (ℤ/Nℤ)^*, which must be given as first argument to all functions handling Dirichlet characters.

znconreychar transforms t_INT, t_INTMOD and t_COL to a SNF character.

znconreylog transforms t_INT, t_INTMOD and t_VEC to a Conrey logarithm.

znconreyexp transforms t_VEC and t_COL to a Conrey label.

Also available are charconj, chardiv, charmul, charker, chareval, charorder, zncharinduce, znconreyconductor (also computes the primitive character attached to the input character). The prefix char indicates that the function applies to all characters, the prefix znchar that it is specific to Dirichlet characters (on (ℤ/Nℤ)^*) and the prefix znconrey that it is specific to Conrey representation.

Let cyc represent a finite abelian group by its elementary divisors, i.e. (d_j) represents ∑_{j ≤ k} ℤ/d_jℤ with d_k | ... | d₁; any object which has a .cyc method is also allowed, e.g. the output of znstar or bnrinit. A character on this group is given by a row vector χ = [a₁,...,a_n] such that χ(∏ g_j^n_j) = exp(2π i∑_j a_j n_j / d_j), where g_j denotes the generator (of order d_j) of the j-th cyclic component. This function returns the conjugate character.

  ? cyc = [15,5]; chi = [1,1];
  ? charconj(cyc, chi)
  %2 = [14, 4]
  ? bnf = bnfinit(x^2+23);
  ? bnf.cyc
  %4 = [3]
  ? charconj(bnf, [1])
  %5 = [2]

For Dirichlet characters (when cyc is znstar(q,1)), characters in Conrey representation are available, see Section se:dirichletchar or ??character:

  ? G = znstar(16, 1);  \\ (Z/16Z)*
  ? charconj(G, 3)  \\ Conrey label
  %2 = [1, 1]~
  ? znconreyexp(G, %)
  %3 = 11 \\ attached Conrey label; indeed 11 = 3^(-1) mod 16
  ? chi = znconreylog(G, 3);
  ? charconj(G, chi)  \\ Conrey logarithm
  %5 = [1, 1]~

The library syntax is GEN charconj0(GEN cyc, GEN chi). Also available is GEN charconj(GEN cyc, GEN chi), when cyc is known to be a vector of elementary divisors and chi a compatible character (no checks).

Let cyc represent a finite abelian group by its elementary divisors, i.e. (d_j) represents ∑_{j ≤ k} ℤ/d_jℤ with d_k. | ... | d₁; any object which has a .cyc method is also allowed, e.g. the output of znstar or bnrinit. A character on this group is given by a row vector a = [a₁,...,a_n] such that χ(∏ g_j^n_j) = exp(2π i∑_j a_j n_j / d_j), where g_j denotes the generator (of order d_j) of the j-th cyclic component.

Given two characters a and b, return the character a / b = a b.

  ? cyc = [15,5]; a = [1,1]; b =  [2,4];
  ? chardiv(cyc, a,b)
  %2 = [14, 2]
  ? bnf = bnfinit(x^2+23);
  ? bnf.cyc
  %4 = [3]
  ? chardiv(bnf, [1], [2])
  %5 = [2]

For Dirichlet characters on (ℤ/Nℤ)^*, additional representations are available (Conrey labels, Conrey logarithm), see Section se:dirichletchar or ??character. If the two characters are in the same format, the result is given in the same format, otherwise a Conrey logarithm is used.

  ? G = znstar(100, 1);
  ? G.cyc
  %2 = [20, 2]
  ? a = [10, 1]; \\ usual representation for characters
  ? b = 7; \\ Conrey label;
  ? c = znconreylog(G, 11); \\ Conrey log
  ? chardiv(G, b,b)
  %6 = 1   \\ Conrey label
  ? chardiv(G, a,b)
  %7 = [0, 5]~  \\ Conrey log
  ? chardiv(G, a,c)
  %7 = [0, 14]~   \\ Conrey log

The library syntax is GEN chardiv0(GEN cyc, GEN a, GEN b). Also available is GEN chardiv(GEN cyc, GEN a, GEN b), when cyc is known to be a vector of elementary divisors and a, b are compatible characters (no checks).

Let G be an abelian group structure affording a discrete logarithm method, e.g G = znstar(N, 1) for (ℤ/Nℤ)^* or a bnr structure, let x be an element of G and let chi be a character of G (see the note below for details). This function returns the value of chi at x.

Note on characters. Let K be some field. If G is an abelian group, let χ: G → K^* be a character of finite order and let o be a multiple of the character order such that χ(n) = ζ^c(n) for some fixed ζ ∈ K^* of multiplicative order o and a unique morphism c: G → (ℤ/oℤ,+). Our usual convention is to write G = (ℤ/o₁ℤ) g₁ ⨁ ...⨁ (ℤ/o_dℤ) g_d for some generators (g_i) of respective order d_i, where the group has exponent o := lcm_i o_i. Since ζ^o = 1, the vector (c_i) in ∏_i (ℤ/o_iℤ) defines a character χ on G via χ(g_i) = ζ^{c_i (o/o_i)} for all i. Classical Dirichlet characters have values in K = ℂ and we can take ζ = exp(2iπ/o).

Note on Dirichlet characters. In the special case where bid is attached to G = (ℤ/qℤ)^* (as per G = znstar(q,1)), the Dirichlet character chi can be written in one of the usual 3 formats: a t_VEC in terms of bid.gen as above, a t_COL in terms of the Conrey generators, or a t_INT (Conrey label); see Section se:dirichletchar or ??character.

The character value is encoded as follows, depending on the optional argument z:

* If z is omitted: return the rational number c(x)/o for x coprime to q, where we normalize 0 ≤ c(x) < o. If x can not be mapped to the group (e.g. x is not coprime to the conductor of a Dirichlet or Hecke character) we return the sentinel value -1.

* If z is an integer o, then we assume that o is a multiple of the character order and we return the integer c(x) when x belongs to the group, and the sentinel value -1 otherwise.

* z can be of the form [zeta, o], where zeta is an o-th root of 1 and o is a multiple of the character order. We return ζ^c(x) if x belongs to the group, and the sentinel value 0 otherwise. (Note that this coincides with the usual extension of Dirichlet characters to ℤ, or of Hecke characters to general ideals.)

* Finally, z can be of the form [vzeta, o], where vzeta is a vector of powers ζ⁰,..., ζ^o-1 of some o-th root of 1 and o is a multiple of the character order. As above, we return ζ^c(x) after a table lookup. Or the sentinel value 0.

The library syntax is GEN chareval(GEN G, GEN chi, GEN x, GEN z = NULL).

Let cyc represent a finite abelian group by its elementary divisors (any object which has a .cyc method is also allowed, i.e. the output of znstar or bnrinit). Return a list of representatives for the Galois orbits of complex characters of G. If ORD is present, select characters depending on their orders:

* if ORD is a t_INT, restrict to orders less than this bound;

* if ORD is a t_VEC or t_VECSMALL, restrict to orders in the list.

  ? G = znstar(96);
  ? #chargalois(G) \\ 16 orbits of characters mod 96
  %2 = 16
  ? #chargalois(G,4) \\ order less than 4
  %3 = 12
  ? chargalois(G,[1,4]) \\ order 1 or 4; 5 orbits
  %4 = [[0, 0, 0], [2, 0, 0], [2, 1, 0], [2, 0, 1], [2, 1, 1]]

Given a character χ, of order n (charorder(G,chi)), the elements in its orbit are the φ(n) characters χ^k, (k,n) = 1.

The library syntax is GEN chargalois(GEN cyc, GEN ORD = NULL).

Let cyc represent a finite abelian group by its elementary divisors, i.e. (d_j) represents ∑_{j ≤ k} ℤ/d_jℤ with d_k | ... | d₁; any object which has a .cyc method is also allowed, e.g. the output of znstar or bnrinit. A character on this group is given by a row vector χ = [a₁,...,a_n] such that χ(∏ g_j^n_j) = exp(2π i∑_j a_j n_j / d_j), where g_j denotes the generator (of order d_j) of the j-th cyclic component.

This function returns the kernel of χ, as a matrix K in HNF which is a left-divisor of matdiagonal(d). Its columns express in terms of the g_j the generators of the subgroup. The determinant of K is the kernel index.

  ? cyc = [15,5]; chi = [1,1];
  ? charker(cyc, chi)
  %2 =
  [15 12]
  
  [ 0  1]
  
  ? bnf = bnfinit(x^2+23);
  ? bnf.cyc
  %4 = [3]
  ? charker(bnf, [1])
  %5 =
  [3]

Note that for Dirichlet characters (when cyc is znstar(q, 1)), characters in Conrey representation are available, see Section se:dirichletchar or ??character.

  ? G = znstar(8, 1);  \\ (Z/8Z)*
  ? charker(G, 1) \\ Conrey label for trivial character
  %2 =
  [1 0]
  
  [0 1]

The library syntax is GEN charker0(GEN cyc, GEN chi). Also available is GEN charker(GEN cyc, GEN chi), when cyc is known to be a vector of elementary divisors and chi a compatible character (no checks).

Let cyc represent a finite abelian group by its elementary divisors, i.e. (d_j) represents ∑_{j ≤ k} ℤ/d_jℤ with d_k | ... | d₁; any object which has a .cyc method is also allowed, e.g. the output of znstar or bnrinit. A character on this group is given by a row vector χ = [a₁,...,a_n] such that χ(∏ g_j^n_j) = exp(2π i∑_j a_j n_j / d_j), where g_j denotes the generator (of order d_j) of the j-th cyclic component.

Given two characters a and b, return the product character ab.

  ? cyc = [15,5]; a = [1,1]; b =  [2,4];
  ? charmul(cyc, a,b)
  %2 = [3, 0]
  ? bnf = bnfinit(x^2+23);
  ? bnf.cyc
  %4 = [3]
  ? charmul(bnf, [1], [2])
  %5 = [0]

For Dirichlet characters on (ℤ/Nℤ)^*, additional representations are available (Conrey labels, Conrey logarithm), see Section se:dirichletchar or ??character. If the two characters are in the same format, their product is given in the same format, otherwise a Conrey logarithm is used.

  ? G = znstar(100, 1);
  ? G.cyc
  %2 = [20, 2]
  ? a = [10, 1]; \\ usual representation for characters
  ? b = 7; \\ Conrey label;
  ? c = znconreylog(G, 11); \\ Conrey log
  ? charmul(G, b,b)
  %6 = 49   \\ Conrey label
  ? charmul(G, a,b)
  %7 = [0, 15]~  \\ Conrey log
  ? charmul(G, a,c)
  %7 = [0, 6]~   \\ Conrey log

The library syntax is GEN charmul0(GEN cyc, GEN a, GEN b). Also available is GEN charmul(GEN cyc, GEN a, GEN b), when cyc is known to be a vector of elementary divisors and a, b are compatible characters (no checks).

Let cyc represent a finite abelian group by its elementary divisors, i.e. (d_j) represents ∑_{j ≤ k} ℤ/d_jℤ with d_k | ... | d₁; any object which has a .cyc method is also allowed, e.g. the output of znstar or bnrinit. A character on this group is given by a row vector χ = [a₁,...,a_n] such that χ(∏ g_j^n_j) = exp(2π i∑_j a_j n_j / d_j), where g_j denotes the generator (of order d_j) of the j-th cyclic component.

This function returns the order of the character chi.

  ? cyc = [15,5]; chi = [1,1];
  ? charorder(cyc, chi)
  %2 = 15
  ? bnf = bnfinit(x^2+23);
  ? bnf.cyc
  %4 = [3]
  ? charorder(bnf, [1])
  %5 = 3

For Dirichlet characters (when cyc is znstar(q, 1)), characters in Conrey representation are available, see Section se:dirichletchar or ??character:

  ? G = znstar(100, 1); \\ (Z/100Z)*
  ? charorder(G, 7)   \\ Conrey label
  %2 = 4

The library syntax is GEN charorder0(GEN cyc, GEN chi). Also available is GEN charorder(GEN cyc, GEN chi), when cyc is known to be a vector of elementary divisors and chi a compatible character (no checks).

Let cyc represent a finite abelian group by its elementary divisors, i.e. (d_j) represents ∑_{j ≤ k} ℤ/d_jℤ with d_k | ... | d₁; any object which has a .cyc method is also allowed, e.g. the output of znstar or bnrinit. A character on this group is given by a row vector χ = [a₁,...,a_n] such that χ(∏ g_j^n_j) = exp(2π i∑_j a_j n_j / d_j), where g_j denotes the generator (of order d_j) of the j-th cyclic component.

Given n ∈ ℤ and a character a, return the character aⁿ.

  ? cyc = [15,5]; a = [1,1];
  ? charpow(cyc, a, 3)
  %2 = [3, 3]
  ? charpow(cyc, a, 5)
  %2 = [5, 0]
  ? bnf = bnfinit(x^2+23);
  ? bnf.cyc
  %4 = [3]
  ? charpow(bnf, [1], 3)
  %5 = [0]

For Dirichlet characters on (ℤ/Nℤ)^*, additional representations are available (Conrey labels, Conrey logarithm), see Section se:dirichletchar or ??character and the output uses the same format as the input.

  ? G = znstar(100, 1);
  ? G.cyc
  %2 = [20, 2]
  ? a = [10, 1]; \\ standard representation for characters
  ? b = 7; \\ Conrey label;
  ? c = znconreylog(G, 11); \\ Conrey log
  ? charpow(G, a,3)
  %6 = [10, 1]   \\ standard representation
  ? charpow(G, b,3)
  %7 = 43   \\ Conrey label
  ? charpow(G, c,3)
  %8 = [1, 8]~  \\ Conrey log

The library syntax is GEN charpow0(GEN cyc, GEN a, GEN n). Also available is GEN charpow(GEN cyc, GEN a, GEN n), when cyc is known to be a vector of elementary divisors (no check).

Kronecker symbol (x|y), where x and y must be of type integer. By definition, this is the extension of Legendre symbol to ℤ x ℤ by total multiplicativity in both arguments with the following special rules for y = 0, -1 or 2:

* (x|0) = 1 if |x |= 1 and 0 otherwise.

* (x|-1) = 1 if x ≥ 0 and -1 otherwise.

* (x|2) = 0 if x is even and 1 if x = 1,-1 mod 8 and -1 if x = 3,-3 mod 8.

The library syntax is long kronecker(GEN x, GEN y).

Given a datum D describing a group (ℤ/Nℤ)^* and a Dirichlet character χ, return the pair [G, chi], where G is znstar(N, 1)) and chi is a GP character.

The following possibilities for D are supported

* a nonzero t_INT congruent to 0,1 modulo 4, return the real character modulo D given by the Kronecker symbol (D/.);

* a t_INTMOD Mod(m, N), return the Conrey character modulo N of index m (see znconreylog).

* a modular form space as per mfinit([N,k,χ]) or a modular form for such a space, return the underlying Dirichlet character χ (which may be defined modulo a divisor of N but need not be primitive).

In the remaining cases, G is initialized by znstar(N, 1).

* a pair [G, chi], where chi is a standard GP Dirichlet character c = (c_j) on G (generic character t_VEC or Conrey characters t_COL or t_INT); given generators G = ⨁ (ℤ/d_jℤ) g_j, χ(g_j) = e(c_j/d_j).

* a pair [G, chin], where chin is a normalized representation [n, ~{c}] of the Dirichlet character c; χ(g_j) = e(~{c}_j / n) where n is minimal (order of χ).

  ? [G,chi] = znchar(-3);
  ? G.cyc
  %2 = [2]
  ? chareval(G, chi, 2)
  %3 = 1/2
  ?  kronecker(-3,2)
  %4 = -1
  ? znchartokronecker(G,chi)
  %5 = -3
  ? mf = mfinit([28, 5/2, Mod(2,7)]); [f] = mfbasis(mf);
  ? [G,chi] = znchar(mf); [G.mod, chi]
  %7 = [7, [2]~]
  ? [G,chi] = znchar(f); chi
  %8 = [28, [0, 2]~]

The library syntax is GEN znchar(GEN D).

Let G be attached to (ℤ/qℤ)^* (as per G = znstar(q, 1)) and chi be a Dirichlet character on (ℤ/qℤ)^* (see Section se:dirichletchar or ??character). Return the conductor of chi:

  ? G = znstar(126000, 1);
  ? zncharconductor(G,11)   \\ primitive
  %2 = 126000
  ? zncharconductor(G,1)    \\ trivial character, not primitive!
  %3 = 1
  ? zncharconductor(G,1009) \\ character mod 5^3
  %4 = 125

The library syntax is GEN zncharconductor(GEN G, GEN chi).

Let N = ∏_p p^e_p and a Dirichlet character χ, we have a decomposition χ = ∏_p χ_p into character modulo N where the conductor of χ_p divides p^e_p; it equals p^e_p for all p if and only if χ is primitive.

Given a znstar G describing a group (ℤ/Nℤ)^*, a Dirichlet character chi and an integer Q, return ∏_{p | (Q,N)} χ_p. For instance, if Q = p is a prime divisor of N, the function returns χ_p (as a character modulo N), given as a Conrey character (t_COL).

  ? G = znstar(40, 1);
  ? G.cyc
  %2 = [4, 2, 2]
  ? chi = [2, 1, 1];
  ? chi2 = znchardecompose(G, chi, 2)
  %4 = [1, 1, 0]~
  ? chi5 = znchardecompose(G, chi, 5)
  %5 = [0, 0, 2]~
  ? znchardecompose(G, chi, 3)
  %6 = [0, 0, 0]~
  ? c = charmul(G, chi2, chi5)
  %7 = [1, 1, 2]~  \\ t_COL: in terms of Conrey generators !
  ? znconreychar(G,c)
  %8 = [2, 1, 1]   \\ t_VEC: in terms of SNF generators

The library syntax is GEN znchardecompose(GEN G, GEN chi, GEN Q).

Given a Dirichlet character χ on G = (ℤ/Nℤ)^* (see znchar), return the complex Gauss sum g(χ,a) = ∑_{n = 1}^N χ(n) e(a n/N)

  ? [G,chi] = znchar(-3); \\ quadratic Gauss sum: I*sqrt(3)
  ? znchargauss(G,chi)
  %2 = 1.7320508075688772935274463415058723670*I
  ? [G,chi] = znchar(5);
  ? znchargauss(G,chi)  \\ sqrt(5)
  %2 = 2.2360679774997896964091736687312762354
  ? G = znstar(300,1); chi = [1,1,12]~;
  ? znchargauss(G,chi) / sqrt(300) - exp(2*I*Pi*11/25)  \\ = 0
  %4 = 2.350988701644575016 E-38 + 1.4693679385278593850 E-39*I
  ? lfuntheta([G,chi], 1)  \\ = 0
  %5 = -5.79[...] E-39 - 2.71[...] E-40*I

The library syntax is GEN znchargauss(GEN G, GEN chi, GEN a = NULL, long bitprec).

Let G be attached to (ℤ/qℤ)^* (as per G = znstar(q,1)) and let chi be a Dirichlet character on (ℤ/qℤ)^*, given by

* a t_VEC: a standard character on bid.gen,

* a t_INT or a t_COL: a Conrey index in (ℤ/qℤ)^* or its Conrey logarithm; see Section se:dirichletchar or ??character.

Let N be a multiple of q, return the character modulo N extending chi. As usual for arithmetic functions, the new modulus N can be given as a t_INT, via a factorization matrix or a pair [N, factor(N)], or by znstar(N,1).

  ? G = znstar(4, 1);
  ? chi = znconreylog(G,1); \\ trivial character mod 4
  ? zncharinduce(G, chi, 80)  \\ now mod 80
  %3 = [0, 0, 0]~
  ? zncharinduce(G, 1, 80)  \\ same using directly Conrey label
  %4 = [0, 0, 0]~
  ? G2 = znstar(80, 1);
  ? zncharinduce(G, 1, G2)  \\ same
  %4 = [0, 0, 0]~
  
  ? chi = zncharinduce(G, 3, G2)  \\ extend the nontrivial character mod 4
  %5 = [1, 0, 0]~
  ? [G0,chi0] = znchartoprimitive(G2, chi);
  ? G0.mod
  %7 = 4
  ? chi0
  %8 = [1]~

Here is a larger example:

  ? G = znstar(126000, 1);
  ? label = 1009;
  ? chi = znconreylog(G, label)
  %3 = [0, 0, 0, 14, 0]~
  ? [G0,chi0] = znchartoprimitive(G, label); \\ works also with 'chi'
  ? G0.mod
  %5 = 125
  ? chi0 \\ primitive character mod 5^3 attached to chi
  %6 = [14]~
  ? G0 = znstar(N0, 1);
  ? zncharinduce(G0, chi0, G) \\ induce back
  %8 = [0, 0, 0, 14, 0]~
  ? znconreyexp(G, %)
  %9 = 1009

The library syntax is GEN zncharinduce(GEN G, GEN chi, GEN N).

Let G be attached to (ℤ/Nℤ)^* (as per G = znstar(N,1)) and let chi be a Dirichlet character on (ℤ/Nℤ)^*, given by

* a t_VEC: a standard character on G.gen,

* a t_INT or a t_COL: a Conrey index in (ℤ/qℤ)^* or its Conrey logarithm; see Section se:dirichletchar or ??character.

Return 1 if and only if chi(-1) = -1 and 0 otherwise.

  ? G = znstar(8, 1);
  ? zncharisodd(G, 1)  \\ trivial character
  %2 = 0
  ? zncharisodd(G, 3)
  %3 = 1
  ? chareval(G, 3, -1)
  %4 = 1/2

The library syntax is long zncharisodd(GEN G, GEN chi).

Let G be attached to (ℤ/Nℤ)^* (as per G = znstar(N,1)) and let chi be a Dirichlet character on (ℤ/Nℤ)^*, given by

* a t_VEC: a standard character on bid.gen,

* a t_INT or a t_COL: a Conrey index in (ℤ/qℤ)^* or its Conrey logarithm; see Section se:dirichletchar or ??character.

If flag = 0, return the discriminant D if chi is real equal to the Kronecker symbol (D/.) and 0 otherwise. The discriminant D is fundamental if and only if chi is primitive.

If flag = 1, return the fundamental discriminant attached to the corresponding primitive character.

  ? G = znstar(8,1); CHARS = [1,3,5,7]; \\ Conrey labels
  ? apply(t->znchartokronecker(G,t), CHARS)
  %2 = [4, -8, 8, -4]
  ? apply(t->znchartokronecker(G,t,1), CHARS)
  %3 = [1, -8, 8, -4]

The library syntax is GEN znchartokronecker(GEN G, GEN chi, long flag).

Let G be attached to (ℤ/qℤ)^* (as per G = znstar(q, 1)) and chi be a Dirichlet character on (ℤ/qℤ)^*, of conductor q₀ | q. Return [G0, chi0], where chi0 is the primitive character attached to chi and G0 is znstar(q0,1); the character chi0 is returned as a Conrey logarithm unless chi is primitive, in which case chi0 is identical to chi.

  ? G = znstar(126000, 1);
  ? [G0,chi0] = znchartoprimitive(G,11)
  ? G0.mod
  %3 = 126000
  ? chi0
  %4 = 11
  ? [G0,chi0] = znchartoprimitive(G,1);\\ trivial character, not primitive!
  ? G0.mod
  %6 = 1
  ? chi0
  %7 = []~
  ? [G0,chi0] = znchartoprimitive(G,1009)
  ? G0.mod
  %4 = 125
  ? chi0
  %5 = [14]~

Note that znconreyconductor is more efficient since it can return χ₀ and its conductor q₀ without needing to initialize G₀. The price to pay is a more cryptic format and the need to initalize G₀ later, but that needs to be done only once for all characters with conductor q₀.

The library syntax is GEN znchartoprimitive(GEN G, GEN chi).

Given a znstar G attached to (ℤ/qℤ)^* (as per G = znstar(q,1)), this function returns the Dirichlet character attached to m ∈ (ℤ/qℤ)^* via Conrey's logarithm, which establishes a "canonical" bijection between (ℤ/qℤ)^* and its dual.

Let q = ∏_p p^e_p be the factorization of q into distinct primes. For all odd p with e_p > 0, let g_p be the element in (ℤ/qℤ)^* which is

* congruent to 1 mod q/p^e_p,

* congruent mod p^e_p to the smallest positive integer that generates (ℤ/p²ℤ)^*.

For p = 2, we let g₄ (if 2^e₂ ≥ 4) and g₈ (if furthermore (2^e₂ ≥ 8) be the elements in (ℤ/qℤ)^* which are

* congruent to 1 mod q/2^e₂,

* g₄ = -1 mod 2^e₂,

* g₈ = 5 mod 2^e₂.

Then the g_p (and the extra g₄ and g₈ if 2^e₂ ≥ 2) are independent generators of (ℤ/qℤ)^*, i.e. every m in (ℤ/qℤ)^* can be written uniquely as ∏_p g_p^m_p, where m_p is defined modulo the order o_p of g_p and p ∈ S_q, the set of prime divisors of q together with 4 if 4 | q and 8 if 8 | q. Note that the g_p are in general not SNF generators as produced by znstar whenever ω(q) ≥ 2, although their number is the same. They however allow to handle the finite abelian group (ℤ/qℤ)^* in a fast and elegant way. (Which unfortunately does not generalize to ray class groups or Hecke characters.)

The Conrey logarithm of m is the vector (m_p)_{p ∈ S_{q}}, obtained via znconreylog. The Conrey character χ_q(m,.) attached to m mod q maps each g_p, p ∈ S_q to e(m_p / o_p), where e(x) = exp(2iπ x). This function returns the Conrey character expressed in the standard PARI way in terms of the SNF generators G.gen.

  ? G = znstar(8,1);
  ? G.cyc
  %2 = [2, 2]  \\ Z/2 x Z/2
  ? G.gen
  %3 = [7, 3]
  ? znconreychar(G,1)  \\ 1 is always the trivial character
  %4 = [0, 0]
  ? znconreychar(G,2)  \\ 2 is not coprime to 8 !!!
    ***   at top-level: znconreychar(G,2)
    ***                 ^ —  —  —  —  — --
    *** znconreychar: elements not coprime in Zideallog:
      2
      8
    ***   Break loop: type 'break' to go back to GP prompt
  break>
  
  ? znconreychar(G,3)
  %5 = [0, 1]
  ? znconreychar(G,5)
  %6 = [1, 1]
  ? znconreychar(G,7)
  %7 = [1, 0]

We indeed get all 4 characters of (ℤ/8ℤ)^*.

For convenience, we allow to input the Conrey logarithm of m instead of m:

  ? G = znstar(55, 1);
  ? znconreychar(G,7)
  %2 = [7, 0]
  ? znconreychar(G, znconreylog(G,7))
  %3 = [7, 0]

The library syntax is GEN znconreychar(GEN G, GEN m).

Let G be attached to (ℤ/qℤ)^* (as per G = znstar(q, 1)) and chi be a Dirichlet character on (ℤ/qℤ)^*, given by

* a t_VEC: a standard character on bid.gen,

* a t_INT or a t_COL: a Conrey index in (ℤ/qℤ)^* or its Conrey logarithm; see Section se:dirichletchar or ??character.

Return the conductor of chi, as the t_INT bid.mod if chi is primitive, and as a pair [N, faN] (with faN the factorization of N) otherwise.

If chi0 is present, set it to the Conrey logarithm of the attached primitive character.

  ? G = znstar(126000, 1);
  ? znconreyconductor(G,11)   \\ primitive
  %2 = 126000
  ? znconreyconductor(G,1)    \\ trivial character, not primitive!
  %3 = [1, matrix(0,2)]
  ? N0 = znconreyconductor(G,1009, &chi0) \\ character mod 5^3
  %4 = [125, Mat([5, 3])]
  ? chi0
  %5 = [14]~
  ? G0 = znstar(N0, 1);      \\ format [N,factor(N)] accepted
  ? znconreyexp(G0, chi0)
  %7 = 9
  ? znconreyconductor(G0, chi0) \\ now primitive, as expected
  %8 = 125

The group G0 is not computed as part of znconreyconductor because it needs to be computed only once per conductor, not once per character.

The library syntax is GEN znconreyconductor(GEN G, GEN chi, GEN *chi0 = NULL).

Given a znstar G attached to (ℤ/qℤ)^* (as per G = znstar(q, 1)), this function returns the Conrey exponential of the character chi: it returns the integer m ∈ (ℤ/qℤ)^* such that znconreylog(G, m) is chi.

The character chi is given either as a

* t_VEC: in terms of the generators G.gen;

* t_COL: a Conrey logarithm.

  ? G = znstar(126000, 1)
  ? znconreylog(G,1)
  %2 = [0, 0, 0, 0, 0]~
  ? znconreyexp(G,%)
  %3 = 1
  ? G.cyc \\ SNF generators
  %4 = [300, 12, 2, 2, 2]
  ? chi = [100, 1, 0, 1, 0]; \\ some random character on SNF generators
  ? znconreylog(G, chi)  \\ in terms of Conrey generators
  %6 = [0, 3, 3, 0, 2]~
  ? znconreyexp(G, %)  \\ apply to a Conrey log
  %7 = 18251
  ? znconreyexp(G, chi) \\ ... or a char on SNF generators
  %8 = 18251
  ? znconreychar(G,%)
  %9 = [100, 1, 0, 1, 0]

The library syntax is GEN znconreyexp(GEN G, GEN chi).

Given a znstar attached to (ℤ/qℤ)^* (as per G = znstar(q,1)), this function returns the Conrey logarithm of m ∈ (ℤ/qℤ)^*.

Let q = ∏_p p^e_p be the factorization of q into distinct primes, where we assume e₂ = 0 or e₂ ≥ 2. (If e₂ = 1, we can ignore 2 from the factorization, as if we replaced q by q/2, since (ℤ/qℤ)^* ~ (ℤ/(q/2)ℤ)^*.)

For all odd p with e_p > 0, let g_p be the element in (ℤ/qℤ)^* which is

* congruent to 1 mod q/p^e_p,

* congruent mod p^e_p to the smallest positive integer that generates (ℤ/p²ℤ)^*.

For p = 2, we let g₄ (if 2^e₂ ≥ 4) and g₈ (if furthermore (2^e₂ ≥ 8) be the elements in (ℤ/qℤ)^* which are

* congruent to 1 mod q/2^e₂,

* g₄ = -1 mod 2^e₂,

* g₈ = 5 mod 2^e₂.

Then the g_p (and the extra g₄ and g₈ if 2^e₂ ≥ 2) are independent generators of ℤ/qℤ^*, i.e. every m in (ℤ/qℤ)^* can be written uniquely as ∏_p g_p^m_p, where m_p is defined modulo the order o_p of g_p and p ∈ S_q, the set of prime divisors of q together with 4 if 4 | q and 8 if 8 | q. Note that the g_p are in general not SNF generators as produced by znstar whenever ω(q) ≥ 2, although their number is the same. They however allow to handle the finite abelian group (ℤ/qℤ)^* in a fast and elegant way. (Which unfortunately does not generalize to ray class groups or Hecke characters.)

The Conrey logarithm of m is the vector (m_p)_{p ∈ S_{q}}. The inverse function znconreyexp recovers the Conrey label m from a character.

  ? G = znstar(126000, 1);
  ? znconreylog(G,1)
  %2 = [0, 0, 0, 0, 0]~
  ? znconreyexp(G, %)
  %3 = 1
  ? znconreylog(G,2)  \\ 2 is not coprime to modulus !!!
    ***   at top-level: znconreylog(G,2)
    ***                 ^ —  —  —  —  — --
    *** znconreylog: elements not coprime in Zideallog:
      2
      126000
    ***   Break loop: type 'break' to go back to GP prompt
  break>
  ? znconreylog(G,11) \\ wrt. Conrey generators
  %4 = [0, 3, 1, 76, 4]~
  ? log11 = ideallog(,11,G)   \\ wrt. SNF generators
  %5 = [178, 3, -75, 1, 0]~

For convenience, we allow to input the ordinary discrete log of m, ideallog(,m,bid), which allows to convert discrete logs from bid.gen generators to Conrey generators.

  ? znconreylog(G, log11)
  %7 = [0, 3, 1, 76, 4]~

We also allow a character (t_VEC) on bid.gen and return its representation on the Conrey generators.

  ? G.cyc
  %8 = [300, 12, 2, 2, 2]
  ? chi = [10,1,0,1,1];
  ? znconreylog(G, chi)
  %10 = [1, 3, 3, 10, 2]~
  ? n = znconreyexp(G, chi)
  %11 = 84149
  ? znconreychar(G, n)
  %12 = [10, 1, 0, 1, 1]

The library syntax is GEN znconreylog(GEN G, GEN m).

Coppersmith's algorithm. N being an integer and P ∈ ℤ[t], finds in polynomial time in log(N) and d = deg(P) all integers x with |x| ≤ X such that gcd(N, P(x)) ≥ B. This is a famous application of the LLL algorithm meant to help in the factorization of N. Notice that P may be reduced modulo Nℤ[t] without affecting the situation.

The parameter X must not be too large. Assume for now that the leading coefficient of P is coprime to N, then we must have d log X log N < log² B, i.e., X < N^1/d when B = N. Let now P₀ be the gcd of the leading coefficient of P and N. In applications to factorization, we should have P₀ = 1; otherwise, either P₀ = N and we can reduce the degree of P, or P₀ is a non trivial factor of N. For completeness, we nevertheless document the exact conditions that X must satisfy in this case: let p := log_N P₀, b := log_N B, x := log_N X, then

* either p ≥ d / (2d-1) is large and we must have x d < 2b - 1;

* or p < d / (2d-1) and we must have both p < b < 1 - p + p/d and x(d + p(1-2d)) < (b - p)². Note that this reduces to x d < b² when p = 0, i.e., the condition described above.

Some x larger than X may be returned if you are very lucky. The routine runs in polynomial time in log N and d but the smaller B, or the larger X, the slower. The strength of Coppersmith method is the ability to find roots modulo a general composite N: if N is a prime or a prime power, polrootsmod or polrootspadic will be much faster.

We shall now present two simple applications. The first one is finding nontrivial factors of N, given some partial information on the factors; in that case B must obviously be smaller than the largest nontrivial divisor of N.

  setrand(1); \\ to make the example reproducible
  [a,b] = [10^30, 10^31]; D = 20;
  p = randomprime([a,b]);
  q = randomprime([a,b]); N = p*q;
  \\ assume we know 0) p | N; 1) p in [a,b]; 2) the last D digits of p
  p0 = p % 10^D;
  
  ? L = zncoppersmith(10^D*x + p0, N, b \ 10^D, a)
  time = 1ms.
  %6 = [738281386540]
  ? gcd(L[1] * 10^D + p0, N) == p
  %7 = 1

and we recovered p, faster than by trying all possibilities x < 10¹¹.

The second application is an attack on RSA with low exponent, when the message x is short and the padding P is known to the attacker. We use the same RSA modulus N as in the first example:

  setrand(1);
  P = random(N);    \\ known padding
  e = 3;            \\ small public encryption exponent
  X = floor(N^0.3); \\ N^(1/e - epsilon)
  x0 = random(X);   \\ unknown short message
  C = lift( (Mod(x0,N) + P)^e ); \\ known ciphertext, with padding P
  zncoppersmith((P + x)^3 - C, N, X)
  
  \\ result in 37ms.
  %14 = [2679982004001230401]
  
  ? %[1] == x0
  %15 = 1

We guessed an integer of the order of 10¹⁸, almost instantly.

The library syntax is GEN zncoppersmith(GEN P, GEN N, GEN X, GEN B = NULL).

This functions allows two distinct modes of operation depending on g:

* if g is the output of znstar (with initialization), we compute the discrete logarithm of x with respect to the generators contained in the structure. See ideallog for details.

* else g is an explicit element in (ℤ/Nℤ)^*, we compute the discrete logarithm of x in (ℤ/Nℤ)^* in base g. The rest of this entry describes the latter possibility.

The result is [] when x is not a power of g, though the function may also enter an infinite loop in this case.

If present, o represents the multiplicative order of g, see Section se:DLfun; the preferred format for this parameter is [ord, factor(ord)], where ord is the order of g. This provides a definite speedup when the discrete log problem is simple:

  ? p = nextprime(10^4); g = znprimroot(p); o = [p-1, factor(p-1)];
  ? for(i=1,10^4, znlog(i, g, o))
  time = 163 ms.
  ? for(i=1,10^4, znlog(i, g))
  time = 200 ms. \\ a little slower

The result is undefined if g is not invertible mod N or if the supplied order is incorrect.

This function uses

* a combination of generic discrete log algorithms (see below).

* in (ℤ/Nℤ)^* when N is prime: a quadratic sieve index calculus method, suitable for N < 10⁶⁰, say, is used for large prime divisors of the order.

The generic discrete log algorithms are:

* Pohlig-Hellman algorithm, to reduce to groups of prime order q, where q | p-1 and p is an odd prime divisor of N,

* Shanks baby-step/giant-step (q < 2³² is small),

* Pollard rho method (q > 2³²).

The latter two algorithms require O(sqrt{q}) operations in the group on average, hence will not be able to treat cases where q > 10³⁰, say. In addition, Pollard rho is not able to handle the case where there are no solutions: it will enter an infinite loop.

  ? g = znprimroot(101)
  %1 = Mod(2,101)
  ? znlog(5, g)
  %2 = 24
  ? g^24
  %3 = Mod(5, 101)
  
  ? G = znprimroot(2 * 101^10)
  %4 = Mod(110462212541120451003, 220924425082240902002)
  ? znlog(5, G)
  %5 = 76210072736547066624
  ? G^% == 5
  %6 = 1
  ? N = 2^4*3^2*5^3*7^4*11; g = Mod(13, N); znlog(g^110, g)
  %7 = 110
  ? znlog(6, Mod(2,3))  \\ no solution
  %8 = []

For convenience, g is also allowed to be a p-adic number:

  ? g = 3+O(5^10); znlog(2, g)
  %1 = 1015243
  ? g^%
  %2 = 2 + O(5^10)

The library syntax is GEN znlog0(GEN x, GEN g, GEN o = NULL). The function GEN znlog(GEN x, GEN g, GEN o) is also available

x must be an integer mod n, and the result is the order of x in the multiplicative group (ℤ/nℤ)^*. Returns an error if x is not invertible. The parameter o, if present, represents a nonzero multiple of the order of x, see Section se:DLfun; the preferred format for this parameter is [ord, factor(ord)], where ord = eulerphi(n) is the cardinality of the group.

  ? znorder(Mod(3,101))
  %1 = 100
  ? znorder(Mod(5,101))
  %2 = 25
  ? o = [100, factor(100)]; znorder(Mod(3,101), o)
  %3 = 100

It is also allowed to input a znstar(n,1) structure for o. Such a structure implicitly contains n, the group order and its factorization. In this case, x may be replaced by any lift.

  ? G = znstar(101, 1);
  ? znorder(5, G)
  %5 = 25

It is still possible, although unnecessary, to input an integer modulo n...for the right n!

  ? znorder(Mod(5,101), G)
  %6 = 25
  ? znorder(Mod(5,1009), G)
   ***   at top-level: znorder(Mod(5,1009),G)
   ***                 ^ —  —  —  —  —  —  — 
   *** znorder: incorrect type in znorder [inconsistent modulus] (t_INTMOD).

The library syntax is GEN znorder(GEN x, GEN o = NULL).

Returns a primitive root (generator) of (ℤ/nℤ)^*, whenever this latter group is cyclic (n = 4 or n = 2p^k or n = p^k, where p is an odd prime and k ≥ 0). If the group is not cyclic, the function will raise an exception. If n is a prime power, then the smallest positive primitive root is returned. This may not be true for n = 2p^k, p odd.

Note that this function requires factoring p-1 for p as above, in order to determine the exact order of elements in (ℤ/nℤ)^*: this is likely to be costly if p is large.

The library syntax is GEN znprimroot(GEN n).

Gives the structure of the multiplicative group (ℤ/nℤ)^*. The output G depends on the value of flag:

* flag = 0 (default), an abelian group structure [h,d,g], where h = φ(n) is the order (G.no), d (G.cyc) is a k-component row-vector d of integers d_i such that d_i > 1, d_i | d_i-1 for i ≥ 2 and (ℤ/nℤ)^* ~ ∏_{i = 1}^k (ℤ/d_iℤ), and g (G.gen) is a k-component row vector giving generators of the image of the cyclic groups ℤ/d_iℤ.

* flag = 1 the result is a bid structure; this allows computing discrete logarithms using znlog (also in the noncyclic case!).

  ? G = znstar(40)
  %1 = [16, [4, 2, 2], [Mod(17, 40), Mod(21, 40), Mod(11, 40)]]
  ? G.no   \\ eulerphi(40)
  %2 = 16
  ? G.cyc  \\ cycle structure
  %3 = [4, 2, 2]
  ? G.gen  \\ generators for the cyclic components
  %4 = [Mod(17, 40), Mod(21, 40), Mod(11, 40)]
  ? apply(znorder, G.gen)
  %5 = [4, 2, 2]

For user convenience, we define znstar(0) as [2, [2], [-1]], corresponding to ℤ^*, but flag = 1 is not implemented in this trivial case.

The library syntax is GEN znstar0(GEN n, long flag).

Finds a minimal set of generators for the subgroup of (ℤ/fℤ)^* given by a vector (or vectorsmall) H of length f: for 1 ≤ a ≤ f, H[a] is 1 or 0 according as a ∈ H_F or a ∉ H_F. In most PARI functions, subgroups of an abelian group are given as HNF left-divisors of a diagonal matrix, representing the discrete logarithms of the subgroup generators in terms of a fixed generators for the group cyclic components. The present function allows to convert an enumeration of the subgroup elements to this representation as follows:

  ? G = znstar(f, 1);
  ? v = znsubgroupgenerators(H);
  ? subHNF(G, v) = mathnfmodid(Mat([znlog(h, G) | h<-v]), G.cyc);

The function subHNF can be applied to any elements of (ℤ/fℤ)^*, yielding the subgroup they generate, but using znsubgroupgenerators first allows to reduce the number of discrete logarithms to be computed.

For example, if H = {1,4,11,14} ⊂ (ℤ/15ℤ)^×, then we have

  ? f = 15; H = vector(f); H[1]=H[4]=H[11]=H[14] = 1;
  ? v = znsubgroupgenerators(H)
  %2 = [4, 11]
  ? G = znstar(f, 1); G.cyc
  %3 = [4, 2]
  ? subHNF(G, v)
  %4 =
  [2 0]
  
  [0 1]
  ? subHNF(G, [1,4,11,14])
  %5 =
  [2 0]
  
  [0 1]

This function is mostly useful when f is large and H has small index: if H has few elements, one may just use subHNF directly on the elements of H. For instance, let K = ℚ(ζ_p, sqrt{m}) ⊂ L = ℚ(ζ_f), where p is a prime, sqrt{m} is a quadratic number and f is the conductor of the abelian extension K/ℚ. The following GP script creates H as the Galois group of L/K, as a subgroub of (ℤ/fZ)^*:

  HK(m, p, flag = 0)=
  { my(d = quaddisc(m), f = lcm(d, p), H);
    H = vectorsmall(f, a, a % p == 1 && kronecker(d,a) > 0);
    [f, znsubgroupgenerators(H,flag)];
  }
  ? [f, v] = HK(36322, 5)
  time = 193 ms.
  %1 = [726440, [41, 61, 111, 131]]
  ? G = znstar(f,1); G.cyc
  %2 = [1260, 12, 2, 2, 2, 2]
  ? A = subHNF(G, v)
  %3 =
  [2 0 1 1 0 1]
  
  [0 4 0 0 0 2]
  
  [0 0 1 0 0 0]
  
  [0 0 0 1 0 0]
  
  [0 0 0 0 1 0]
  
  [0 0 0 0 0 1]
  \\ Double check
  ? p = 5; d = quaddisc(36322);
  ? w = select(a->a % p == 1 && kronecker(d,a) > 0, [1..f]); #w
  time = 133 ms.
  %5 = 30240  \\ w enumerates the elements of H
  ? subHNF(G, w) == A \\ same result, about twice slower
  time = 242 ms.
  %6 = 1

This shows that K = ℚ(sqrt{36322},ζ₅) is contained in ℚ(ζ₇₂₆₄₄₀) and H = <41, 61, 111, 131 >. Note that H = <41><61><111 > <131> is not a direct product. If flag = 1, then the function finds generators which decompose H to direct factors:

  ? HK(36322, 5, 1)
  %3 = [726440, [41, 31261, 324611, 506221]]

This time H = <41>x <31261>x <324611 >x <506221 >.

The library syntax is GEN znsubgroupgenerators(GEN H, long flag).