Advertisement
Published in:
2010 | OriginalPaper | Chapter
On the Complexity of the Montes Ideal Factorization Algorithm
Authors : David Ford, Olga Veres
Published in: Algorithmic Number Theory
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
Let
p
be a rational prime and let Φ(
X
) be a monic irreducible polynomial in
Z
[
X
], with
n
Φ = degΦ and
δ
Φ =
v
p
(discΦ). In [13] Montes describes an algorithm for the decomposition of the ideal
$p\mathcal{O}K$
in the algebraic number field
K
generated by a root of Φ. A simplified version of the Montes algorithm, merely testing Φ(
X
) for irreducibility over Q
p
, is given in [19], together with a full
Maple
implementation and a demonstration that in the worst case, when Φ(
X
) is irreducible over Q
p
, the expected number of bit operations for termination is
O
(
n
Φ
3 +
ε
δ
Φ
2 +
ε
). We now give a refined analysis that yields an improved estimate of
O
(
n
Φ
3 +
ε
δ
Φ +
n
Φ
2 +
ε
δ
Φ
2 +
ε
) bit operations. Since the worst case of the simplified algorithm coincides with the worst case of the original algorithm, this estimate applies as well to the complete Montes algorithm.