A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields

Pingping Li; Leilei Yu; Linqi Song; Hanxu Hou

doi:10.1109/WCSP58612.2023.10404656

A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields

Pingping Li, Leilei Yu, Linqi Song, Hanxu Hou^*

^*Corresponding author for this work

Department of Computer Science

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

Abstract

Finding all roots of polynomials over finite fields is a crucial problem in algebraic coding techniques, such as decoding BCH codes and Reed-Solomon codes. The current commonly used methods are Chien search or fast Fourier transform (FFT), which evaluates all elements in a finite field and results in field multiplications whose number increases linearly with the field size. In this paper, we propose a new approach that enables the multiplicative complexity to grow sub-linearly with the field size. To our knowledge, this is the currently lowest multiplicative complexity for this problem. Additionally, the proposed approach maintains the additive complexity similar to that of FFT-based method. © 2023 IEEE.

Original language	English
Title of host publication	2023 IEEE the 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023)
Publisher	IEEE
Pages	299-304
ISBN (Electronic)	9798350324662, 9798350324655
ISBN (Print)	9798350324679
DOIs	https://doi.org/10.1109/WCSP58612.2023.10404656
Publication status	Published - Nov 2023
Event	15th International Conference on Wireless Communications and Signal Processing (WCSP 2023) - Huabei Hotel, Hangzhou, China Duration: 2 Nov 2023 → 4 Nov 2023 http://www.ic-wcsp.org/2023/show.asp?id=21

Publication series

Name	IEEE International Conference on Wireless Communications and Signal Processing, WCSP

Conference

Conference	15th International Conference on Wireless Communications and Signal Processing (WCSP 2023)
Place	China
City	Hangzhou
Period	2/11/23 → 4/11/23
Internet address	http://www.ic-wcsp.org/2023/show.asp?id=21

Research Keywords

error-correction codes
error-locator polynomial
fast Fourier transforms (FFT)
Polynomial evaluation

Access Output

10.1109/WCSP58612.2023.10404656

Other Access Options

Check CityUHK Library

Permanent Link

Right click to copy link

Cite this

Li, P., Yu, L., Song, L., & Hou, H. (2023). A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields. In 2023 IEEE the 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023) (pp. 299-304). (IEEE International Conference on Wireless Communications and Signal Processing, WCSP). IEEE. https://doi.org/10.1109/WCSP58612.2023.10404656

@inproceedings{ae975d25a4254d56abd4268b04e19cd7,

title = "A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields",

abstract = "Finding all roots of polynomials over finite fields is a crucial problem in algebraic coding techniques, such as decoding BCH codes and Reed-Solomon codes. The current commonly used methods are Chien search or fast Fourier transform (FFT), which evaluates all elements in a finite field and results in field multiplications whose number increases linearly with the field size. In this paper, we propose a new approach that enables the multiplicative complexity to grow sub-linearly with the field size. To our knowledge, this is the currently lowest multiplicative complexity for this problem. Additionally, the proposed approach maintains the additive complexity similar to that of FFT-based method. {\textcopyright} 2023 IEEE.",

keywords = "error-correction codes, error-locator polynomial, fast Fourier transforms (FFT), Polynomial evaluation",

author = "Pingping Li and Leilei Yu and Linqi Song and Hanxu Hou",

year = "2023",

month = nov,

doi = "10.1109/WCSP58612.2023.10404656",

language = "English",

isbn = "9798350324679",

series = "IEEE International Conference on Wireless Communications and Signal Processing, WCSP",

publisher = "IEEE",

pages = "299--304",

booktitle = "2023 IEEE the 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023)",

address = "United States",

note = "15th International Conference on Wireless Communications and Signal Processing (WCSP 2023) ; Conference date: 02-11-2023 Through 04-11-2023",

url = "http://www.ic-wcsp.org/2023/show.asp?id=21",

}

Li, P, Yu, L, Song, L & Hou, H 2023, A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields. in 2023 IEEE the 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023). IEEE International Conference on Wireless Communications and Signal Processing, WCSP, IEEE, pp. 299-304, 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023), Hangzhou, China, 2/11/23. https://doi.org/10.1109/WCSP58612.2023.10404656

A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields. / Li, Pingping; Yu, Leilei; Song, Linqi et al.
2023 IEEE the 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023). IEEE, 2023. p. 299-304 (IEEE International Conference on Wireless Communications and Signal Processing, WCSP).

Research output: Chapters, Conference Papers, Creative and Literary Works › RGC 32 - Refereed conference paper (with host publication) › peer-review

TY - GEN

T1 - A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields

AU - Li, Pingping

AU - Yu, Leilei

AU - Song, Linqi

AU - Hou, Hanxu

PY - 2023/11

Y1 - 2023/11

N2 - Finding all roots of polynomials over finite fields is a crucial problem in algebraic coding techniques, such as decoding BCH codes and Reed-Solomon codes. The current commonly used methods are Chien search or fast Fourier transform (FFT), which evaluates all elements in a finite field and results in field multiplications whose number increases linearly with the field size. In this paper, we propose a new approach that enables the multiplicative complexity to grow sub-linearly with the field size. To our knowledge, this is the currently lowest multiplicative complexity for this problem. Additionally, the proposed approach maintains the additive complexity similar to that of FFT-based method. © 2023 IEEE.

AB - Finding all roots of polynomials over finite fields is a crucial problem in algebraic coding techniques, such as decoding BCH codes and Reed-Solomon codes. The current commonly used methods are Chien search or fast Fourier transform (FFT), which evaluates all elements in a finite field and results in field multiplications whose number increases linearly with the field size. In this paper, we propose a new approach that enables the multiplicative complexity to grow sub-linearly with the field size. To our knowledge, this is the currently lowest multiplicative complexity for this problem. Additionally, the proposed approach maintains the additive complexity similar to that of FFT-based method. © 2023 IEEE.

KW - error-correction codes

KW - error-locator polynomial

KW - fast Fourier transforms (FFT)

KW - Polynomial evaluation

UR - http://www.scopus.com/inward/record.url?scp=85185873262&partnerID=8YFLogxK

UR - https://www.scopus.com/record/pubmetrics.uri?eid=2-s2.0-85185873262&origin=recordpage

U2 - 10.1109/WCSP58612.2023.10404656

DO - 10.1109/WCSP58612.2023.10404656

M3 - RGC 32 - Refereed conference paper (with host publication)

SN - 9798350324679

T3 - IEEE International Conference on Wireless Communications and Signal Processing, WCSP

SP - 299

EP - 304

BT - 2023 IEEE the 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023)

PB - IEEE

T2 - 15th International Conference on Wireless Communications and Signal Processing (WCSP 2023)

Y2 - 2 November 2023 through 4 November 2023

ER -

A Fast Algorithm for Finding the Roots of Polynomials over Finite Fields

Abstract

Publication series

Conference

Research Keywords

Access Output

Other Access Options

Permanent Link

Other Files and Links

Fingerprint

Cite this