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).