Function: _header_znstar
Class: header
Section: znstar
Doc:
 \section{$(\Z/N\Z)^*$ and Dirichlet characters}\label{se:ZnZ}

 The finite abelian group $G = (\Z/N\Z)^{*}$ can be written as
 $G = \oplus_{i\leq n} (\Z/d_{i}\Z) g_{i}$, with
 $d_{n} \mid \dots \mid d_{2} \mid d_{1}$ (SNF condition), all $d_{i} > 0$
 and $\prod_{i} d_{i} = \phi(N)$.

 The positivity and SNF condition make the $d_{i}$ unique, but the generators
 $g_{i}$, of respective order $d_{i}$, are definitely not unique. The
 $\oplus$ notation means that all elements of $G$ can be written uniquely as
 $\prod_{i} g_{i}^{n_{i}}$ where $n_{i} \in \Z/d_{i}\Z$ (discrete logarithm).
 The $g_{i}$ are the so-called \tev{SNF generators} of $G$.

 The command \kbd{G = znstar(N, 1)} initializes $(\Z/N\Z)^{*}$, in particular
 computing the \emph{elementary divisors} $d_{i}$ (\kbd{G.cyc}) and the
 \emph{generators} $g_{i}$ (\kbd{G.gen}). This $G$ can be given as argument
 to \kbd{znorder} (order of elements) or \kbd{znlog} (discrete logarithms).

 In the important special case where $G$ is cyclic, \kbd{znprimroot} returns
 a generator without needing a full \kbd{znstar} initialization. Similarly,
 the functions \kbd{znorder} and \kbd{znlog} also allow one-off usage,
 without \kbd{znstar} initialization.

 \subsec{Orders in finite groups and Discrete Logarithm functions} %GPHELPskip
 \label{se:DLfun}

 In addition to \kbd{znorder} and \kbd{znlog}, other functions compute
 the order of an element or discrete logarithms in a finite abelian group:
 \kbd{ellorder} and \kbd{elllog} (the rational points on an elliptic curve
 defined over a finite field), \kbd{fforder} and \kbd{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 \emph{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:

 \item \typ{INT}: the integer $N$,

 \item \typ{MAT}: the factorization \kbd{fa = factor($N$)},

 \item \typ{VEC}: this is the preferred format and provides both the
 integer $N$ and its factorization in a two-component vector \kbd{[$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
 \bprog
 ? 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
 @eprog

 \subsec{Dirichlet characters and Conrey logarithms}\label{se:dirichletchar} %GPHELPskip

 \item a \tev{character} on the abelian group $\oplus_{j} (\Z/d_{j}\Z) g_{j}$
 is given by a row vector $\chi = [a_{1},\ldots,a_{n}]$ of integers
 $0\leq a_{i}  < d_{i}$ such that $\chi(g_{j}) = e(a_{j} / d_{j})$ for all $j$,
 with the standard notation $e(x) := \exp(2i\pi x)$.
 In other words,
 $\chi(\prod_{j} g_{j}^{n_{j}}) = e(\sum_{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 $(\Z/N\Z)^{*}$, 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 = \prod p^{e_{p}}$
 is the factorization of $N$ into primes, the so-called \tev{Conrey generators}
 of $G$ are the generators of the $(\Z/p^{e_{p}}\Z)^{*}$ lifted to
 $(\Z/N\Z)^{*}$ 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^{2}$, and for $p = 2$ we take $-1$ if $e_{2} > 1$ and additionally $5$
 if $e_{2} > 2$). We can again write $G = \oplus_{i\leq n} (\Z/D_{i}\Z) G_{i}$,
 where again $\prod_{i} D_{i} = \phi(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}-2}$ $(e_{2} > 2)$. Nevertheless, any
 $m\in (\Z/N\Z)^{*}$ can be uniquely decomposed as $m = \prod_{j} G_{i}^{m_{i}}$
 for some $m_{i}$ modulo $D_{i}$ and we can define a character by $\chi(G_{j})
 = e(m_{j} / D_{j})$ for all $j$.

 \item The \emph{column vector} of the $m_{j}$, $0 \leq m_{j} < D_{j}$ is
 called the \tev{Conrey logarithm} of $m$ (discrete logarithm in terms of the
 Conrey generators). Note that discrete logarithms in PARI/GP are always
 expressed as \typ{COL}s.

 \item The attached character is called the \tev{Conrey character}
 attached to $m$.

 To sum up a Dirichlet character can be defined by a \typ{INTMOD}
 \kbd{Mod}$(m, N)$, a \typ{INT} lift (the Conrey label $m$),
 a \typ{COL} (the Conrey logarithm of $m$, in terms of the Conrey
 generators) or a \typ{VEC} (in  terms of the SNF generators). The \typ{COL}
 format, i.e. Conrey logarithms, is the preferred (fastest) representation.

 Concretely, this works as follows:

 \kbd{G = znstar(N, 1)} initializes $(\Z/N\Z)^{*}$, which must be given as
 first argument to all functions handling Dirichlet characters.

 \kbd{znconreychar} transforms \typ{INT}, \typ{INTMOD} and \typ{COL} to a SNF
 character.

 \kbd{znconreylog} transforms \typ{INT}, \typ{INTMOD} and \typ{VEC}
 to a Conrey logarithm.

 \kbd{znconreyexp} transforms \typ{VEC} and \typ{COL} to a Conrey label.

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