TESTING SHIFT-EQUIVALENCE OF POLYNOMIALS BY DETERMINISTIC, PROBABILISTIC AND QUANTUM MACHINES

The polynomials f, g is an element of F[X-1,...,X-n] are called shift- equivalent if there exists a shift (alpha(1),..., alpha(n)) is an elem ent of F-n such that f(X-1 + alpha(1),...,X-n + alpha(n)) = g. In thre e different cases algorithms which produce the set of all shift-equiva lences of f, g in polynomial time are designed. Here (1) in the case o f a zero-characteristic field F the designed algorithm is deterministi c; (2) in the case of a prime residue field F = F-p and a reduced poly nomial f, i.e. deg(Xi)(f) less than or equal to p - 1, 1 less than or equal to i less than or equal to n, the algorithm is randomized; (3) i n the case of a finite field F = F-q of characteristic 2 the algorithm is quantum; for an arbitrary finite field F-q a quantum machine, whic h computes the group of all shift-self-equivalences of f, i.e. (beta(1 ),...,beta(n)) is an element of F-q(n) such that f(X-1 + beta(1),...,X -n + beta(n)) = f, is designed.