On solving systems of diagonal polynomial equations over finite fields

DOI10.1007/978-3-319-19647-3_12MaRDI QIDQ3452558zbMATH OpenOpenAlexFDO

Authors Gábor Ivanyos, Miklos Santha

Publication date 12 November 2015

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.09016, http://eprints.sztaki.hu/8531/

zbMATH Keywords

algorithmChevalley-warning theoremfinite fieldspolynomial equationsquantum computing

Mathematics Subject Classification ID

Quantum algorithms and complexity in the theory of computing (68Q12) Symbolic computation and algebraic computation (68W30)

Abstract: We present an algorithm to solve a system of diagonal polynomial equations over finite fields when the number of variables is greater than some fixed polynomial of the number of equations whose degree depends only on the degree of the polynomial equations. Our algorithm works in time polynomial in the number of equations and the logarithm of the size of the field, whenever the degree of the polynomial equations is constant. As a consequence we design polynomial time quantum algorithms for two algebraic hidden structure problems: for the hidden subgroup problem in certain semidirect product p-groups of constant nilpotency class, and for the multi-dimensional univariate hidden polynomial graph problem when the degree of the polynomials is constant.

Recommendations

• Solving systems of diagonal polynomial equations over finite fields
• scientific article; zbMATH DE number 5372380
• Beating brute force for systems of polynomial equations over finite fields
• Deterministic equation solving over finite fields
• Efficient quantum algorithm for identifying hidden polynomials

Cites work

• A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
• An efficient quantum algorithm for the hidden subgroup problem in nil-2 groups
• Deterministic equation solving over finite fields
• Efficient quantum algorithm for identifying hidden polynomials
• Finding conjugate stabilizer subgroups in PSL(2; q) and related groups
• Hidden symmetry subgroup problems
• Hidden translation and translating coset in quantum computing
• scientific article; zbMATH DE number 5595151 (Why is no real title available?)
• scientific article; zbMATH DE number 3480679 (Why is no real title available?)
• scientific article; zbMATH DE number 1256724 (Why is no real title available?)
• On solving systems of diagonal polynomial equations over finite fields
• On the complexity of the parity argument and other inefficient proofs of existence
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Quantum Computation and Lattice Problems
• Quantum mechanical algorithms for the nonabelian hidden subgroup problem
• Reducibility among combinatorial problems
• The Hidden Subgroup Problem and Quantum Computation Using Group Representations
• The power of basis selection in Fourier sampling: hidden subgroup problems in affine groups

Cited in

(4)

• On solving systems of diagonal polynomial equations over finite fields
• Solving systems of diagonal polynomial equations over finite fields
• Automata, Languages and Programming
• Polynomial parametrization of the solutions of certain systems of Diophantine equations

This page was built for publication: On solving systems of diagonal polynomial equations over finite fields

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