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

✍ Scribed by D. Grigoriev

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 930 KB
• Volume: 180
• Category: Article
• ISSN: 0304-3975
• DOI: 10.1016/s0304-3975(96)00188-0

✦ Synopsis

The polynomials f, g E F[Xl, ,X,J are called shift-equivalent if there exists a shift (a~, , cc,) E F" such that f(Xl furl, . . ,X,, + CC,) = 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, and a reduced polynomial ,f, i.e. deg,!(f) G p -1, 1 <i <n, the algorithm is randomized;

(3) in the case of a finite field F = iF, of characteristic 2 the algorithm is quantum; for an arbitrary finite field F, a quantum machine, which computes the group of all shift-selfequivalences of f, i.e. (PI,. .,p',,) E lFi such that f(Xr + /?I,. .,X, + fin) = J', is designed.