Title :
Testing equalities of multiplicative representations in polynomial time
Author_Institution :
Dept. of Math., California Univ., Berkeley, CA, USA
Abstract :
For multiplicative representations Πi=1kαin(i) and Πj=1lβjm(j) where αi, βj are non-zero elements of some algebraic number field K and ni, mj are rational integers, we present a deterministic polynomial time algorithm that decides whether Πi=1kαin(i) equals Πj=1lβjm(j). The running time of the algorithm is polynomial in the number of bits required to represent the number field K, the elements αi , βj and the integers ni, mj
Keywords :
deterministic algorithms; polynomial matrices; algebraic number field; deterministic polynomial time algorithm; multiplicative representations; nonzero elements; polynomial time; rational integers; testing equalities; Error probability; Galois fields; Mathematics; Polynomials; Testing;
Conference_Titel :
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location :
Palo Alto, CA
Print_ISBN :
0-8186-4370-6
DOI :
10.1109/SFCS.1993.366845