Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with GCD:
TR99-010 | 1st April 1999
Eric Allender, Igor E. Shparlinski, Michael Saks

A Lower Bound for Primality

Comments: 1

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

ISSN 1433-8092 | Imprint