Loading…
Faster Polynomial Multiplication over Finite Fields
Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let p be a prime, and let M p ( n ) denote the bit complexity of multiplying two polynomials...
Saved in:
| Published in: | Journal of the ACM 2017-02, Vol.63 (6), p.1-23 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | English |
| Subjects: | |
| Citations: | Items that this one cites Items that cite this one |
| Online Access: | Get full text |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| cited_by | cdi_FETCH-LOGICAL-c353t-f827f08c38aaecb1f7abad7527244a447c31b404cc61e43c8d56f05249424c3b3 |
|---|---|
| cites | cdi_FETCH-LOGICAL-c353t-f827f08c38aaecb1f7abad7527244a447c31b404cc61e43c8d56f05249424c3b3 |
| container_end_page | 23 |
| container_issue | 6 |
| container_start_page | 1 |
| container_title | Journal of the ACM |
| container_volume | 63 |
| creator | Harvey, David Hoeven, Joris Van Der Lecerf, Grégoire |
| description | Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let
p
be a prime, and let M
p
(
n
) denote the bit complexity of multiplying two polynomials in F
p
[
X
] of degree less than
n
. For
n
large compared to
p
, we establish the bound M
p
(
n
) =
O
(
n
log
n
8
log*
n
log
p
), where log
*
n
= min{
k
ϵ N: log …
k
×
… log
n
≤ 1} stands for the iterated logarithm. This improves on the previously best known bound M
p
(
n
) =
O
(
n
log
n
log log
n
log
p
), which essentially goes back to the 1970s. |
| doi_str_mv | 10.1145/3005344 |
| format | article |
| fullrecord | <record><control><sourceid>proquest_hal_p</sourceid><recordid>TN_cdi_hal_primary_oai_HAL_hal_02350386v1</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>4314249161</sourcerecordid><originalsourceid>FETCH-LOGICAL-c353t-f827f08c38aaecb1f7abad7527244a447c31b404cc61e43c8d56f05249424c3b3</originalsourceid><addsrcrecordid>eNpdkEFLAzEQhYMoWKv4Fwoe1MNqsjPZpMdSrBUqelDwFrJpFlPSTU12C_33prR48PSYmW-GN4-Qa0YfGEP-CJRyQDwhA8a5KATwr1MyoJRiwZGxc3KR0iqXtKRiQGCmU2fj6D34XRvWTvvRa-87t_HO6M6FdhS2eTxzretsFuuX6ZKcNdone3XUIfmcPX1M58Xi7fllOlkUBjh0RSNL0VBpQGptTc0aoWu9FLwUJaJGFAZYjRSNqZhFMHLJq4byEsdYooEahuT-cPdbe7WJbq3jTgXt1HyyUPseLYFTkNWWZfbuwG5i-Olt6tTaJWO9160NfVJMjkGOKc8rQ3LzD12FPrb5k0xVkjMhpczU7YEyMaQUbfPngFG1D1odg4ZfpmBsTw</addsrcrecordid><sourcetype>Open Access Repository</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>1868517888</pqid></control><display><type>article</type><title>Faster Polynomial Multiplication over Finite Fields</title><source>Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list)</source><source>BSC - Ebsco (Business Source Ultimate)</source><creator>Harvey, David ; Hoeven, Joris Van Der ; Lecerf, Grégoire</creator><creatorcontrib>Harvey, David ; Hoeven, Joris Van Der ; Lecerf, Grégoire</creatorcontrib><description>Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let
p
be a prime, and let M
p
(
n
) denote the bit complexity of multiplying two polynomials in F
p
[
X
] of degree less than
n
. For
n
large compared to
p
, we establish the bound M
p
(
n
) =
O
(
n
log
n
8
log*
n
log
p
), where log
*
n
= min{
k
ϵ N: log …
k
×
… log
n
≤ 1} stands for the iterated logarithm. This improves on the previously best known bound M
p
(
n
) =
O
(
n
log
n
log log
n
log
p
), which essentially goes back to the 1970s.</description><identifier>ISSN: 0004-5411</identifier><identifier>EISSN: 1557-735X</identifier><identifier>DOI: 10.1145/3005344</identifier><identifier>CODEN: JACOAH</identifier><language>eng</language><publisher>New York: Association for Computing Machinery</publisher><subject>Algebra ; Algorithms ; Complexity ; Computer Science ; Cryptography ; Error correcting codes ; Logarithms ; Mathematical analysis ; Mathematical Software ; Polynomials ; Stands ; Studies</subject><ispartof>Journal of the ACM, 2017-02, Vol.63 (6), p.1-23</ispartof><rights>Copyright Association for Computing Machinery Feb 2017</rights><rights>Distributed under a Creative Commons Attribution 4.0 International License</rights><lds50>peer_reviewed</lds50><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c353t-f827f08c38aaecb1f7abad7527244a447c31b404cc61e43c8d56f05249424c3b3</citedby><cites>FETCH-LOGICAL-c353t-f827f08c38aaecb1f7abad7527244a447c31b404cc61e43c8d56f05249424c3b3</cites><orcidid>0000-0003-2244-1897 ; 0000-0002-6066-6707</orcidid></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><link.rule.ids>230,314,780,784,885,27924,27925</link.rule.ids><backlink>$$Uhttps://hal.science/hal-02350386$$DView record in HAL$$Hfree_for_read</backlink></links><search><creatorcontrib>Harvey, David</creatorcontrib><creatorcontrib>Hoeven, Joris Van Der</creatorcontrib><creatorcontrib>Lecerf, Grégoire</creatorcontrib><title>Faster Polynomial Multiplication over Finite Fields</title><title>Journal of the ACM</title><description>Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let
p
be a prime, and let M
p
(
n
) denote the bit complexity of multiplying two polynomials in F
p
[
X
] of degree less than
n
. For
n
large compared to
p
, we establish the bound M
p
(
n
) =
O
(
n
log
n
8
log*
n
log
p
), where log
*
n
= min{
k
ϵ N: log …
k
×
… log
n
≤ 1} stands for the iterated logarithm. This improves on the previously best known bound M
p
(
n
) =
O
(
n
log
n
log log
n
log
p
), which essentially goes back to the 1970s.</description><subject>Algebra</subject><subject>Algorithms</subject><subject>Complexity</subject><subject>Computer Science</subject><subject>Cryptography</subject><subject>Error correcting codes</subject><subject>Logarithms</subject><subject>Mathematical analysis</subject><subject>Mathematical Software</subject><subject>Polynomials</subject><subject>Stands</subject><subject>Studies</subject><issn>0004-5411</issn><issn>1557-735X</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2017</creationdate><recordtype>article</recordtype><recordid>eNpdkEFLAzEQhYMoWKv4Fwoe1MNqsjPZpMdSrBUqelDwFrJpFlPSTU12C_33prR48PSYmW-GN4-Qa0YfGEP-CJRyQDwhA8a5KATwr1MyoJRiwZGxc3KR0iqXtKRiQGCmU2fj6D34XRvWTvvRa-87t_HO6M6FdhS2eTxzretsFuuX6ZKcNdone3XUIfmcPX1M58Xi7fllOlkUBjh0RSNL0VBpQGptTc0aoWu9FLwUJaJGFAZYjRSNqZhFMHLJq4byEsdYooEahuT-cPdbe7WJbq3jTgXt1HyyUPseLYFTkNWWZfbuwG5i-Olt6tTaJWO9160NfVJMjkGOKc8rQ3LzD12FPrb5k0xVkjMhpczU7YEyMaQUbfPngFG1D1odg4ZfpmBsTw</recordid><startdate>20170201</startdate><enddate>20170201</enddate><creator>Harvey, David</creator><creator>Hoeven, Joris Van Der</creator><creator>Lecerf, Grégoire</creator><general>Association for Computing Machinery</general><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope><scope>1XC</scope><orcidid>https://orcid.org/0000-0003-2244-1897</orcidid><orcidid>https://orcid.org/0000-0002-6066-6707</orcidid></search><sort><creationdate>20170201</creationdate><title>Faster Polynomial Multiplication over Finite Fields</title><author>Harvey, David ; Hoeven, Joris Van Der ; Lecerf, Grégoire</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c353t-f827f08c38aaecb1f7abad7527244a447c31b404cc61e43c8d56f05249424c3b3</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2017</creationdate><topic>Algebra</topic><topic>Algorithms</topic><topic>Complexity</topic><topic>Computer Science</topic><topic>Cryptography</topic><topic>Error correcting codes</topic><topic>Logarithms</topic><topic>Mathematical analysis</topic><topic>Mathematical Software</topic><topic>Polynomials</topic><topic>Stands</topic><topic>Studies</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Harvey, David</creatorcontrib><creatorcontrib>Hoeven, Joris Van Der</creatorcontrib><creatorcontrib>Lecerf, Grégoire</creatorcontrib><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><collection>Hyper Article en Ligne (HAL)</collection><jtitle>Journal of the ACM</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Harvey, David</au><au>Hoeven, Joris Van Der</au><au>Lecerf, Grégoire</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>Faster Polynomial Multiplication over Finite Fields</atitle><jtitle>Journal of the ACM</jtitle><date>2017-02-01</date><risdate>2017</risdate><volume>63</volume><issue>6</issue><spage>1</spage><epage>23</epage><pages>1-23</pages><issn>0004-5411</issn><eissn>1557-735X</eissn><coden>JACOAH</coden><abstract>Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let
p
be a prime, and let M
p
(
n
) denote the bit complexity of multiplying two polynomials in F
p
[
X
] of degree less than
n
. For
n
large compared to
p
, we establish the bound M
p
(
n
) =
O
(
n
log
n
8
log*
n
log
p
), where log
*
n
= min{
k
ϵ N: log …
k
×
… log
n
≤ 1} stands for the iterated logarithm. This improves on the previously best known bound M
p
(
n
) =
O
(
n
log
n
log log
n
log
p
), which essentially goes back to the 1970s.</abstract><cop>New York</cop><pub>Association for Computing Machinery</pub><doi>10.1145/3005344</doi><tpages>23</tpages><orcidid>https://orcid.org/0000-0003-2244-1897</orcidid><orcidid>https://orcid.org/0000-0002-6066-6707</orcidid><oa>free_for_read</oa></addata></record> |
| fulltext | fulltext |
| identifier | ISSN: 0004-5411 |
| ispartof | Journal of the ACM, 2017-02, Vol.63 (6), p.1-23 |
| issn | 0004-5411 1557-735X |
| language | eng |
| recordid | cdi_hal_primary_oai_HAL_hal_02350386v1 |
| source | Association for Computing Machinery:Jisc Collections:ACM OPEN Journals 2023-2025 (reading list); BSC - Ebsco (Business Source Ultimate) |
| subjects | Algebra Algorithms Complexity Computer Science Cryptography Error correcting codes Logarithms Mathematical analysis Mathematical Software Polynomials Stands Studies |
| title | Faster Polynomial Multiplication over Finite Fields |
| url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T22%3A51%3A44IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_hal_p&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=Faster%20Polynomial%20Multiplication%20over%20Finite%20Fields&rft.jtitle=Journal%20of%20the%20ACM&rft.au=Harvey,%20David&rft.date=2017-02-01&rft.volume=63&rft.issue=6&rft.spage=1&rft.epage=23&rft.pages=1-23&rft.issn=0004-5411&rft.eissn=1557-735X&rft.coden=JACOAH&rft_id=info:doi/10.1145/3005344&rft_dat=%3Cproquest_hal_p%3E4314249161%3C/proquest_hal_p%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c353t-f827f08c38aaecb1f7abad7527244a447c31b404cc61e43c8d56f05249424c3b3%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=1868517888&rft_id=info:pmid/&rfr_iscdi=true |