%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%
%%  quadratic_ideal.tex       LiDIA documentation
%%
%%  This file contains the documentation of the class quadratic_ideal
%%
%%  Copyright   (c)   1996   by  LiDIA-Group
%%
%%  Author:  Michael J. Jacobson, Jr., Markus Maurer
%%

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\NAME

\CLASS{quadratic_ideal} \dotfill fractional ideals of quadratic orders


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ABSTRACT

\code{quadratic_ideal} is a class for representing and computing with fractional ideals of
quadratic orders.  It supports basic operations like ideal multiplication as well as more
complex operations such as computing the order of an equivalence class in the class group.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\DESCRIPTION

A \code{quadratic_ideal} is represented as an ordered triple $(q,a,b)$ ($a$ and $b$ are
\code{bigint}, $q$ is \code{bigrational}) representing the $\bbfZ$-module $q [a\bbfZ + (b +
\sqrt{\D})/ 2\, \bbfZ ]$.  In addition to $a$, $b$, and $q$, a pointer to the
\code{quadratic_order} to which the ideal belongs is stored with each instance of
\code{quadratic_ideal}.

Let $I$ be a real quadratic ideal and $a\in I$.  We call $\alpha$ a minimum of $I$, if $\alpha >
0$ and there is no non-zero number $\beta\in I$ such that $|\beta| < |\alpha|$ and $|\sigma
\beta| < |\sigma \alpha|$, where $\sigma$ denotes the conjugate map.  We call $I$ reduced, if
$1$ is a minimum in $I$, which is equivalent to the fact that $\bigl|\sqrt{\D} - 2 |a|\bigr| < b
< \sqrt{\D}$, i.e., the corresponding form $a,b,c$ is reduced, and $q = 1/a$.  Similarly, a
imaginary quadratic ideal $I$ is called reduced, if $a \leq c$ and $b \geq 0$ if $a = c$ and $q
= 1/a$.  Here, $c = (b^{2} - \D)/(4a)$.

This class is meant to be used for general computations with quadratic ideals.  The classes
\code{qi_class} and \code{qi_class_real} should be used for computations specific to quadratic
ideal equivalence classes.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\CONS

\begin{fcode}{ct}{quadratic_ideal}{}
  initializes with the zero ideal.
\end{fcode}

\begin{fcode}{ct}{quadratic_ideal}{const bigint & $a_2$, const bigint &
    $b_2$, bigrational & $q_2$, quadratic_order & $\Or_2$ = last_order}%
  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it,
  otherwise $A$ is set to the zero ideal.  If $\Or_2$ is omitted, the most-recently accessed
  \code{quadratic_order} will be used.
\end{fcode}

\begin{fcode}{ct}{quadratic_ideal}{const long $a_2$, const long $b_2$, bigrational & $q_2$,
    quadratic_order & $\Or_2$ = last_order}%
  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it,
  otherwise $A$ is set to the zero ideal.  If $\Or_2$ is omitted, the most-recently accessed
  \code{quadratic_order} will be used.
\end{fcode}

\begin{fcode}{ct}{quadratic_ideal}{const quadratic_form & $f$}
  initializes with the positively oriented ideal associated with $f$.  If $f$ is not regular,
  the \code{quadratic_ideal} will be initialized to zero.
\end{fcode}

\begin{fcode}{ct}{quadratic_ideal}{const qi_class & $A$}
  initializes with the reduced ideal $A$.
\end{fcode}

\begin{fcode}{ct}{quadratic_ideal}{const qi_class_real & $A$}
  initializes with the reduced ideal $A$.
\end{fcode}

\begin{fcode}{ct}{quadratic_ideal}{const quadratic_ideal & $A$}
  initializes a copy of $A$.
\end{fcode}

\begin{fcode}{ct}{quadratic_ideal}{const quadratic_order & $O$}
  initializes with the ideal $O$.
\end{fcode}

\begin{fcode}{dt}{~quadratic_ideal}{}
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ASGN

Let $A$ be of type \code{quadratic_ideal}.  The operator \code{=} is overloaded.  For efficiency
reasons, the following functions are also implemented.  Note that the parameter $\Or_2$ is
optional.  If it is omitted, the new ideal will belong to the most recently accessed quadratic
order.

\begin{fcode}{void}{$A$.assign_zero}{quadratic_order & $\Or_2$ = last_order}
  $A = (0)$, the zero ideal.
\end{fcode}

\begin{fcode}{void}{$A$.assign_one}{quadratic_order & $\Or_2$ = last_order}
  $A = (1)$, the whole order.
