• 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