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 | |||
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
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