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 element of F-n such that f(X-1 + alpha(1),...,X-n + alpha(n)) = g. In three different cases algorithms which produce the set of all shift-equivalences of f, g in polynomial time are designed. Here (1) in the case of a zero-characteristic field F the designed algorithm is deterministic; (2) in the case of a prime residue field F = F-p and a reduced polynomial 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) in 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, which 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. [References: 19]
展开▼
