A deterministic test for permutation polynomials
type: Item
instance of: scholarly article
title: A deterministic test for permutation polynomials
zbMATH Open document ID: 0766.11048
DOI: 10.1007/BF01202000
published in: Computational Complexity
publication date: 1993-04-01T00:00:00Z
review text: A deterministic algorithm is presented for testing whether a given polynomial of degree \(n\) over the finite field \(F_ q\) of order \(q\) is a permutation polynomial of \(F_ q\). The algorithm requires \(O((nq)^{6/7+\varepsilon})\) arithmetic operations in \(F_ q\). For \(q\leq 4n^ 6\) it suffices to use a test due to \textit{J. von zur Gathen} [SIAM J. Comput. 20, 591-602 (1991; Zbl 0733.11048)]. For \(q>4n^ 6\) a new test is developed, the proof of which depends on the bound of \textit{E. Bombieri} [Am. J. Math. 88, 71-105 (1966; Zbl 0171.415)] for exponential sums along curves over finite fields.
reviewed by: Harald Niederreiter
Mathematics Subject Classification ID: 11T06
Mathematics Subject Classification ID: 68W30
Mathematics Subject Classification ID: 11Y16
zbMATH DE Number: 149535
zbMATH Keywords: deterministic algorithm
zbMATH Keywords: finite field
zbMATH Keywords: permutation polynomial
author: Igor E. Shparlinski
MaRDI profile type: Publication
cites work: On Exponential Sums in Finite Fields
cites work: Tests for Permutation Polynomials
cites work: Values of polynomials over finite fields
cites work: When Does a Polynomial Over a Finite Field Permute the Elements of the Field?
cites work: Frobenius Maps of Abelian Varieties and Finding Roots of Unity in Finite Fields
cites work: A method for obtaining digital signatures and public-key cryptosystems
cites work: Q3137899
full work available at URL: https://doi.org/10.1007/bf01202000
OpenAlex ID: W1970367963
Recommended article: Tests for Permutation Polynomials
Recommended article: On the Detection of Permutation Polynomials
Recommended article: A new criterion for permutation polynomials
Recommended article: Tests for permutation functions
Recommended article: Q4471369
Recommended article: On permutation polynomials
Recommended article: On piece-wise permutation polynomials
Recommended article: A note on constructing permutation polynomials
Recommended article: Q4395650
Recommended article: On a Problem Concerning Permutation Polynomials
description: scientific article; zbMATH DE number 149535