\end{fcode}

\begin{fcode}{void}{$A$.assign_principal}{const bigint & $x$, const bigint & $y$,
    quadratic_order & $\Or_2$ = last_order}%
  sets $A$ to the principal ideal generated by $x + y (\D + \sqrt{\D}) / 2$, where $\D$ is the
  discriminant of $\Or_2$.
\end{fcode}

\begin{fcode}{bool}{$A$.assign}{const bigint & $a_2$, const bigint & $b_2$,
    const bigrational & $q_2$, quadratic_order & $\Or_2$ = last_order}%
  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it
  and \TRUE is returned.  Otherwise, $A$ will be set to zero and \FALSE is returned.
\end{fcode}

\begin{fcode}{bool}{$A$.assign}{const long $a_2$, const long $b_2$, const bigrational & $q_2$,
    quadratic_order & $\Or_2$ = last_order}%
  if $q_2 [a_2\bbfZ + (b_2 + \sqrt{\D})/2\, \bbfZ ]$ is an ideal of $\Or_2$, $A$ is set to it
  and \TRUE is returned.  Otherwise, $A$ will be set to zero and \FALSE is returned.
\end{fcode}

\begin{fcode}{void}{$A$.assign}{const quadratic_form & $f$}
  sets $A$ to the positively oriented ideal associated with $f$.  If $f$ is not regular, the
  \LEH will be evoked.
\end{fcode}

\begin{fcode}{void}{$A$.assign}{const qi_class & $B$}
  sets $A$ to the reduced ideal $B$.
\end{fcode}

\begin{fcode}{void}{$A$.assign}{const qi_class_real & $B$}
  sets $A$ to the reduced ideal $B$.
\end{fcode}

\begin{fcode}{void}{$A$.assign}{const quadratic_ideal & $B$}
  $A \assign B$.
\end{fcode}

\begin{fcode}{bool}{$A$.assign_order}{quadratic_order & $\Or_2$}
  changes the quadratic order to which $A$ belongs.  If $A$ is not an ideal in $\Or_2$, nothing
  is changed and false is returned.  Otherwise, true is returned.
\end{fcode}

\begin{fcode}{bool}{$A$.set_order}{quadratic_order & $\Or_2$}
  changes the quadratic order to which $A$ belongs.  If $A$ is not an ideal in $\Or_2$, nothing
  is changed and false is returned.  Otherwise, true is returned.
\end{fcode}

\begin{Tfcode}{void}{$A$.assign_module_of}{const bigrational & $nq$,
    quadratic_number_standard $q_1$, quadratic_number_standard $q_2$}%
    Initializes the coefficients of $A$ such that $q (\bbfZ a + \bbfZ
    (b + \sqrt{\D})/2) = n q (\bbfZ q_1 + \bbfZ q_2)$ without assigning an order to $A$.
\end{Tfcode}

\begin{fcode}{bool}{$A$.assign}{const bigrational & $nq$,
    const quadratic_number_standard & $q_1$,const quadratic_number_standard & $q_2$}%
  If $q (\bbfZ q_1 + \bbfZ q_2)$ is a quadratic ideal, i.e., a $\bbfZ$ module of rank $2$, the
  function returns true, and assigns the standard representation of the module to $A$.
  Otherwise the function returns false, and initializes the ideal with the order.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ACCS

Let $A$ be of type \code{quadratic_ideal}.

\begin{cfcode}{bigint}{$A$.get_a}{}
  returns the coefficient $a$ in the representation $(q,a,b)$ of $A$.
\end{cfcode}

\begin{cfcode}{bigint}{$A$.get_b}{}
  returns the coefficient $b$ in the representation $(q,a,b)$ of $A$.
\end{cfcode}

\begin{cfcode}{bigrational}{$A$.get_q}{}
  returns the coefficient $q$ in the representation $(q,a,b)$ of $A$.
\end{cfcode}

\begin{cfcode}{bigint}{$A$.get_c}{}
  returns the value $c = (b^2 - \D ) / (4a)$ corresponding to the representation $(q,a,b)$ of
  $A$, where $\D$ is the discriminant of the quadratic order to which $A$ belongs.
\end{cfcode}

\begin{cfcode}{const quadratic_order &}{$A$.which_order}{}
  returns a reference to the \code{quadratic_order} of which $A$ belongs.
\end{cfcode}

\begin{cfcode}{const quadratic_order &}{$A$.get_order}{}
  returns a reference to the \code{quadratic_order} of which $A$ belongs.
