A lower bound for primality

Eric Allender; Michael Saks; Igor Shparlinski

doi:10.1006/jcss.2000.1725

A lower bound for primality

Eric Allender, Michael Saks, Igor Shparlinski

Research output: Contribution to journal › Article › peer-review

13 Scopus citations

Abstract

Recent work by Bernasconi, Damm, and Shparlinski showed that the set of square-free numbers is not in AC⁰ and raised as an open question whether similar (or stronger) lower bounds could be proved for the set of prime numbers. We show that the Boolean majority function is AC⁰-Turing reducible to the set of prime numbers (represented in binary). From known lower bounds on Maj (due to Razborov and Smolensky) we conclude that primality cannot be tested in AC⁰[p] for any prime p. Similar results are obtained for the set of square-free numbers and for the problem of computing the greatest common divisor of two numbers.

Original language	English (US)
Article number	91725
Pages (from-to)	356-366
Number of pages	11
Journal	Journal of Computer and System Sciences
Volume	62
Issue number	2
DOIs	https://doi.org/10.1006/jcss.2000.1725
State	Published - 2001

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Applied Mathematics
Computer Science(all)
Computer Networks and Communications
Computational Theory and Mathematics

Access to Document

10.1006/jcss.2000.1725

Cite this

@article{e805aa89a57e4267ae922c7f5dc05f59,

title = "A lower bound for primality",

abstract = "Recent work by Bernasconi, Damm, and Shparlinski showed that the set of square-free numbers is not in AC0 and raised as an open question whether similar (or stronger) lower bounds could be proved for the set of prime numbers. We show that the Boolean majority function is AC0-Turing reducible to the set of prime numbers (represented in binary). From known lower bounds on Maj (due to Razborov and Smolensky) we conclude that primality cannot be tested in AC0[p] for any prime p. Similar results are obtained 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",

note = "Funding Information: 1A preliminary version of this work appeared in Proc. 14th Annual IEEE Conference on Computational Complexity, 1999, pp. 10 14. 2Supported in part by NSF Grant CCR-9734918. 3Supported in part by NSF Grant CCR-9700239. 4Supported in part by ARC Grant A69700294.",

year = "2001",

doi = "10.1006/jcss.2000.1725",

language = "English (US)",

volume = "62",

pages = "356--366",

journal = "Journal of Computer and System Sciences",

issn = "0022-0000",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - A lower bound for primality

AU - Allender, Eric

AU - Saks, Michael

AU - Shparlinski, Igor

N1 - Funding Information: 1A preliminary version of this work appeared in Proc. 14th Annual IEEE Conference on Computational Complexity, 1999, pp. 10 14. 2Supported in part by NSF Grant CCR-9734918. 3Supported in part by NSF Grant CCR-9700239. 4Supported in part by ARC Grant A69700294.

PY - 2001

Y1 - 2001

N2 - Recent work by Bernasconi, Damm, and Shparlinski showed that the set of square-free numbers is not in AC0 and raised as an open question whether similar (or stronger) lower bounds could be proved for the set of prime numbers. We show that the Boolean majority function is AC0-Turing reducible to the set of prime numbers (represented in binary). From known lower bounds on Maj (due to Razborov and Smolensky) we conclude that primality cannot be tested in AC0[p] for any prime p. Similar results are obtained 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 showed that the set of square-free numbers is not in AC0 and raised as an open question whether similar (or stronger) lower bounds could be proved for the set of prime numbers. We show that the Boolean majority function is AC0-Turing reducible to the set of prime numbers (represented in binary). From known lower bounds on Maj (due to Razborov and Smolensky) we conclude that primality cannot be tested in AC0[p] for any prime p. Similar results are obtained 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=0035276873&partnerID=8YFLogxK

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

U2 - 10.1006/jcss.2000.1725

DO - 10.1006/jcss.2000.1725

M3 - Article

AN - SCOPUS:0035276873

SN - 0022-0000

VL - 62

SP - 356

EP - 366

JO - Journal of Computer and System Sciences

JF - Journal of Computer and System Sciences

IS - 2

M1 - 91725

ER -

A lower bound for primality

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this