\section{Built-in Module \sectcode{mpz}}
\label{module-mpz}
\bimodindex{mpz}

This is an optional module.  It is only available when Python is
configured to include it, which requires that the GNU MP software is
installed.

This module implements the interface to part of the GNU MP library,
which defines arbitrary precision integer and rational number
arithmetic routines.  Only the interfaces to the \emph{integer}
(\samp{mpz_{\rm \ldots}}) routines are provided. If not stated
otherwise, the description in the GNU MP documentation can be applied.

In general, \dfn{mpz}-numbers can be used just like other standard
Python numbers, e.g.\ you can use the built-in operators like \code{+},
\code{*}, etc., as well as the standard built-in functions like
\code{abs}, \code{int}, \ldots, \code{divmod}, \code{pow}.
\strong{Please note:} the \emph{bitwise-xor} operation has been implemented as
a bunch of \emph{and}s, \emph{invert}s and \emph{or}s, because the library
lacks an \code{mpz_xor} function, and I didn't need one.

You create an mpz-number by calling the function called \code{mpz} (see
below for an exact description). An mpz-number is printed like this:
\code{mpz(\var{value})}.

\renewcommand{\indexsubitem}{(in module mpz)}
\begin{funcdesc}{mpz}{value}
  Create a new mpz-number. \var{value} can be an integer, a long,
  another mpz-number, or even a string. If it is a string, it is
  interpreted as an array of radix-256 digits, least significant digit
  first, resulting in a positive number. See also the \code{binary}
  method, described below.
\end{funcdesc}

A number of \emph{extra} functions are defined in this module. Non
mpz-arguments are converted to mpz-values first, and the functions
return mpz-numbers.

\begin{funcdesc}{powm}{base\, exponent\, modulus}
  Return \code{pow(\var{base}, \var{exponent}) \%{} \var{modulus}}. If
  \code{\var{exponent} == 0}, return \code{mpz(1)}. In contrast to the
  \C-library function, this version can handle negative exponents.
\end{funcdesc}

\begin{funcdesc}{gcd}{op1\, op2}
  Return the greatest common divisor of \var{op1} and \var{op2}.
\end{funcdesc}

\begin{funcdesc}{gcdext}{a\, b}
  Return a tuple \code{(\var{g}, \var{s}, \var{t})}, such that
  \code{\var{a}*\var{s} + \var{b}*\var{t} == \var{g} == gcd(\var{a}, \var{b})}.
\end{funcdesc}

\begin{funcdesc}{sqrt}{op}
  Return the square root of \var{op}. The result is rounded towards zero.
\end{funcdesc}

\begin{funcdesc}{sqrtrem}{op}
  Return a tuple \code{(\var{root}, \var{remainder})}, such that
  \code{\var{root}*\var{root} + \var{remainder} == \var{op}}.
\end{funcdesc}

\begin{funcdesc}{divm}{numerator\, denominator\, modulus}
  Returns a number \var{q}. such that
  \code{\var{q} * \var{denominator} \%{} \var{modulus} == \var{numerator}}.
  One could also implement this function in Python, using \code{gcdext}.
\end{funcdesc}

An mpz-number has one method:

\renewcommand{\indexsubitem}{(mpz method)}
\begin{funcdesc}{binary}{}
  Convert this mpz-number to a binary string, where the number has been
  stored as an array of radix-256 digits, least significant digit first.

  The mpz-number must have a value greater than or equal to zero,
  otherwise a \code{ValueError}-exception will be raised.
\end{funcdesc}