\end{cfcode}

\begin{fcode}{const quadratic_order &}{which_order}{const quadratic_ideal & $A$}
  returns a reference to the \code{quadratic_order} of which $A$ belongs.
\end{fcode}

\begin{cfcode}{bigint}{$A$.discriminant}{}
  returns the discriminant of the quadratic order to which $A$ belongs.
\end{cfcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\ARTH

Let $A$ be of type \code{quadratic_ideal}.  The following operators are overloaded and can be
used in exactly the same way as in the programming language C++.
\begin{center}
  \code{(unary) -}\\
  \code{(binary) +, *, /}\\
  \code{(binary with assignment) *=,  /=}\\
\end{center}
\textbf{Note:} By $-A$ and $A^{-1}$ we denote the inverse of $A$ if it exists, by $A / B$ we
denote $A \cdot B^{-1}$, and by $A + B$ the set $\{ a+b | a\in A, b\in B\}$.

To avoid copying, these operations can also be performed by the following functions:

\begin{fcode}{void}{add}{quadratic_ideal & $C$, const quadratic_ideal & $A$,
    const quadratic_ideal & $B$}%
  $C \assign A + B$ if $A$ and $B$ are of the same quadratic order; otherwise the \LEH will be evoked.
\end{fcode}

%\begin{fcode}{void}{intersect}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const quadratic_ideal & $B$}
%       $C$ is set to the intersection of $A$ and $B$ if they
%       are of the same quadratic order;
%       otherwise the \LEH will be evoked.
%\end{fcode}

\begin{fcode}{void}{multiply}{quadratic_ideal & $C$, const quadratic_ideal & $A$,
    const quadratic_ideal & $B$}%
  $C \assign A \cdot B$.  If $A$ and $B$ do not belong to the same quadratic order, the \LEH will be
  evoked.
\end{fcode}

\begin{fcode}{void}{multiply}{quadratic_ideal & $J$, const quadratic_ideal & $I$,
    const quadratic_number_standard & $g$}%
  $J \assign I \cdot (g \cdot O)$, where $O$ is the order of $I$ and $g$.
\end{fcode}

\begin{fcode}{void}{$A$.conjugate}{}
  $A$ is set to the conjugate of $A$.
\end{fcode}

\begin{fcode}{void}{get_conjugate}{quadratic_ideal & $A$, const quadratic_ideal & $B$}
  $A$ is set to the conjugate of $B$.
\end{fcode}

\begin{fcode}{quadratic_ideal}{get_conjugate}{quadratic_ideal & $A$}
  returns the conjugate of $A$.
\end{fcode}

\begin{fcode}{void}{$A$.invert}{}
  If $A$ is invertible, $A \assign A^{-1}$, otherwise $A$ is set to its conjugate.
\end{fcode}

\begin{fcode}{void}{inverse}{quadratic_ideal & $A$, const quadratic_ideal & $B$}
  If $B$ is invertible, $A \assign B^{-1}$, otherwise $A$ is set to the conjugate of $B$.
\end{fcode}

\begin{fcode}{quadratic_ideal}{inverse}{quadratic_ideal & $A$}
  If $A$ is invertible, $A^{-1}$ is returned, otherwise the conjugate of $A$ is returned.
\end{fcode}

\begin{fcode}{void}{divide}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const quadratic_ideal & $B$}
  $C = A \cdot B^{-1}$.  If $A$ and $B$ are not of the same quadratic order or $B = (0)$, the
  \LEH will be evoked.  If $B$ is not invertible, $C$ is set to the product of $A$ and the
  conjugate of $B$.
\end{fcode}

\begin{fcode}{void}{divide}{quadratic_ideal & $J$, const quadratic_ideal & $I$,
    const quadratic_number_standard & $g$}%
  $J \assign I / (g \cdot O)$, where $O$ is the order of $I$ and $g$.
\end{fcode}

\begin{fcode}{void}{square}{quadratic_ideal & $C$, const quadratic_ideal & $A$}
  $C \assign A^2$.
\end{fcode}

\begin{fcode}{void}{power}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const bigint & $i$}
  $C \assign A^i$.  If $i < 0$, $B^i$ is computed where $B = A^{-1}$ or the conjugate of $A$ if $A$ is
  not invertible.
\end{fcode}

\begin{fcode}{void}{power}{quadratic_ideal & $C$, const quadratic_ideal & $A$, const long $i$}
  $C \assign A^i$.  If $i < 0$, $B^i$ is computed where $B = A^{-1}$ or the conjugate of $A$ if
  $A$ is not invertible.
