Polynomial evaluation over finite fields: new algorithmsand complexity bounds

Elia, Michele; Rosenthal, J.; Schipani, D.

doi:10.1007/s00200-011-0160-6

An efficient evaluation method is described for polynomials in finite fields. Its complexity is shown to be lower than that of standard techniques, when the degree of the polynomial is large enough compared to the field characteristic. Specifically, if n is the degree of the polynomiaI, the asymptotic complexity is shown to be O(√n), versus O(n) of classical algorithms. Applications to the syndrome computation in the decoding of Reed-Solomon codes are highlighted.

Polynomial evaluation over finite fields: new algorithmsand complexity bounds / Elia m.; Rosenthal J.; Schipani D.. - In: APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING. - ISSN 0938-1279. - STAMPA. - 23:3(2012), pp. 129-141. [10.1007/s00200-011-0160-6]

Titolo:	Polynomial evaluation over finite fields: new algorithmsand complexity bounds
Autori:	ELIA, Michele Rosenthal J. Schipani D. mostra contributor esterni nascondi contributor esterni
Data di pubblicazione:	2012
Rivista:	APPLICABLE ALGEBRA IN ENGINEERING COMMUNICATION AND COMPUTING
Digital Object Identifier (DOI):	http://dx.doi.org/10.1007/s00200-011-0160-6
Appare nelle tipologie:	1.1 Articolo in rivista

File in questo prodotto:

File	Descrizione	Tipologia	Licenza
POLY48.pdf		1. Preprint / submitted version [pre- review]	Non Pubblico - Accesso privato/ristretto	Administrator Richiedi una copia

Utilizza questo identificativo per citare o creare un link a questo documento:
http://hdl.handle.net/11583/2496726

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

PORTO @ Archivio Istituzionale della Ricerca

File in questo prodotto: