The finite abelian group G = (ℤ/Nℤ)* can be written as G = ⨁ i ≤ n (ℤ/diℤ) gi, with dn | ... | d2 | d1 (SNF condition), all di > 0 and ∏i di = φ(N).
The positivity and SNF condition make the di unique, but the generators gi, of respective order di, are definitely not unique. The ⨁ notation means that all elements of G can be written uniquely as ∏i gini where ni ∈ ℤ/diℤ (discrete logarithm). The gi are the so-called SNF generators of G.
The command G = znstar(N, 1) initializes (ℤ/Nℤ)*, in particular
computing the elementary divisors di (G.cyc) and the
generators gi (G.gen). This G can be given as argument
to znorder (order of elements) or znlog (discrete logarithms).
In the important special case where G is cyclic, znprimroot returns
a generator without needing a full znstar initialization. Similarly,
the functions znorder and znlog also allow one-off usage,
without znstar initialization.
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 (ℤ/djℤ) gj is given by a row vector χ = [a1,...,an] of integers 0 ≤ ai < di such that χ(gj) = e(aj / dj) for all j, with the standard notation e(x) := exp(2iπ x). In other words, χ(∏j gjnj) = e(∑j aj nj / dj).
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 = ∏ pep is the factorization of N into primes, the so-called Conrey generators of G are the generators of the (ℤ/pepℤ)* lifted to (ℤ/Nℤ)* by requesting that they be congruent to 1 modulo N/pep (for p odd we take the smallest positive primitive root mod p2, and for p = 2 we take -1 if e2 > 1 and additionally 5 if e2 > 2). We can again write G = ⨁ i ≤ n (ℤ/Diℤ) Gi, where again ∏i Di = φ(N). These generators don't satisfy the SNF condition in general since their orders are now (p-1)pep-1 for p odd; for p = 2, the generator -1 has order 2 and 5 has order 2e2-2 (e2 > 2). Nevertheless, any m ∈ (ℤ/Nℤ)* can be uniquely decomposed as m = ∏j Gimi for some mi modulo Di and we can define a character by χ(Gj) = e(mj / Dj) for all j.
* The column vector of the mj, 0 ≤ mj < Dj 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. (dj) represents ∑j ≤ k ℤ/djℤ with dk
| ... | d1; 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 χ = [a1,...,an] such that
χ(∏ gjnj) = exp(2π i∑j aj nj / dj), where
gj denotes the generator (of order dj) 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. (dj) represents ∑j ≤ k ℤ/djℤ with dk.
| ... | d1; 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 = [a1,...,an] such that
χ(∏ gjnj) = exp(2π i∑j aj nj / dj),
where gj denotes the generator (of order dj) 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 = (ℤ/o1ℤ) g1 ⨁ ...⨁ (ℤ/odℤ) gd for some generators (gi) of respective order di, where the group has exponent o := lcmi oi. Since ζo = 1, the vector (ci) in ∏i (ℤ/oiℤ) defines a character χ on G via χ(gi) = ζci (o/oi) 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 ζ0,..., ζ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. (dj) represents ∑j ≤ k ℤ/djℤ with dk
| ... | d1; 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 χ = [a1,...,an] such that
χ(∏ gjnj) = exp(2π i∑j aj nj / dj),
where gj denotes
the generator (of order dj) 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 gj 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. (dj) represents ∑j ≤ k ℤ/djℤ with dk
| ... | d1; 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 χ = [a1,...,an] such that
χ(∏ gjnj) = exp(2π i∑j aj nj / dj),
where gj denotes
the generator (of order dj) 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. (dj) represents ∑j ≤ k ℤ/djℤ with dk
| ... | d1; 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 χ = [a1,...,an] such that
χ(∏ gjnj) = exp(2π i∑j aj nj / dj),
where gj denotes
the generator (of order dj) 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. (dj) represents ∑j ≤ k ℤ/djℤ with dk
| ... | d1; 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 χ = [a1,...,an] such that
χ(∏ gjnj) = exp(2π i∑j aj nj / dj),
where gj denotes
the generator (of order dj) of the j-th cyclic component.
Given n ∈ ℤ and a character a, return the character an.
? 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 = (cj) on G (generic character t_VEC or
Conrey characters t_COL or t_INT); given
generators G = ⨁ (ℤ/djℤ) gj, χ(gj) = e(cj/dj).
* a pair [G, chin], where chin is a normalized
representation [n, ~{c}] of the Dirichlet character c; χ(gj)
= 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 pep and a Dirichlet character χ, we have a decomposition χ = ∏p χp into character modulo N where the conductor of χp divides pep; it equals pep 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 = 1N χ(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 q0 | 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 χ0 and its conductor q0 without needing to
initialize G0. The price to pay is a more cryptic format and the need to
initalize G0 later, but that needs to be done only once for all
characters with conductor q0.
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 pep be the factorization of q into distinct primes. For all odd p with ep > 0, let gp be the element in (ℤ/qℤ)* which is
* congruent to 1 mod q/pep,
* congruent mod pep to the smallest positive integer that generates (ℤ/p2ℤ)*.
For p = 2, we let g4 (if 2e2 ≥ 4) and g8 (if furthermore (2e2 ≥ 8) be the elements in (ℤ/qℤ)* which are
* congruent to 1 mod q/2e2,
* g4 = -1 mod 2e2,
* g8 = 5 mod 2e2.
Then the gp (and the extra g4 and g8 if 2e2 ≥ 2) are
independent generators of (ℤ/qℤ)*, i.e. every m in (ℤ/qℤ)*
can be written uniquely as ∏p gpmp, where mp is defined
modulo the
order op of gp and p ∈ Sq, the set of prime divisors of q
together with 4 if 4 | q and 8 if 8 | q. Note that the gp
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 (mp)p ∈ S_{q}, obtained
via znconreylog. The Conrey character χq(m,.) attached to
m mod q maps
each gp, p ∈ Sq to e(mp / op), 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 pep be the factorization of q into distinct primes, where we assume e2 = 0 or e2 ≥ 2. (If e2 = 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 ep > 0, let gp be the element in (ℤ/qℤ)* which is
* congruent to 1 mod q/pep,
* congruent mod pep to the smallest positive integer that generates (ℤ/p2ℤ)*.
For p = 2, we let g4 (if 2e2 ≥ 4) and g8 (if furthermore (2e2 ≥ 8) be the elements in (ℤ/qℤ)* which are
* congruent to 1 mod q/2e2,
* g4 = -1 mod 2e2,
* g8 = 5 mod 2e2.
Then the gp (and the extra g4 and g8 if 2e2 ≥ 2) are
independent generators of ℤ/qℤ*, i.e. every m in (ℤ/qℤ)* can be
written uniquely as ∏p gpmp, where mp is defined modulo
the order op of gp and p ∈ Sq, the set of prime divisors of
q together with 4 if 4 | q and 8 if 8 | q. Note that the
gp
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 (mp)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 < log2 B, i.e., X < N1/d when B = N. Let now P0 be the gcd of the leading coefficient of P and N. In applications to factorization, we should have P0 = 1; otherwise, either P0 = N and we can reduce the degree of P, or P0 is a non trivial factor of N. For completeness, we nevertheless document the exact conditions that X must satisfy in this case: let p := logN P0, b := logN B, x := logN 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)2. Note that this reduces to x d < b2 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 < 1011.
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 1018, 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 < 1060, 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 < 232 is small),
* Pollard rho method (q > 232).
The latter two algorithms require O(sqrt{q}) operations in the group on average, hence will not be able to treat cases where q > 1030, 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 = 2pk or n = pk, 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 = 2pk, 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 di such that di > 1,
di | di-1 for i ≥ 2 and
(ℤ/nℤ)* ~ ∏i = 1k (ℤ/diℤ),
and g (G.gen) is a k-component row vector giving generators of
the image of the cyclic groups ℤ/diℤ.
* 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 ∈ HF
or a ∉ HF. 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},ζ5) is contained in
ℚ(ζ726440) 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).