DocumentCode
2366266
Title
Testing equalities of multiplicative representations in polynomial time
Author
Ge, Guoqiang
Author_Institution
Dept. of Math., California Univ., Berkeley, CA, USA
fYear
1993
fDate
3-5 Nov 1993
Firstpage
422
Lastpage
426
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;
fLanguage
English
Publisher
ieee
Conference_Titel
Foundations of Computer Science, 1993. Proceedings., 34th Annual Symposium on
Conference_Location
Palo Alto, CA
Print_ISBN
0-8186-4370-6
Type
conf
DOI
10.1109/SFCS.1993.366845
Filename
366845
Link To Document