A lower bound for primality

Eric Allender; Michael Saks; Igor Shparlinski

doi:10.1109/CCC.1999.766257

A lower bound for primality

Eric Allender^*, Michael Saks, Igor Shparlinski

^*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceeding › Conference proceeding contribution › peer-review

3 Citations (Scopus)

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 AC⁰[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 language	English
Title of host publication	Proceedings of the Annual IEEE Conference on Computational Complexity
Place of Publication	Piscataway, N.J.
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	1-5
Number of pages	5
ISBN (Print)	0769500757
DOIs	https://doi.org/10.1109/CCC.1999.766257
Publication status	Published - May 1999
Externally published	Yes
Event	Proceedings of the 1999 14th Annual IEEE Conference on Computational Complexity - Atlanta, GA, USA Duration: 4 May 1999 → 6 May 1999

Other

Other	Proceedings of the 1999 14th Annual IEEE Conference on Computational Complexity
City	Atlanta, GA, USA
Period	4/05/99 → 6/05/99

Access to Document

10.1109/CCC.1999.766257

Cite this

@inproceedings{78790e46263444ee81d202d7f3fe8d02,

title = "A lower bound for primality",

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.",

author = "Eric Allender and Michael Saks and Igor Shparlinski",

year = "1999",

month = may,

doi = "10.1109/CCC.1999.766257",

language = "English",

isbn = "0769500757",

pages = "1--5",

booktitle = "Proceedings of the Annual IEEE Conference on Computational Complexity",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

address = "United States",

note = "Proceedings of the 1999 14th Annual IEEE Conference on Computational Complexity ; Conference date: 04-05-1999 Through 06-05-1999",

}

Allender, E, Saks, M & Shparlinski, I 1999, A lower bound for primality. in Proceedings of the Annual IEEE Conference on Computational Complexity., 00766257, Institute of Electrical and Electronics Engineers (IEEE), Piscataway, N.J., pp. 1-5, Proceedings of the 1999 14th Annual IEEE Conference on Computational Complexity, Atlanta, GA, USA, 4/05/99. https://doi.org/10.1109/CCC.1999.766257

TY - GEN

T1 - A lower bound for primality

AU - Allender, Eric

AU - Saks, Michael

AU - Shparlinski, Igor

PY - 1999/5

Y1 - 1999/5

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032670029&partnerID=8YFLogxK

U2 - 10.1109/CCC.1999.766257

DO - 10.1109/CCC.1999.766257

M3 - Conference proceeding contribution

AN - SCOPUS:0032670029

SN - 0769500757

SP - 1

EP - 5

BT - Proceedings of the Annual IEEE Conference on Computational Complexity

PB - Institute of Electrical and Electronics Engineers (IEEE)

CY - Piscataway, N.J.

T2 - Proceedings of the 1999 14th Annual IEEE Conference on Computational Complexity

Y2 - 4 May 1999 through 6 May 1999

ER -

A lower bound for primality

Abstract

Other

Access to Document

Other files and links

Fingerprint

Cite this