Probabilistic Algorithms in Finite Fields
From MaRDI portal
Publication:3910619
DOI10.1137/0209024zbMath0461.12012DBLPjournals/siamcomp/Rabin80OpenAlexW2007643787WikidataQ56003480 ScholiaQ56003480MaRDI QIDQ3910619
Publication date: 1980
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0209024
Analysis of algorithms and problem complexity (68Q25) Polynomials over finite fields (11T06) Normal numbers, radix expansions, Pisot numbers, Salem numbers, good lattice points, etc. (11K16) Arithmetic theory of polynomial rings over finite fields (11T55) Software, source code, etc. for problems pertaining to field theory (12-04)
Related Items (63)
On the period length of generalized inversive pseudorandom number generators ⋮ Irreducibility of multivariate polynomials ⋮ Complete divisibility problems for slowly utilized oracles ⋮ Computing Frobenius maps and factoring polynomials ⋮ Constructing irreducible polynomials over finite fields ⋮ Deterministic root finding over finite fields using Graeffe transforms ⋮ Factoring polynomials and primitive elements for special primes ⋮ Constructing normal bases in finite fields ⋮ Computing special powers in finite fields ⋮ Computing the structure of finite algebras ⋮ Optimal ancilla-free Pauli+V circuits for axial rotations ⋮ Short presentations for finite groups ⋮ Univariate polynomial factorization over finite fields ⋮ Unconditional Byzantine agreement for any number of faulty processors ⋮ SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption ⋮ Cryptanalysis of the CLT13 multilinear map ⋮ Power roots of polynomials over arbitrary fields ⋮ Univariate polynomial factorization over finite fields with large extension degree ⋮ Characterization of irreducible polynomials over a special principal ideal ring ⋮ An improvement of Rabin's probabilistic algorithm for generating irreducible polynomials over GF(p) ⋮ Homomorphic public-key cryptosystems and encrypting Boolean circuits ⋮ Classifying the computational complexity of problems ⋮ Uniform complexity and digital signatures ⋮ On the deterministic complexity of factoring polynomials over finite fields ⋮ Analysis of Euclidean algorithms for polynomials over finite fields ⋮ Factoring polynomials using fewer random bits ⋮ On splitting sets in block designs and finding roots of polynomials ⋮ Counting Solutions to Polynomial Systems via Reductions ⋮ Arithmetic of finite fields ⋮ A New Algorithm for Factoring Polynomials Over Finite Fields ⋮ Calculating the set of orders of elements in the finite linear groups ⋮ Practic zero-knowledge proofs: Giving hints and using deficiencies ⋮ A Subexponential Algorithm for Discrete Logarithms Over all Finite Fields ⋮ On quasilinear-time complexity theory ⋮ On taking square roots without quadratic nonresidues over finite fields ⋮ Decomposition of algebras over finite fields and number fields ⋮ Efficient randomized generation of optimal algorithms for multiplication in certain finite fields ⋮ Factoring polynomials over finite fields: A survey ⋮ Deterministic polynomial factoring and association schemes ⋮ Subquadratic-time factoring of polynomials over finite fields ⋮ Analysis of Rabin's irreducibility test for polynomials over finite fields ⋮ On the number of trace-one elements in polynomial bases for \({\mathbb F}_{2^n}\) ⋮ Modular composition via factorization ⋮ Factoring Multivariate Polynomials over Large Finite Fields ⋮ Probabilistic algorithm for finding roots of linearized polynomials ⋮ Computation of orders and cycle lengths of automorphisms of finite solvable groups ⋮ Computing Characteristic Polynomials of Matrices of Structured Polynomials ⋮ Computing in Picard groups of projective curves over finite fields ⋮ A secure and scalable group key exchange system ⋮ Randomised algorithms ⋮ The time-precision tradeoff problem on on-line probabilistic Turing machines ⋮ Computing modular polynomials and isogenies of rank two Drinfeld modules over finite fields ⋮ Trading GRH for algebra: Algorithms for factoring polynomials and related structures ⋮ Concatenation of pseudorandom binary sequences ⋮ Supersingular curves with small noninteger endomorphisms ⋮ On the distribution of Atkin and Elkies primes for reductions of elliptic curves on average ⋮ A probabilistic lower bound for checking disjointness of sets ⋮ On non-Abelian homomorphic public-key cryptosystems ⋮ Computing newforms using supersingular isogeny graphs ⋮ On the decisional Diffie-Hellman problem for class group actions on oriented elliptic curves ⋮ Non-malleability against polynomial tampering ⋮ Algebraic algorithms in GF(q) ⋮ Finding roots in with the successive resultants algorithm
This page was built for publication: Probabilistic Algorithms in Finite Fields