\end{fcode}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\COMP

The binary operators \code{==}, \code{!=}, \code{<=}, \code{<} (true subset), \code{>=},
\code{>} and the unary operator \code{!} (comparison with $(0)$) are overloaded and can be used
in exactly the same way as in the programming language C++.  Let $A$ be an instance of type
\code{quadratic_ideal}.

\begin{cfcode}{bool}{$A$.is_zero}{}
  returns \TRUE if $A = (0)$, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bool}{$A$.is_one}{}
  returns \TRUE if $A = (1)$, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bool}{$A$.is_equal}{const quadratic_ideal & $B$}
  returns \TRUE if $A$ and $B$ are equal, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bool}{$A$.is_subset}{const quadratic_ideal & $B$}
  returns \TRUE if $A$ is a subset of $B$, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bool}{$A$.is_proper_subset}{const quadratic_ideal & $B$}
  returns \TRUE if $A$ is a proper subset of $B$, \FALSE otherwise.
\end{cfcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\BASIC

\begin{cfcode}{operator}{quadratic_form}{}
  cast operator which implicitly converts a \code{quadratic_ideal} to a \code{quadratic_form}.
\end{cfcode}

\begin{cfcode}{operator}{qi_class}{}
  cast operator which implicitly converts a \code{quadratic_ideal} to a \code{qi_class}.  The
  current order of \code{qi_class} will be set to the order of the ideal.
\end{cfcode}

\begin{cfcode}{operator}{qi_class_real}{}
  cast operator which implicitly converts a \code{quadratic_ideal} to a \code{qi_class_real}.
  The current order of \code{qi_class} and \code{qi_class_real} will be set to the order of the
  ideal.
\end{cfcode}

\begin{fcode}{void}{swap}{quadratic_ideal & $A$, quadratic_ideal & $B$}
  exchanges the values of $A$ and $B$.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\HIGH

Let $A$ be of type \code{quadratic_ideal}.

\begin{cfcode}{bigrational}{$A$.smallest_rational}{}
  returns the smallest rational number in $A$.  This is simply the value of $qa$, where $q$ and
  $a$ are coefficients in the representation of $A$.
\end{cfcode}

\begin{cfcode}{bigint}{$A$.denominator}{}
  returns the smallest positive integer $d$ such that $d \cdot A$ is integral. This is simply
  the denominator of $q$, where $q$ is the coefficient of the representation of $A$.
\end{cfcode}

\begin{cfcode}{bigint}{$A$.multiply_by_denominator}{}
  multiplies $A$ by its denominator $d$, where $d$ is the smallest positive integer $d$ such
  that $d \cdot A$ is integral.
\end{cfcode}

\begin{cfcode}{bool}{$A$.is_integral}{}
  returns \TRUE if $A$ is an integral ideal, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bigint}{$A$.conductor}{}
  returns the conductor of $A$.
\end{cfcode}

\begin{cfcode}{bool}{$A$.is_invertible}{}
  returns \TRUE if $A$ is invertible, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bigrational}{$A$.norm}{}
  returns the norm of $A$.
\end{cfcode}

\begin{fcode}{quadratic_order}{$A$.ring_of_multipliers}{}
  returns the ring of multipliers of $A$.
\end{fcode}

\begin{fcode}{bool}{generate_prime_ideal}{quadratic_ideal A, const bigint & $p$,
    quadratic_order & $\Or_2$ = last_order}%
  attempts to set $A$ to the prime ideal lying over the prime $p$.  If successful (the Kronecker
  symbol $\kronecker{\D}{p} \neq -1$), \TRUE is returned, otherwise \FALSE is returned.  Note
  that the parameter $\Or_2$ is optional.  If it is omitted, the new ideal will belong to the
  most recently accessed quadratic order.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Reduction}

For the reduction operator functions, if $A$ is reduced and belongs to an imaginary quadratic
order, it will not be modified.

\begin{cfcode}{bool}{$A$.is_reduced}{}
  returns \TRUE if $A$ is reduced, \FALSE otherwise.
\end{cfcode}

\begin{fcode}{void}{$A$.reduce}{}
  reduces $A$.
\end{fcode}

\begin{fcode}{void}{$A$.reduce}{quadratic_number_standard & $g$}
  computes $g$ such that $A / g$ is reduced and assigns $A \assign A/g$.
\end{fcode}

