Function: _header_number_theoretical
Class: header
Section: number_theoretical
Doc:
 \section{Basic number theory}
 Functions in this section cover 5 classical arithmetic topics

 \item finite fields;

 \item factorization in polynomial rings, in particular over
 finite fields and over the rationals;

 \item factorization over the integers, including primality proving;

 \item arithmetic functions;

 \item binary quadratic forms and the arithmetic of quadratic fields.

 \subsec{Arithmetic functions}\label{se:arithmetic} %GPHELPskip

 Arithmetic functions are naturally defined over $\Z$ or $\Z_{>0}$ and
 related to integer factorization. An integer argument $N$ can be given in
 the following alternate formats:

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

 \item \typ{VEC}: a pair \kbd{[$N$, fa]} giving both the integer and
   its factorization.

 This allows to compute different arithmetic functions at a given $N$
 while factoring the latter only once.

 \bprog
   ? N = 10!; faN = factor(N);
   ? eulerphi(N)
   %2 = 829440
   ? eulerphi(faN)
   %3 = 829440
   ? eulerphi(S = [N, faN])
   %4 = 829440
   ? sigma(S)
   %5 = 15334088
 @eprog

 \subsec{Arithmetic functions and the factoring engine} %GPHELPskip
 All arithmetic functions in the narrow sense of the word~--- Euler's
 totient\sidx{Euler totient function} function, the \idx{Moebius} function,
 the sums over divisors or powers of divisors, \idx{Ramanujan} $\tau$
 function, etc.--- call the factoring machinery described
 under \kbd{factorint}. It includes trial division by small primes,
 \idx{Shanks SQUFOF}, \idx{Pollard Rho},
 \idx{ECM} and \idx{MPQS} stages, with early exit options for functions
 such as \teb{moebius} and \teb{issquarefree}. This machinery relies on a
 fairly strong probabilistic primality test but, by default, integer
 factorizations are not fully proven, see \kbd{ispseudoprime}. You
 may also set
 \bprog
   default(factor_proven, 1)
 @eprog\noindent to ensure that all tentative factorizations \emph{are} proven.
 This should not slow down PARI too much, unless prime numbers with
 hundreds of decimal digits occur frequently in your application.
