"Fossies" - the Fresh Open Source Software Archive

Member "pari-2.13.1/src/functions/number_fields/bnfisprincipal" (26 Oct 2020, 3659 Bytes) of package /linux/misc/pari-2.13.1.tar.gz:


As a special service "Fossies" has tried to format the requested text file into HTML format (style: standard) with prefixed line numbers. Alternatively you can here view or download the uninterpreted source code file. See also the latest Fossies "Diffs" side-by-side code changes report for "bnfisprincipal": 2.13.0_vs_2.13.1.

    1 Function: bnfisprincipal
    2 Section: number_fields
    3 C-Name: bnfisprincipal0
    4 Prototype: GGD1,L,
    5 Help: bnfisprincipal(bnf,x,{flag=1}): bnf being output by bnfinit, gives
    6  [e,t], where e is the vector of exponents on the class group generators and
    7  t is the generator of the resulting principal ideal. In particular x is
    8  principal if and only if e is the zero vector. flag is optional, whose
    9  binary digits mean 1: output [e,t] (only e if unset); 2: increase precision
   10  until alpha can be computed (do not insist if unset); 4: return alpha in
   11  factored form (compact representation).
   12 Doc: $\var{bnf}$ being the \sidx{principal ideal}
   13  number field data output by \kbd{bnfinit}, and $x$ being an ideal, this
   14  function tests whether the ideal is principal or not. The result is more
   15  complete than a simple true/false answer and solves a general discrete
   16  logarithm problem. Assume the class group is $\oplus (\Z/d_i\Z)g_i$
   17  (where the generators $g_i$ and their orders $d_i$ are respectively given by
   18  \kbd{bnf.gen} and \kbd{bnf.cyc}). The routine returns a row vector $[e,t]$,
   19  where $e$ is a vector of exponents $0 \leq e_i < d_i$, and $t$ is a number
   20  field element such that
   21  $$ x = (t) \prod_i  g_i^{e_i}.$$
   22  For \emph{given} $g_i$ (i.e. for a given \kbd{bnf}), the $e_i$ are unique,
   23  and $t$ is unique modulo units.
   24 
   25  In particular, $x$ is principal if and only if $e$ is the zero vector. Note
   26  that the empty vector, which is returned when the class number is $1$, is
   27  considered to be a zero vector (of dimension $0$).
   28  \bprog
   29  ? K = bnfinit(y^2+23);
   30  ? K.cyc
   31  %2 = [3]
   32  ? K.gen
   33  %3 = [[2, 0; 0, 1]]          \\ a prime ideal above 2
   34  ? P = idealprimedec(K,3)[1]; \\ a prime ideal above 3
   35  ? v = bnfisprincipal(K, P)
   36  %5 = [[2]~, [3/4, 1/4]~]
   37  ? idealmul(K, v[2], idealfactorback(K, K.gen, v[1]))
   38  %6 =
   39  [3 0]
   40 
   41  [0 1]
   42  ? % == idealhnf(K, P)
   43  %7 = 1
   44  @eprog
   45 
   46  \noindent The binary digits of \fl mean:
   47 
   48  \item $1$: If set, outputs $[e,t]$ as explained above, otherwise returns
   49  only $e$, which is much easier to compute. The following idiom only tests
   50  whether an ideal is principal:
   51  \bprog
   52    is_principal(bnf, x) = !bnfisprincipal(bnf,x,0);
   53  @eprog
   54 
   55  \item $2$: It may not be possible to recover $t$, given the initial accuracy
   56  to which the \kbd{bnf} structure was computed. In that case, a warning is
   57  printed and $t$ is set equal to the empty vector \kbd{[]\til}. If this bit is
   58  set, increase the precision and recompute needed quantities until $t$ can be
   59  computed. Warning: setting this may induce \emph{lengthy} computations
   60  and you should consider using flag $4$ instead.
   61 
   62  \item $4$: Return $t$ in factored form (compact representation),
   63  as a small product of $S$-units for a small set of finite places $S$,
   64  possibly with huge exponents. This kind of result can be cheaply mapped to
   65  $K^*/(K^*)^\ell$ or to $\C$ or $\Q_p$ to bounded accuracy and this is usually
   66  enough for applications. Explicitly expanding such a compact representation
   67  is possible using \kbd{nffactorback} but may be very costly. The algorithm
   68  is guaranteed to succeed if the \kbd{bnf} was computed using
   69  \kbd{bnfinit(,1)}. If not, the algorithm may fail to compute a huge
   70  generator in this case (and replace it by \kbd{[]\til}). This is orders of
   71  magnitude faster than flag $2$ when the generators are indeed large.
   72 
   73 Variant: Instead of the above hardcoded numerical flags, one should
   74  rather use an or-ed combination of the symbolic flags \tet{nf_GEN} (include
   75  generators, possibly a place holder if too difficult), \tet{nf_GENMAT}
   76  (include generators in compact form) and
   77  \tet{nf_FORCE} (insist on finding the generators, a no-op if \tet{nf_GENMAT}
   78  is included).