Tests for permutation functions (Q1344091): Difference between revisions

From MaRDI portal
Added link to MaRDI item.
Normalize DOI.
 
(4 intermediate revisions by 4 users not shown)
Property / DOI
 
Property / DOI: 10.1006/ffta.1995.1003 / rank
Normal rank
 
Property / MaRDI profile type
 
Property / MaRDI profile type: MaRDI publication profile / rank
 
Normal rank
Property / full work available at URL
 
Property / full work available at URL: https://doi.org/10.1006/ffta.1995.1003 / rank
 
Normal rank
Property / OpenAlex ID
 
Property / OpenAlex ID: W1981913693 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1006/FFTA.1995.1003 / rank
 
Normal rank

Latest revision as of 18:29, 10 December 2024

scientific article
Language Label Description Also known as
English
Tests for permutation functions
scientific article

    Statements

    Tests for permutation functions (English)
    0 references
    0 references
    0 references
    9 February 1995
    0 references
    For \(q\) a prime power, let \(\mathbb{F}_ q\) denote the finite field of order \(q\) and let \(f\in \mathbb{F}_ q (x)\) be a rational function over \(\mathbb{F}_ q\). \(D\subseteq \mathbb{F}_ q\) will denote the domain of definition of \(f\). In recent years many papers have been written concerning permutation polynomials over \(\mathbb{F}_ q\), i.e. permutations which are induced by polynomials over \(\mathbb{F}_ q\). In this paper the authors consider several more general settings and study three notions of permutation function: (i) \(f\) is a permutation of \(\mathbb{F}_ q\); (ii) \(f\) is a permutation on \(D\); (iii) \(f\) is injective on \(D\). The paper contains many detailed results concerning each of these notions of permutation function as well as their inter-connections. In particular for each of them, a random polynomial-time algorithm test is presented. In addition, for the image or value set size of an arbitrary rational function, a fully polynomial-time randomized approximation scheme is given. Finally the paper concludes with a list of five open questions.
    0 references
    finite field
    0 references
    permutation polynomials
    0 references
    permutation function
    0 references
    random polynomial-time algorithm test
    0 references
    polynomial-time randomized approximation scheme
    0 references
    open questions
    0 references

    Identifiers