Login | Register

On the complexity of polynomial factorization over P-adic fields

Title:

On the complexity of polynomial factorization over P-adic fields

Veres, Olga Erzsébet (2009) On the complexity of polynomial factorization over P-adic fields. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
NR63368.pdf - Accepted Version
1MB

Abstract

Let p be a rational prime and Z( x ) be a monic irreducible polynomial in Z p [ x ]. Based on the work of Ore on Newton polygons (Ore, 1928) and MacLane's characterization of polynomial valuations (MacLane, 1936), Montes described an algorithm for the decomposition of the ideal [Special characters omitted.] over an algebraic number field (Montes, 1999). We give a simplified version of the Montes algorithm with a full MAPLE implementation which tests the irreducibility of Z( x ) over Q p . We derive an estimate of the complexity of this simplified algorithm in the worst case, when Z( x ) is irreducible over Q p . We show that in this case the algorithm terminates in at most[Special characters omitted.] bit operations. Lastly, we compare the "one-element" and "two-element" variations of the Zassenhaus "Round Four" algorithm with the Montes algorithm

Divisions:Concordia University > Faculty of Arts and Science > Mathematics and Statistics
Item Type:Thesis (PhD)
Authors:Veres, Olga Erzsébet
Pagination:ix, 118 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Mathematics
Date:2009
Thesis Supervisor(s):Ford, D
ID Code:976383
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:24
Last Modified:18 Jan 2018 17:42
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top