Lower bound for primality

Eric Allender, Michael Saks, Igor Shparlinski

Research output: Chapter in Book/Report/Conference proceedingConference contribution

3 Scopus citations

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.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual IEEE Conference on Computational Complexity
PublisherIEEE Comp Soc
Pages10-14
Number of pages5
ISBN (Print)0769500757
StatePublished - 1999
EventProceedings of the 1999 14th Annual IEEE Conference on Computational Complexity - Atlanta, GA, USA
Duration: May 4 1999May 6 1999

Publication series

NameProceedings of the Annual IEEE Conference on Computational Complexity
ISSN (Print)1093-0159

Other

OtherProceedings of the 1999 14th Annual IEEE Conference on Computational Complexity
CityAtlanta, GA, USA
Period5/4/995/6/99

All Science Journal Classification (ASJC) codes

  • Software
  • Theoretical Computer Science
  • Computational Mathematics

Fingerprint

Dive into the research topics of 'Lower bound for primality'. Together they form a unique fingerprint.

Cite this