The computational complexity of recognizing permutation functions

DOI10.1007/BF01277957MaRDI QIDQ5917358zbMATH OpenOpenAlexFDO

Authors Keju Ma, Joachim von zur Gathen

Publication date 11 July 1995

Published in Computational Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01277957

zbMATH Keywords

probabilistic test

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Number-theoretic algorithms; complexity (11Y16)

Recommendations

• The computational complexity of recognizing permutation functions
• Tests for permutation functions
• scientific article; zbMATH DE number 4152523
• Tests for Permutation Polynomials
• A deterministic test for permutation polynomials

Cites work

• scientific article; zbMATH DE number 426128 (Why is no real title available?)
• scientific article; zbMATH DE number 426134 (Why is no real title available?)
• scientific article; zbMATH DE number 429512 (Why is no real title available?)
• scientific article; zbMATH DE number 3839766 (Why is no real title available?)
• scientific article; zbMATH DE number 3511563 (Why is no real title available?)
• scientific article; zbMATH DE number 3804835 (Why is no real title available?)
• scientific article; zbMATH DE number 3221520 (Why is no real title available?)
• A Fast Monte-Carlo Test for Primality
• A deterministic test for permutation polynomials
• A geometric approach to permutation polynomials over a finite field
• Counting curves and their projections
• Deterministic irreducibility testing of polynomials over large finite fields
• Every Prime Has a Succinct Certificate
• Factoring multivariate polynomials over finite fields
• Factorization of Multivariate Polynomials Over Finite Fields
• Fast multiplication of large numbers
• Fast parallel absolute irreducibility testing
• NOTES ON CONGRUENCES (I)
• On Bivariate Polynomial Factorization over Finite Fields
• On Exceptional Polynomials
• On Exponential Sums in Finite Fields
• On a conjecture of Davenport and Lewis concerning exceptional polynomials
• On fast multiplication of polynomials over arbitrary algebras
• Primality testing and Abelian varieties over finite fields
• Probabilistic algorithm for testing primality
• Riemann's hypothesis and tests for primality
• Tests for Permutation Polynomials
• The distribution of polynomials over finite fields
• Values of polynomials over finite fields
• When Does a Polynomial Over a Finite Field Permute the Elements of the Field?
• When Does a Polynomial over a Finite Field Permute the Elements of the Field?, II

Cited in

(5)

• State complexity of permutation and related decision problems on alphabetical pattern constraints
• Tests for Permutation Polynomials
• On the arithmetic complexity of Euler function
• Tests for permutation functions
• The computational complexity of recognizing permutation functions

This page was built for publication: The computational complexity of recognizing permutation functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5917358)