Displaying similar documents to “A fast algorithm for polynomial factorization over ℚ p ”

A polynomial reduction algorithm

Henri Cohen, Francisco Diaz Y Diaz (1991)

Journal de théorie des nombres de Bordeaux

Similarity:

The algorithm described in this paper is a practical approach to the problem of giving, for each number field K a polynomial, as canonical as possible, a root of which is a primitive element of the extension K / ℚ . Our algorithm uses the L L L algorithm to find a basis of minimal vectors for the lattice of ℝ n determined by the integers of K under the canonical map.

On computing subfields. A detailed description of the algorithm

Jürgen Klüners (1998)

Journal de théorie des nombres de Bordeaux

Similarity:

Let ℚ ( α ) be an algebraic number field given by the minimal polynomial f of α . We want to determine all subfields ℚ ( β ) ⊂ ℚ ( α ) of given degree. It is convenient to describe each subfield by a pair ( g , h ) ∈ ℤ [ t ] × ℚ [ t ] such that g is the minimal polynomial of β = h ( α ) . There is a bijection between the block systems of the Galois group of f and the subfields of ℚ ( α ) . These block systems are computed using cyclic subgroups of the Galois group which we get from the Dedekind criterion. When a block system is known we compute the corresponding...

On Elkies subgroups of ℓ -torsion points in elliptic curves defined over a finite field

Reynald Lercier, Thomas Sirvent (2008)

Journal de Théorie des Nombres de Bordeaux

Similarity:

As a subproduct of the Schoof-Elkies-Atkin algorithm to count points on elliptic curves defined over finite fields of characteristic p , there exists an algorithm that computes, for ℓ an Elkies prime, ℓ -torsion points in an extension of degree ℓ - 1 at cost O ˜ ( ℓ max ( ℓ , log q ) 2 ) bit operations in the favorable case where ℓ ≤ p / 2 . We combine in this work a fast algorithm for computing isogenies due to Bostan, Morain, Salvy and Schost with the p -adic approach followed by Joux and Lercier to get an algorithm...

On some subgroups of the multiplicative group of finite rings

José Felipe Voloch (2004)

Journal de Théorie des Nombres de Bordeaux

Similarity:

Let S be a subset of F q , the field of q elements and h ∈ F q [ x ] a polynomial of degree d > 1 with no roots in S . Consider the group generated by the image of { x - s ∣ s ∈ S } in the group of units of the ring F q [ x ] / ( h ) . In this paper we present a number of lower bounds for the size of this group. Our main motivation is an application to the recent polynomial time primality testing algorithm [AKS]. The bounds have also applications to graph theory and to the bounding of the number of rational points on abelian covers of...