\begin{fcode}{void}{$A$.rho}{}
  applies the reduction operator $\rho$ once to $A$.
\end{fcode}

\begin{fcode}{void}{$A$.rho}{quadratic_number_standard & $g$}
  computes $g$ sucht that $\rho(A) = A / g$ and assigns $A \assign A / g$.
\end{fcode}

\begin{fcode}{void}{apply_rho}{quadratic_ideal & $C$, const quadratic_ideal & $A$}
  sets $C$ to the result of the reduction operator $\rho$ being applied once to $A$.
\end{fcode}

\begin{fcode}{qi_class}{apply_rho}{quadratic_ideal & $A$}
  returns a \code{qi_class} corresponding to the result of the reduction operator $\rho$ being
  applied once to $A$.
\end{fcode}

\begin{fcode}{void}{$A$.inverse_rho}{}
  applies the inverse reduction operator once to $A$.
\end{fcode}

\begin{fcode}{void}{$A$.inverse_rho}{quadratic_number_standard & $g$}
  computes $g$ sucht that $\rho^{-1}(A) = A / g$ and assigns $A \assign A / g$.
\end{fcode}

\begin{fcode}{void}{apply_inverse_rho}{quadratic_ideal & $C$, const quadratic_ideal & $A$}
  sets $C$ to the result of the inverse reduction operator $\rho^{-1}$ being applied once to $A$.
\end{fcode}

\begin{fcode}{qi_class}{apply_inverse_rho}{quadratic_ideal & $A$}
  returns a \code{qi_class} corresponding to the result of the inverse reduction operator
  $\rho^{-1}$ being applied once to $A$.
\end{fcode}



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Prescribed logarithm}

Let $\Ln$ denote the Lenstra logarithm: $\Ln(x) = 1/2 \ln|x / \sigma(x)|$.

\begin{fcode}{void}{$A$.local_close}{quadratic_number_standard & $\alpha$, xbigfloat & $a$,
    xbigfloat $t$, long $k$}%
  The function transforms $A$ into a reduced ideal $B = A / \alpha$, where $\alpha$ is a minimum
  in $A$ with $|t - \Ln(\alpha)| < |t - \Ln(\beta)| + 2^{-k+1}$ for any minimum $\beta$ in $A$.
  It also computes an absolute $k$-approximation $a$ to $\Ln(\alpha)$.  The function uses
  reduction, $\rho$, and inverse $\rho$ operations to determine $B$.  If $A$ is not a real
  quadratic ideal, the \LEH is called.
\end{fcode}

\begin{fcode}{void}{$A$.order_close}{quadratic_number_power_product & $\alpha$, xbigfloat & $a$,
    xbigfloat $t$, long $k$}%
  If $A$ is a real quadratic order, the function transforms $A$ into a reduced ideal $B = A /
  \alpha$, where $\alpha$ is a minimum in $A$ with $|t - \Ln(\alpha)| < |t - \Ln(\beta)| +
  2^{-k+1}$ for any minimum $\beta$ in $A$.  It also computes an absolute $k$-approximation $a$
  to $\Ln(\alpha)$.  The function uses repeated squaring to determine $B$.  If $A$ is not a real
  quadratic order, the \LEH is called.
\end{fcode}

\begin{fcode}{void}{$A$.close}{quadratic_number_power_product & $\alpha$ xbigfloat & $a$,
    xbigfloat $t$, long $k$}%
  The function transforms $A$ into a reduced ideal $B = A / \alpha$, where $\alpha$ is a minimum
  in $A$ with $|t - \Ln(\alpha)| < |t - \Ln(\beta)| + 2^{-k+1}$ for any minimum $\beta$ in $A$.
  It also computes an absolute $k$-approximation $a$ to $\Ln(\alpha)$.  The function uses
  \code{order_close} and \code{local_close} to determine $B$.  If $A$ is not a real quadratic
  ideal, the \LEH is called.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Equivalence and principality testing}

\begin{cfcode}{bool}{$A$.is_equivalent}{const quadratic_ideal & $B$}
  returns \TRUE if $A$ and $B$ are in the same ideal equivalence class, \FALSE otherwise.
\end{cfcode}

\begin{cfcode}{bool}{$A$.is_principal}{}
  returns \TRUE if $A$ is principal, \FALSE otherwise.
