The computational complexity of recognizing permutation functions

DOI10.1007/BF01277957zbMath0816.68071OpenAlexW2007756980MaRDI QIDQ5917358

Joachim von zur Gathen, Keju Ma

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) Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Factoring multivariate polynomials over finite fields
• Fast parallel absolute irreducibility testing
• Probabilistic algorithm for testing primality
• On fast multiplication of polynomials over arbitrary algebras
• Primality testing and Abelian varieties over finite fields
• A deterministic test for permutation polynomials
• Riemann's hypothesis and tests for primality
• Deterministic irreducibility testing of polynomials over large finite fields
• A geometric approach to permutation polynomials over a finite field
• Fast multiplication of large numbers
• Tests for Permutation Polynomials
• Values of polynomials over finite fields
• Factorization of Multivariate 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
• Every Prime Has a Succinct Certificate
• A Fast Monte-Carlo Test for Primality
• Counting curves and their projections
• On Bivariate Polynomial Factorization over Finite Fields
• On Exceptional Polynomials
• On a conjecture of Davenport and Lewis concerning exceptional polynomials
• On Exponential Sums in Finite Fields
• The distribution of polynomials over finite fields
• NOTES ON CONGRUENCES (I)