LMS Durham Symposium

Polynomial factorization over p-adic fields

David FORD (Concordia)

David Ford, Sebastian Pauli, and Xavier-François Roblot

Abstract:

In the last year several new algorithms have appeared for the factorization of polynomials over finite extensions of ${\mathbb{Q} }_p$ .

In his Ph.D. dissertation (Barcelona, 1999), J. Montes Peral gives a complete algorithm for factorizing primes via Newton polygons.
D. Ford, S. Pauli, and X.-R. Roblot (CICMA, Montreal, 2000), have reformulated and greatly improved the Zassenhaus Round Four algorithm. This algorithm is incorporated in the most recent releases of the PARI system.
Cantor and Gordon (ANTS-IV, 2000), applying ideas of Chistov, have proved the following.

Theorem 1 (D.G. CANTOR & D.M. GORDON) Let k be an extension of ${\mathbb{Q} }_p$ of degree k, let ${\mathfrak p}$ be the prime ideal of k, and let $\varPhi(x)$ be a polynomial in k[x] of degree N. Then there exists an algorithm that finds an irreducible factor of $\varPhi(x)$ in random time

$\begin{displaymath}O\bigl(N^{8+\epsilon} v_{\mathfrak p}(\operatorname{disc}\varPhi)^3 \log^2 \!p^k \bigr). \end{displaymath}$
Most recently, S. Pauli has exploited Krasner's lemma to produce a very efficient algorithm. The results below are from his Ph.D. thesis (Concordia University, in progress).

Theorem 2 Let k be a finite extension of ${\mathbb{Q} }_p$ , let ${\mathfrak p}$ be the prime ideal of k, and let $\varPhi(x)\in{\mathbf k}[x]$ be monic and squarefree of degree N. Let $\Omega_{n,q}$ denote the number of steps required to factorize a polynomial of degree n over ${\mathbb{F} }_{\mskip-2muq}$ and let $\Omega^*_{n,q}$ denote the number of steps required to find a primitive element for a degree n extension of ${\mathbb{F} }_{\mskip-2muq}$ , given an ${\mathbb{F} }_{\mskip-2muq}$ -basis for the extension.
Then there exists an algorithm that gives a factorization of $\varPhi(x)$ into irreducible factors with the number of additions and multiplications in k being

$\begin{displaymath}O\bigl(\log N(\Omega^*_{N\!,q} + N^4 \log N + (N^3+\Omega_{N\!,q}) v_{\mathfrak p}(\operatorname{disc}\varPhi))\bigr). \end{displaymath}$

Corollary 1 There exists an algorithm that gives a factorization of $\varPhi(x)$ into irreducible factors with the expected number of additions and multiplications in k being

$\begin{displaymath}O\bigl( N^4 \log^2 N + N^3 \log N \cdot v_{\mathfrak p}(\operatorname{disc}\varPhi) \bigr). \end{displaymath}$

Termination of Pauli's algorithm is guaranteed by the proposition below, which is derived in part from Krasner's lemma.

Proposition 1 Let k be a finite extension of ${\mathbb{Q} }_p$ and let $\alpha_1,\,\dots,\,\alpha_N$ and $a_1,\,\dots,\,a_n$ be elements of an algebraic closure of k that satisfy the following.

1.
$\varPhi(x)=\prod_{j=1}^N(x-\alpha_j)$ is a squarefree polynomial in ${\mathcal O}_{\mathbf k}[x]$ .

2.
$\varphi(x)=\prod_{i=1}^n(x-a_i)$ is a polynomial in k[x].

3.
$\vert\varphi(\alpha_j)\vert^N\! < \vert\operatorname{disc}\varPhi\vert^2$ for $1 \leqslant j \leqslant N$ .

4.
The degree of any irreducible factor of $\varPhi$ is greater than or equal to n.

Then N = n and $\varPhi$ is irreducible over k.

LMS Durham Symposium on Computational Number Theory
24 July - 3 August 2000

Abstract of talks

Rethinking the number field sieve

40 years on

Finding Rational Points on Curves of genus 3

Explicit construction of number field extensions of small degree, with applications to discriminant counting

(Two talks)

Coverings of algebraic curves : explicit methods and applications

Recent Developments in Cryptography: What is "breaking RSA"

The interactive group theory of arithmetically equivalent fields

Estimating the rank of an elliptic curve over its field of n-division points

Fermat Quartics and a Challenge Curve of Serre

Polynomial factorization over p-adic fields

Height Conjectures and Galois Representations Attached to Elliptic Curves

Elliptic Curve Cryptography and Weil descent

(Four talks)

Schoof's Algorithm in genus 2

Imaginary quadratic orders and cryptography

Non-interactive Public-Key Cryptography

Constructive Galois Theory

Fast absolute irreducibility testing for sparse polynomials

Iterative Differential Equations and Abhyankar's Conjecture

Finding a generating unit by real-gcd computations

Modular Curves and Class Invariants

Function Fields: Invariants and Cryptography

Finding torsion cosets on hypersurfaces

The parallelized Pollard Kangaroo method in real quadratic function fields

An introduction to NUCOMP

Real zeros of real odd Dirichlet L-functions and class numbers of imaginary quadratic fields

A key exchange protocol based on real quadratic fields

Shafarevich-Tate groups of modular abelian varieties

LMS Durham Symposium on Computational Number Theory 24 July - 3 August 2000

Abstract of talks

Rethinking the number field sieve

40 years on

Finding Rational Points on Curves of genus 3

Explicit construction of number field extensions of small degree, with applications to discriminant counting

(Two talks)

Coverings of algebraic curves : explicit methods and applications

Recent Developments in Cryptography: What is "breaking RSA"

The interactive group theory of arithmetically equivalent fields

Estimating the rank of an elliptic curve over its field of n-division points

Fermat Quartics and a Challenge Curve of Serre

Polynomial factorization over p-adic fields

Height Conjectures and Galois Representations Attached to Elliptic Curves

Elliptic Curve Cryptography and Weil descent

(Four talks)

Schoof's Algorithm in genus 2

Imaginary quadratic orders and cryptography

Non-interactive Public-Key Cryptography

Constructive Galois Theory

Fast absolute irreducibility testing for sparse polynomials

Iterative Differential Equations and Abhyankar's Conjecture

Finding a generating unit by real-gcd computations

Modular Curves and Class Invariants

Function Fields: Invariants and Cryptography

Finding torsion cosets on hypersurfaces

The parallelized Pollard Kangaroo method in real quadratic function fields

An introduction to NUCOMP

Real zeros of real odd Dirichlet L-functions and class numbers of imaginary quadratic fields

A key exchange protocol based on real quadratic fields

Shafarevich-Tate groups of modular abelian varieties

LMS Durham Symposium on Computational Number Theory
24 July - 3 August 2000