\end{cfcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SSTITLE{Orders, discrete logarithms, and subgroup structures}

\begin{fcode}{bigint}{$A$.order_in_CL}{}
  returns the order of $A$ in the ideal class group of its quadratic order, i.e. the least
  positive integer $x$ such that $A^x$ is equivalent to $(1)$.  It uses the \code{qi_class}
  function of the same name.  If $A$ is not invertible, $0$ is returned.
\end{fcode}

\begin{cfcode}{bool}{$A$.DL}{const quadratic_ideal & $G$, bigint & $x$}
  returns \TRUE if $A$ belongs to the cyclic subgroup generated by $G$, \FALSE otherwise.  If
  so, $x$ is set to the discrete logarithm of $A$ to the base $G$, i.e., the least non-negative
  integer $x$ such that $G^x$ is equivalent to $A$.  If not, $x$ is set to the order of $G$.
  The function uses the \code{qi_class} function of the same name.  If either $A$ or $G$ is not
  invertible, \FALSE is returned and $x$ is set to $0$.
\end{cfcode}

\begin{fcode}{base_vector< bigint >}{subgroup}{base_vector< quadratic_ideal > & $G$}
  returns the vector of elementary divisors representing the structure of the subgroup generated
  by the classes corresponding to the invertible ideals contained in $G$.  The function uses the
  \code{qi_class} function of the same name.
\end{fcode}

\begin{fcode}{bigfloat}{$A$.regulator}{}
  returns an approximation of the regulator of the quadratic order to which $A$ belongs.  If $A$
  belongs to an imaginary quadratic order, $1$ is returned.
\end{fcode}

\begin{fcode}{bigint}{$A$.class_number}{}
  returns the order of the ideal class group of the quadratic order to which $A$ belongs.
\end{fcode}

\begin{fcode}{base_vector< bigint >}{$A$.class_group}{}
  returns the vector of elementary divisors representing the structure of the ideal class group
  of the quadratic order to which $A$ belongs.
\end{fcode}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\IO

Let $A$ be of type \code{quadratic_ideal}.  The \code{istream} operator \code{>>} and the
\code{ostream} operator \code{<<} are overloaded.  The input of a \code{quadratic_ideal}
consists of \code{(q a b)}, where $q$ is a \code{bigrational} and $a$ and $b$ are integers
corresponding to the representation $A = q [ a \bbfZ + (b + \sqrt{\D})/2 \, \bbfZ ]$.  The ideal
is assumed to belong to the most recently accessed quadratic order.  The output has the format
$((q),a,b)$.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\SEEALSO

\SEE{quadratic_order},
\SEE{qi_class},
\SEE{qi_class_real},
\SEE{quadratic_form}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%\NOTES


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\EXAMPLES

\begin{quote}
\begin{verbatim}
#include <LiDIA/quadratic_order.h>
#include <LiDIA/quadratic_ideal.h>

int main()
{
    quadratic_order QO;
    quadratic_ideal A, B, C;
    bigint D, p, x;

    do {
        cout << "Please enter a quadratic discriminant: "; cin >> D;
    } while (!QO.assign(D));
    cout << endl;

    /* compute 2 prime ideals */
    p = 3;
    while (!generate_prime_ideal(A,p,QO))
        p = next_prime(p);
    p = next_prime(p);
    while (!generate_prime_ideal(B,p,QO))
        p = next_prime(p);

    cout << "A = " << A << endl;
    cout << "B = " << B << endl;

    power(C,B,3);
    C *= -A;
    square(C, C);
    cout << "C = (A^-1*B^3)^2 = " << C << endl;

    cout << "|<C>| = " << C.order_in_CL() << endl;

    C.reduce();
    cout << "C reduced = " << C << endl;

    cout << "ring of multipliers of C:\n";
    cout << C.ring_of_multipliers() << endl;

    if (A.DL(B, x))
        cout << "log_B A = " << x << endl << flush;
    else
        cout << "no discrete log:  |<B>| = " << x << endl << flush;

    return 0
}
\end{verbatim}
\end{quote}

Example:
\begin{quote}
\begin{verbatim}
Please enter a quadratic discriminant: -82636319

A = ((1), 3, 1)
B = ((1), 5, 1)
C = (A^-1*B^3)^2 = ((1/9), 140625, 103541)
|<C>| = 20299
C reduced = ((1), 2856, -271)
ring of multipliers of C:
Quadratic Order:
   Delta = -82636319 (8)

log_B A = 17219
\end{verbatim}
\end{quote}

For further examples please refer to
\path{LiDIA/src/packages/quadratic_order/quadratic_ideal_appl.cc}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\AUTHOR

Michael J.~Jacobson, Jr.
