• DocumentCode
    2822114
  • Title

    A lower bound for primality

  • Author

    Allender, Eric ; Saks, Michael ; Shparlinski, Igor

  • Author_Institution
    Dept. of Comput. Sci., Rutgers Univ., Piscataway, NJ, USA
  • fYear
    1999
  • fDate
    1999
  • Firstpage
    10
  • Lastpage
    14
  • Abstract
    Recent work by Bernasconi, Damm and Shparlinski proved lower bounds on the circuit complexity of the square-free numbers, and raised as an open question if similar (or stronger) lower bounds could be proved for the set of prime numbers. In this short note, we answer this question affirmatively, by showing that the set of prime numbers (represented in the usual binary notation) is not contained in AC0 [p] for any prime p. Similar lower bounds are presented for the set of square-free numbers, and for the problem of computing the greatest common divisor of two numbers
  • Keywords
    circuit complexity; computational complexity; circuit complexity; greatest common divisor; lower bound; primality; square-free numbers; Circuit testing; Computer science; Encoding; Mathematics; Physics computing; Polynomials; Upper bound;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computational Complexity, 1999. Proceedings. Fourteenth Annual IEEE Conference on
  • Conference_Location
    Atlanta, GA
  • ISSN
    1093-0159
  • Print_ISBN
    0-7695-0075-7
  • Type

    conf

  • DOI
    10.1109/CCC.1999.766257
  • Filename
    766257
    • Link To Document
    https://search.isc.ac/dl/search/defaultta.aspx?DTC=49&DC=2822114