Square-Freeness Testing and Other Number-Theoretic Problems
Igor E. Shparlinski · Birkhäuser Basel eBooks · 2003
We extend the area of applications of our methods to lower bounds on the circuit and decision tree complexity of Boolean functions related to some number-theoretic problems. In particular, we show that deciding whether a given integer is square-free and testing co-primality of two integers by unbounded fan-in circuits of bounded depth requires superpolynomial size, see [9, 38, 39, 40, 41, 460]. This method can be applied to other number-theoretic problems related to arithmetical properties of integers. Unfortunately this approach does not seem to apply to the complexity of the primality testing problem, for which an alternative approach has been developed in [9], which in fact implies stronger but less explicit results (which apply to square-freeness and co-primality testing as well).