Eintrag weiter verarbeiten
Complexity of OM factorizations of polynomials over local fields
Gespeichert in:
| Zeitschriftentitel: | LMS Journal of Computation and Mathematics |
|---|---|
| Personen und Körperschaften: | , , |
| In: | LMS Journal of Computation and Mathematics, 16, 2013, S. 139-171 |
| Format: | E-Article |
| Sprache: | Englisch |
| veröffentlicht: |
Wiley
|
| Schlagwörter: |
| author_facet |
Bauch, Jens-Dietrich Nart, Enric Stainsby, Hayden D. Bauch, Jens-Dietrich Nart, Enric Stainsby, Hayden D. |
|---|---|
| author |
Bauch, Jens-Dietrich Nart, Enric Stainsby, Hayden D. |
| spellingShingle |
Bauch, Jens-Dietrich Nart, Enric Stainsby, Hayden D. LMS Journal of Computation and Mathematics Complexity of OM factorizations of polynomials over local fields Computational Theory and Mathematics General Mathematics |
| author_sort |
bauch, jens-dietrich |
| spelling |
Bauch, Jens-Dietrich Nart, Enric Stainsby, Hayden D. 1461-1570 Wiley Computational Theory and Mathematics General Mathematics http://dx.doi.org/10.1112/s1461157013000089 <jats:title>Abstract</jats:title><jats:p>Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline1" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> be a locally compact complete field with respect to a discrete valuation <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline2" /><jats:tex-math>$v$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline3" /><jats:tex-math>$ \mathcal{O} $</jats:tex-math></jats:alternatives></jats:inline-formula> be the valuation ring, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline4" /><jats:tex-math>$\mathfrak{m}$</jats:tex-math></jats:alternatives></jats:inline-formula> the maximal ideal and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline5" /><jats:tex-math>$F(x)\in \mathcal{O} [x] $</jats:tex-math></jats:alternatives></jats:inline-formula> a monic separable polynomial of degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline6" /><jats:tex-math>$n$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline7" /><jats:tex-math>$\delta = v(\mathrm{Disc} (F))$</jats:tex-math></jats:alternatives></jats:inline-formula>. The Montes algorithm computes an OM factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline8" /><jats:tex-math>$F$</jats:tex-math></jats:alternatives></jats:inline-formula>. The single-factor lifting algorithm derives from this data a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline9" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, for a prescribed precision <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline10" /><jats:tex-math>$\nu $</jats:tex-math></jats:alternatives></jats:inline-formula>. In this paper we find a new estimate for the complexity of the Montes algorithm, leading to an estimation of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline11" /><jats:tex-math>$O({n}^{2+ \epsilon } + {n}^{1+ \epsilon } {\delta }^{2+ \epsilon } + {n}^{2} {\nu }^{1+ \epsilon } )$</jats:tex-math></jats:alternatives></jats:inline-formula> word operations for the complexity of the computation of a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline12" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, assuming that the residue field of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline13" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> is small.</jats:p> Complexity of OM factorizations of polynomials over local fields LMS Journal of Computation and Mathematics |
| doi_str_mv |
10.1112/s1461157013000089 |
| facet_avail |
Online Free |
| finc_class_facet |
Mathematik |
| format |
ElectronicArticle |
| fullrecord |
blob:ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTExMi9zMTQ2MTE1NzAxMzAwMDA4OQ |
| id |
ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTExMi9zMTQ2MTE1NzAxMzAwMDA4OQ |
| institution |
DE-Bn3 DE-Brt1 DE-Zwi2 DE-D161 DE-Gla1 DE-Zi4 DE-15 DE-Rs1 DE-Pl11 DE-105 DE-14 DE-Ch1 DE-L229 DE-D275 |
| imprint |
Wiley, 2013 |
| imprint_str_mv |
Wiley, 2013 |
| issn |
1461-1570 |
| issn_str_mv |
1461-1570 |
| language |
English |
| mega_collection |
Wiley (CrossRef) |
| match_str |
bauch2013complexityofomfactorizationsofpolynomialsoverlocalfields |
| publishDateSort |
2013 |
| publisher |
Wiley |
| recordtype |
ai |
| record_format |
ai |
| series |
LMS Journal of Computation and Mathematics |
| source_id |
49 |
| title |
Complexity of OM factorizations of polynomials over local fields |
| title_unstemmed |
Complexity of OM factorizations of polynomials over local fields |
| title_full |
Complexity of OM factorizations of polynomials over local fields |
| title_fullStr |
Complexity of OM factorizations of polynomials over local fields |
| title_full_unstemmed |
Complexity of OM factorizations of polynomials over local fields |
| title_short |
Complexity of OM factorizations of polynomials over local fields |
| title_sort |
complexity of om factorizations of polynomials over local fields |
| topic |
Computational Theory and Mathematics General Mathematics |
| url |
http://dx.doi.org/10.1112/s1461157013000089 |
| publishDate |
2013 |
| physical |
139-171 |
| description |
<jats:title>Abstract</jats:title><jats:p>Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline1" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> be a locally compact complete field with respect to a discrete valuation <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline2" /><jats:tex-math>$v$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline3" /><jats:tex-math>$ \mathcal{O} $</jats:tex-math></jats:alternatives></jats:inline-formula> be the valuation ring, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline4" /><jats:tex-math>$\mathfrak{m}$</jats:tex-math></jats:alternatives></jats:inline-formula> the maximal ideal and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline5" /><jats:tex-math>$F(x)\in \mathcal{O} [x] $</jats:tex-math></jats:alternatives></jats:inline-formula> a monic separable polynomial of degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline6" /><jats:tex-math>$n$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline7" /><jats:tex-math>$\delta = v(\mathrm{Disc} (F))$</jats:tex-math></jats:alternatives></jats:inline-formula>. The Montes algorithm computes an OM factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline8" /><jats:tex-math>$F$</jats:tex-math></jats:alternatives></jats:inline-formula>. The single-factor lifting algorithm derives from this data a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline9" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, for a prescribed precision <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline10" /><jats:tex-math>$\nu $</jats:tex-math></jats:alternatives></jats:inline-formula>. In this paper we find a new estimate for the complexity of the Montes algorithm, leading to an estimation of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline11" /><jats:tex-math>$O({n}^{2+ \epsilon } + {n}^{1+ \epsilon } {\delta }^{2+ \epsilon } + {n}^{2} {\nu }^{1+ \epsilon } )$</jats:tex-math></jats:alternatives></jats:inline-formula> word operations for the complexity of the computation of a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline12" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, assuming that the residue field of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline13" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> is small.</jats:p> |
| container_start_page |
139 |
| container_title |
LMS Journal of Computation and Mathematics |
| container_volume |
16 |
| format_de105 |
Article, E-Article |
| format_de14 |
Article, E-Article |
| format_de15 |
Article, E-Article |
| format_de520 |
Article, E-Article |
| format_de540 |
Article, E-Article |
| format_dech1 |
Article, E-Article |
| format_ded117 |
Article, E-Article |
| format_degla1 |
E-Article |
| format_del152 |
Buch |
| format_del189 |
Article, E-Article |
| format_dezi4 |
Article |
| format_dezwi2 |
Article, E-Article |
| format_finc |
Article, E-Article |
| format_nrw |
Article, E-Article |
| _version_ |
1792331643738914822 |
| geogr_code |
not assigned |
| last_indexed |
2024-03-01T13:42:35.735Z |
| geogr_code_person |
not assigned |
| openURL |
url_ver=Z39.88-2004&ctx_ver=Z39.88-2004&ctx_enc=info%3Aofi%2Fenc%3AUTF-8&rfr_id=info%3Asid%2Fvufind.svn.sourceforge.net%3Agenerator&rft.title=Complexity+of+OM+factorizations+of+polynomials+over+local+fields&rft.date=2013-01-01&genre=article&issn=1461-1570&volume=16&spage=139&epage=171&pages=139-171&jtitle=LMS+Journal+of+Computation+and+Mathematics&atitle=Complexity+of+OM+factorizations+of+polynomials+over+local+fields&aulast=Stainsby&aufirst=Hayden+D.&rft_id=info%3Adoi%2F10.1112%2Fs1461157013000089&rft.language%5B0%5D=eng |
| SOLR | |
| _version_ | 1792331643738914822 |
| author | Bauch, Jens-Dietrich, Nart, Enric, Stainsby, Hayden D. |
| author_facet | Bauch, Jens-Dietrich, Nart, Enric, Stainsby, Hayden D., Bauch, Jens-Dietrich, Nart, Enric, Stainsby, Hayden D. |
| author_sort | bauch, jens-dietrich |
| container_start_page | 139 |
| container_title | LMS Journal of Computation and Mathematics |
| container_volume | 16 |
| description | <jats:title>Abstract</jats:title><jats:p>Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline1" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> be a locally compact complete field with respect to a discrete valuation <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline2" /><jats:tex-math>$v$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline3" /><jats:tex-math>$ \mathcal{O} $</jats:tex-math></jats:alternatives></jats:inline-formula> be the valuation ring, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline4" /><jats:tex-math>$\mathfrak{m}$</jats:tex-math></jats:alternatives></jats:inline-formula> the maximal ideal and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline5" /><jats:tex-math>$F(x)\in \mathcal{O} [x] $</jats:tex-math></jats:alternatives></jats:inline-formula> a monic separable polynomial of degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline6" /><jats:tex-math>$n$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline7" /><jats:tex-math>$\delta = v(\mathrm{Disc} (F))$</jats:tex-math></jats:alternatives></jats:inline-formula>. The Montes algorithm computes an OM factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline8" /><jats:tex-math>$F$</jats:tex-math></jats:alternatives></jats:inline-formula>. The single-factor lifting algorithm derives from this data a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline9" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, for a prescribed precision <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline10" /><jats:tex-math>$\nu $</jats:tex-math></jats:alternatives></jats:inline-formula>. In this paper we find a new estimate for the complexity of the Montes algorithm, leading to an estimation of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline11" /><jats:tex-math>$O({n}^{2+ \epsilon } + {n}^{1+ \epsilon } {\delta }^{2+ \epsilon } + {n}^{2} {\nu }^{1+ \epsilon } )$</jats:tex-math></jats:alternatives></jats:inline-formula> word operations for the complexity of the computation of a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline12" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, assuming that the residue field of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline13" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> is small.</jats:p> |
| doi_str_mv | 10.1112/s1461157013000089 |
| facet_avail | Online, Free |
| finc_class_facet | Mathematik |
| format | ElectronicArticle |
| format_de105 | Article, E-Article |
| format_de14 | Article, E-Article |
| format_de15 | Article, E-Article |
| format_de520 | Article, E-Article |
| format_de540 | Article, E-Article |
| format_dech1 | Article, E-Article |
| format_ded117 | Article, E-Article |
| format_degla1 | E-Article |
| format_del152 | Buch |
| format_del189 | Article, E-Article |
| format_dezi4 | Article |
| format_dezwi2 | Article, E-Article |
| format_finc | Article, E-Article |
| format_nrw | Article, E-Article |
| geogr_code | not assigned |
| geogr_code_person | not assigned |
| id | ai-49-aHR0cDovL2R4LmRvaS5vcmcvMTAuMTExMi9zMTQ2MTE1NzAxMzAwMDA4OQ |
| imprint | Wiley, 2013 |
| imprint_str_mv | Wiley, 2013 |
| institution | DE-Bn3, DE-Brt1, DE-Zwi2, DE-D161, DE-Gla1, DE-Zi4, DE-15, DE-Rs1, DE-Pl11, DE-105, DE-14, DE-Ch1, DE-L229, DE-D275 |
| issn | 1461-1570 |
| issn_str_mv | 1461-1570 |
| language | English |
| last_indexed | 2024-03-01T13:42:35.735Z |
| match_str | bauch2013complexityofomfactorizationsofpolynomialsoverlocalfields |
| mega_collection | Wiley (CrossRef) |
| physical | 139-171 |
| publishDate | 2013 |
| publishDateSort | 2013 |
| publisher | Wiley |
| record_format | ai |
| recordtype | ai |
| series | LMS Journal of Computation and Mathematics |
| source_id | 49 |
| spelling | Bauch, Jens-Dietrich Nart, Enric Stainsby, Hayden D. 1461-1570 Wiley Computational Theory and Mathematics General Mathematics http://dx.doi.org/10.1112/s1461157013000089 <jats:title>Abstract</jats:title><jats:p>Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline1" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> be a locally compact complete field with respect to a discrete valuation <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline2" /><jats:tex-math>$v$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline3" /><jats:tex-math>$ \mathcal{O} $</jats:tex-math></jats:alternatives></jats:inline-formula> be the valuation ring, <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline4" /><jats:tex-math>$\mathfrak{m}$</jats:tex-math></jats:alternatives></jats:inline-formula> the maximal ideal and <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline5" /><jats:tex-math>$F(x)\in \mathcal{O} [x] $</jats:tex-math></jats:alternatives></jats:inline-formula> a monic separable polynomial of degree <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline6" /><jats:tex-math>$n$</jats:tex-math></jats:alternatives></jats:inline-formula>. Let <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline7" /><jats:tex-math>$\delta = v(\mathrm{Disc} (F))$</jats:tex-math></jats:alternatives></jats:inline-formula>. The Montes algorithm computes an OM factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline8" /><jats:tex-math>$F$</jats:tex-math></jats:alternatives></jats:inline-formula>. The single-factor lifting algorithm derives from this data a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline9" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, for a prescribed precision <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline10" /><jats:tex-math>$\nu $</jats:tex-math></jats:alternatives></jats:inline-formula>. In this paper we find a new estimate for the complexity of the Montes algorithm, leading to an estimation of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline11" /><jats:tex-math>$O({n}^{2+ \epsilon } + {n}^{1+ \epsilon } {\delta }^{2+ \epsilon } + {n}^{2} {\nu }^{1+ \epsilon } )$</jats:tex-math></jats:alternatives></jats:inline-formula> word operations for the complexity of the computation of a factorization of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline12" /><jats:tex-math>$F(\mathrm{mod~} {\mathfrak{m}}^{\nu } )$</jats:tex-math></jats:alternatives></jats:inline-formula>, assuming that the residue field of <jats:inline-formula><jats:alternatives><jats:inline-graphic xmlns:xlink="http://www.w3.org/1999/xlink" mime-subtype="gif" xlink:type="simple" xlink:href="S1461157013000089_inline13" /><jats:tex-math>$k$</jats:tex-math></jats:alternatives></jats:inline-formula> is small.</jats:p> Complexity of OM factorizations of polynomials over local fields LMS Journal of Computation and Mathematics |
| spellingShingle | Bauch, Jens-Dietrich, Nart, Enric, Stainsby, Hayden D., LMS Journal of Computation and Mathematics, Complexity of OM factorizations of polynomials over local fields, Computational Theory and Mathematics, General Mathematics |
| title | Complexity of OM factorizations of polynomials over local fields |
| title_full | Complexity of OM factorizations of polynomials over local fields |
| title_fullStr | Complexity of OM factorizations of polynomials over local fields |
| title_full_unstemmed | Complexity of OM factorizations of polynomials over local fields |
| title_short | Complexity of OM factorizations of polynomials over local fields |
| title_sort | complexity of om factorizations of polynomials over local fields |
| title_unstemmed | Complexity of OM factorizations of polynomials over local fields |
| topic | Computational Theory and Mathematics, General Mathematics |
| url | http://dx.doi.org/10.1112/s1461157013000089 |