Advanced Topics in Computational Number Theory by Henri Cohen

By Henri Cohen

The computation of invariants of algebraic quantity fields resembling critical bases, discriminants, top decompositions, perfect classification teams, and unit teams is critical either for its personal sake and for its quite a few functions, for instance, to the answer of Diophantine equations. the sensible com­ pletion of this activity (sometimes often called the Dedekind application) has been one of many significant achievements of computational quantity concept some time past ten years, because of the efforts of many folks. even if a few useful difficulties nonetheless exist, you could think about the topic as solved in a passable demeanour, and it really is now regimen to invite a really expert computing device Algebra Sys­ tem comparable to Kant/Kash, liDIA, Magma, or Pari/GP, to accomplish quantity box computations that might were unfeasible basically ten years in the past. The (very various) algorithms used are basically all defined in A path in Com­ putational Algebraic quantity concept, GTM 138, first released in 1993 (third corrected printing 1996), that is talked about the following as [CohO]. That textual content additionally treats different matters comparable to elliptic curves, factoring, and primality trying out. Itis very important and typical to generalize those algorithms. numerous gener­ alizations might be thought of, however the most vital are definitely the gen­ eralizations to worldwide functionality fields (finite extensions of the sphere of rational capabilities in a single variable overa finite box) and to relative extensions ofnum­ ber fields. As in [CohO], within the current booklet we are going to give some thought to quantity fields merely and never deal in any respect with functionality fields.

Show description

Read or Download Advanced Topics in Computational Number Theory PDF

Similar combinatorics books

Introduction to Higher-Order Categorical Logic

Half I exhibits that typed-calculi are a formula of higher-order common sense, and cartesian closed different types are primarily an analogous. half II demonstrates that one other formula of higher-order good judgment is heavily on the topic of topos conception.

Combinatorial Pattern Matching: 18th Annual Symposium, CPM 2007, London, Canada, July 9-11, 2007. Proceedings

The papers contained during this quantity have been offered on the 18th Annual S- posium on Combinatorial development Matching (CPM 2007) held on the collage of Western Ontario, in London, Ontario, Canada from July nine to eleven, 2007. all of the papers awarded on the convention are unique learn contri- tions on computational trend matching and research, facts compression and compressed textual content processing, su?

Flag varieties : an interplay of geometry, combinatorics, and representation theory

Flag forms are vital geometric items and their examine consists of an interaction of geometry, combinatorics, and illustration thought. This booklet is specific account of this interaction. within the region of illustration conception, the ebook offers a dialogue of advanced semisimple Lie algebras and of semisimple algebraic teams; furthermore, the illustration idea of symmetric teams can be mentioned.

Additional info for Advanced Topics in Computational Number Theory

Example text

We can now start modifying this pseudo-basis. We can first choose to have only integral (and even primitive) ideals a3 by dividing them by suitable ele­ ments of Q' and multiplying the corresponding w1 by the same. Alternatively, we can ask that w1 E M , and this is done in a similar manner. Then we can ask for a pseudo-basis such that all the ideals are equal to R except perhaps the last, whose ideal class will then be the Steinitz class of M. 6. By induction, using legal elementary transformations on the matrix A, we can replace ideal pairs (aj , OjH) by (R, OjOJ +l ), and hence at the end of the process all ideals except perhaps the last one will be equal to R, as desired.

Although quite simple, this generalization is not absolutely straightforward, so we give some details, closely following the exposition of [CohO] and [Coh1] . 2 The Modular HNF Algorithm We have defined above the notion of a minor-ideal of a pseudo-matrix (A, I) . 6 The Modular HNF Algorithm in Dedekind Domains 39 the pseudo-matrix (A, I) . We will say that g 1 (M) is the determinantal ideal of the module M . It is clearly a generalization of the notion of determinant of a lattice. ) minors of order n, it could be a lengthy task to compute g 1 (M) explicitly, except of course when k = n or even k = n + 1 (note that the computation of each minor is an ordinary determinant computation that can be done with the usual Gauss-Bareiss pivoting strategy, which only involves exact divisions) .

Let a be an integral ideal of R and a E a, a -:j; 0. Assume that the prime ideal factorization of a is known. Then there exists a polynomial-time algorithm that finds b E a such that a = aR + bR. Proof. Write a R = TI P p e p with e p 2: 0. Thus, a = TI P pv p ( a ) with 0 ::; vp (a) ::; e p . 8 we can, in polynomial time, find b E R such that vp (b) = vp (a) for all p I a; by looking at p-adic valuations, it is clear that D a = aR + bR. 22 1. Fundamental Results and Algorithms in Dedekind Domains Remarks Recall that R is the ring of integers of a number field.

Download PDF sample

Rated 4.05 of 5 – based on 36 votes