Loading…
Univariate polynomial factorization over finite fields with large extension degree
The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with d 1.5 + o ( 1 ) for input polynomials of degree d , and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast...
Saved in:
| Published in: | Applicable algebra in engineering, communication and computing communication and computing, 2024-03, Vol.35 (2), p.121-149 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | |
|---|---|
| cites | cdi_FETCH-LOGICAL-c314t-e6cd89b24dc9d0fc41f4ceaeab713c5de1d95c58588249698b3c76116cbae6333 |
| container_end_page | 149 |
| container_issue | 2 |
| container_start_page | 121 |
| container_title | Applicable algebra in engineering, communication and computing |
| container_volume | 35 |
| creator | Hoeven, Joris van der Lecerf, Grégoire |
| description | The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with
d
1.5
+
o
(
1
)
for input polynomials of degree
d
, and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth. |
| doi_str_mv | 10.1007/s00200-021-00536-1 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_journals_2929956596</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2929956596</sourcerecordid><originalsourceid>FETCH-LOGICAL-c314t-e6cd89b24dc9d0fc41f4ceaeab713c5de1d95c58588249698b3c76116cbae6333</originalsourceid><addsrcrecordid>eNp9kF9LwzAUR4MoOKdfwKeCz9GbpE2bRxn-g4Eg7jmk6e3M6JqZZNP56e2s4JtP9-Wc34VDyCWDawZQ3kQADkCBMwpQCEnZEZmwXHAKkvNjMgElKsp4qU7JWYwrAJAqLyfkZdG7nQnOJMw2vtv3fu1Ml7XGJh_cl0nO95nfYcha17sBah12Tcw-XHrLOhOWmOFnwj4euAaXAfGcnLSmi3jxe6dkcX_3Onuk8-eHp9ntnFrB8kRR2qZSNc8bqxpobc7a3KJBU5dM2KJB1qjCFlVRVTxXUlW1sKVkTNraoBRCTMnVuLsJ_n2LMemV34Z-eKm54koVslByoPhI2eBjDNjqTXBrE_aagT6002M7PbTTP-00GyQxSnGA-yWGv-l_rG-1CHMU</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2929956596</pqid></control><display><type>article</type><title>Univariate polynomial factorization over finite fields with large extension degree</title><source>Springer Link</source><creator>Hoeven, Joris van der ; Lecerf, Grégoire</creator><creatorcontrib>Hoeven, Joris van der ; Lecerf, Grégoire</creatorcontrib><description>The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with
d
1.5
+
o
(
1
)
for input polynomials of degree
d
, and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth.</description><identifier>ISSN: 0938-1279</identifier><identifier>EISSN: 1432-0622</identifier><identifier>DOI: 10.1007/s00200-021-00536-1</identifier><language>eng</language><publisher>Berlin/Heidelberg: Springer Berlin Heidelberg</publisher><subject>Algorithms ; Artificial Intelligence ; Computer Hardware ; Computer Science ; Fields (mathematics) ; Original Paper ; Polynomials ; Symbolic and Algebraic Manipulation ; Theory of Computation</subject><ispartof>Applicable algebra in engineering, communication and computing, 2024-03, Vol.35 (2), p.121-149</ispartof><rights>The Author(s), under exclusive licence to Springer-Verlag GmbH Germany, part of Springer Nature 2022. corrected publication 2024. Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><cites>FETCH-LOGICAL-c314t-e6cd89b24dc9d0fc41f4ceaeab713c5de1d95c58588249698b3c76116cbae6333</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>314,780,784,27924,27925</link.rule.ids></links><search><creatorcontrib>Hoeven, Joris van der</creatorcontrib><creatorcontrib>Lecerf, Grégoire</creatorcontrib><title>Univariate polynomial factorization over finite fields with large extension degree</title><title>Applicable algebra in engineering, communication and computing</title><addtitle>AAECC</addtitle><description>The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with
d
1.5
+
o
(
1
)
for input polynomials of degree
d
, and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth.</description><subject>Algorithms</subject><subject>Artificial Intelligence</subject><subject>Computer Hardware</subject><subject>Computer Science</subject><subject>Fields (mathematics)</subject><subject>Original Paper</subject><subject>Polynomials</subject><subject>Symbolic and Algebraic Manipulation</subject><subject>Theory of Computation</subject><issn>0938-1279</issn><issn>1432-0622</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2024</creationdate><recordtype>article</recordtype><recordid>eNp9kF9LwzAUR4MoOKdfwKeCz9GbpE2bRxn-g4Eg7jmk6e3M6JqZZNP56e2s4JtP9-Wc34VDyCWDawZQ3kQADkCBMwpQCEnZEZmwXHAKkvNjMgElKsp4qU7JWYwrAJAqLyfkZdG7nQnOJMw2vtv3fu1Ml7XGJh_cl0nO95nfYcha17sBah12Tcw-XHrLOhOWmOFnwj4euAaXAfGcnLSmi3jxe6dkcX_3Onuk8-eHp9ntnFrB8kRR2qZSNc8bqxpobc7a3KJBU5dM2KJB1qjCFlVRVTxXUlW1sKVkTNraoBRCTMnVuLsJ_n2LMemV34Z-eKm54koVslByoPhI2eBjDNjqTXBrE_aagT6002M7PbTTP-00GyQxSnGA-yWGv-l_rG-1CHMU</recordid><startdate>20240301</startdate><enddate>20240301</enddate><creator>Hoeven, Joris van der</creator><creator>Lecerf, Grégoire</creator><general>Springer Berlin Heidelberg</general><general>Springer Nature B.V</general><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>20240301</creationdate><title>Univariate polynomial factorization over finite fields with large extension degree</title><author>Hoeven, Joris van der ; Lecerf, Grégoire</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c314t-e6cd89b24dc9d0fc41f4ceaeab713c5de1d95c58588249698b3c76116cbae6333</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2024</creationdate><topic>Algorithms</topic><topic>Artificial Intelligence</topic><topic>Computer Hardware</topic><topic>Computer Science</topic><topic>Fields (mathematics)</topic><topic>Original Paper</topic><topic>Polynomials</topic><topic>Symbolic and Algebraic Manipulation</topic><topic>Theory of Computation</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Hoeven, Joris van der</creatorcontrib><creatorcontrib>Lecerf, Grégoire</creatorcontrib><collection>CrossRef</collection><jtitle>Applicable algebra in engineering, communication and computing</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Hoeven, Joris van der</au><au>Lecerf, Grégoire</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Univariate polynomial factorization over finite fields with large extension degree</atitle><jtitle>Applicable algebra in engineering, communication and computing</jtitle><stitle>AAECC</stitle><date>2024-03-01</date><risdate>2024</risdate><volume>35</volume><issue>2</issue><spage>121</spage><epage>149</epage><pages>121-149</pages><issn>0938-1279</issn><eissn>1432-0622</eissn><abstract>The best known asymptotic bit complexity bound for factoring univariate polynomials over finite fields grows with
d
1.5
+
o
(
1
)
for input polynomials of degree
d
, and with the square of the bit size of the ground field. It relies on a variant of the Cantor–Zassenhaus algorithm which exploits fast modular composition. Using techniques by Kaltofen and Shoup, we prove a refinement of this bound when the finite field has a large extension degree over its prime field. We also present fast practical algorithms for the case when the extension degree is smooth.</abstract><cop>Berlin/Heidelberg</cop><pub>Springer Berlin Heidelberg</pub><doi>10.1007/s00200-021-00536-1</doi><tpages>29</tpages><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0938-1279 |
| ispartof | Applicable algebra in engineering, communication and computing, 2024-03, Vol.35 (2), p.121-149 |
| issn | 0938-1279 1432-0622 |
| language | eng |
| recordid | cdi_proquest_journals_2929956596 |
| source | Springer Link |
| subjects | Algorithms Artificial Intelligence Computer Hardware Computer Science Fields (mathematics) Original Paper Polynomials Symbolic and Algebraic Manipulation Theory of Computation |
| title | Univariate polynomial factorization over finite fields with large extension degree |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T22%3A58%3A51IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Univariate%20polynomial%20factorization%20over%20finite%20fields%20with%20large%20extension%20degree&rft.jtitle=Applicable%20algebra%20in%20engineering,%20communication%20and%20computing&rft.au=Hoeven,%20Joris%20van%20der&rft.date=2024-03-01&rft.volume=35&rft.issue=2&rft.spage=121&rft.epage=149&rft.pages=121-149&rft.issn=0938-1279&rft.eissn=1432-0622&rft_id=info:doi/10.1007/s00200-021-00536-1&rft_dat=%3Cproquest_cross%3E2929956596%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c314t-e6cd89b24dc9d0fc41f4ceaeab713c5de1d95c58588249698b3c76116cbae6333%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2929956596&rft_id=info:pmid/&rfr_iscdi=true |