8 citations · 52 across the 22 of their papers we have counts for
22 papers
Quantum Algorithm for Optimization and Polynomial System Solving over Finite Field and Application to Cryptanalysis
Yu-Ao Chen, Xiao-Shan Gao, Chun-Ming Yuan
In this paper, we give quantum algorithms for two fundamental computation problems: solving polynomial systems over finite fields and optimization where the arguments of the object…
Quantum Algorithms for Boolean Equation Solving and Quantum Algebraic Attack on Cryptosystems
Yu-Ao Chen, Xiao-Shan Gao
Decision of whether a Boolean equation system has a solution is an NPC problem and finding a solution is NP hard. In this paper, we present a quantum algorithm to decide whether a…
Revisit Sparse Polynomial Interpolation based on Randomized Kronecker Substitution
Qiao-Long Huang, Xiao-Shan Gao
In this paper, a new reduction based interpolation algorithm for black-box multivariate polynomials over finite fields is given. The method is based on two main ingredients. A new…
Faster Interpolation Algorithms for Sparse Multivariate Polynomials Given by Straight-Line Programs\
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we propose new deterministic and Monte Carlo interpolation algorithms for sparse multivariate polynomials represented by straight-line programs. Let be an -va…
Sparse Rational Function Interpolation with Finitely Many Values for the Coefficients
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we give new sparse interpolation algorithms for black box univariate and multivariate rational functions h=f/g whose coefficients are integers with an upper bound. T…
Sparse Polynomial Interpolation with Finitely Many Values for the Coefficients
Qiao-Long Huang, Xiao-Shan Gao
In this paper, we give new sparse interpolation algorithms for black box polynomial f whose coefficients are from a finite set. In the univariate case, we recover f from one evalua…