• DocumentCode
    303114
  • Title

    Computationally hard algebraic problems

  • Author

    Rabin, Michael O.

  • Author_Institution
    Hebrew Univ., Jerusalem, Israel
  • fYear
    1996
  • fDate
    14-16 Oct 1996
  • Firstpage
    284
  • Lastpage
    289
  • Abstract
    In this paper we present a simple geometric-like series of elements in a finite field Fq, and show that computing its sum is NP-hard. This problem is then reduced to the problem of counting mod p the number of zeroes in a linear recurrence sequence with elements in a finite Fp, where p is a small prime. Hence the latter problem is also NP-hard. In the lecture we shall also survey other computationally hard algebraic problems
  • Keywords
    computational complexity; NP-hard; computationally hard algebraic problems; finite field; geometric-like series; linear recurrence sequence; zeroes; Algebra; Galois fields; Monte Carlo methods; Polynomials;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Foundations of Computer Science, 1996. Proceedings., 37th Annual Symposium on
  • Conference_Location
    Burlington, VT
  • ISSN
    0272-5428
  • Print_ISBN
    0-8186-7594-2
  • Type

    conf

  • DOI
    10.1109/SFCS.1996.548487
  • Filename
    548487
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=303114