Testing shift-equivalence of polynomials by deterministic, probabilistic and quantum machines

AbstractThe polynomials ƒ, g E F[X1,…,Xn] are called shift-equivalent if there exists a shift (α1,…, αn) E Fn such that ƒ(X1 + α1,… ,Xn + αn) = g. In three different cases algorithms which produce the set of all shift-equivalences of ƒ, g in polynomial time are designed. Here 1.(1) in the case of a zero-characteristic field F the designed algorithm is deterministic;2.(2) in the case of a prime residue field F = Fp and a reduced polynomial ƒ, i.e. degXi(ƒ))</ p − 1, 1 </ i </ n, the algorithm is randomized;3.(3) in the case of a finite field F = Fq of characteristic 2 the algorithm is quantum; for an arbitrary finite field fFq a quantum machine, which computes the group of all shift-selfequivalences of ƒ, i.e. (β1,…, βn) E Fqn such that ƒ(X1 + β1,…,Xn + βn) = ƒ, is designed