Ghaith Hiary: Detecting square-free numbers via the explicit formula.
Ghaith Hiary, Britsol University
Time: Thu 2012-10-04 15.15
Location: Room 3721, Mathematics Department, KTH.
Let d = m^2 n, where n is square-free, and where m and n are unknown to us.
A method to obtain a lower bound on n without attempting to factor d is presented.
If d happens to be square-free, then the method might yield a sufficiently good lower
bound on n so that the square-freeness of d can then be certified fast -- in particular,
faster than could have been done had we immediately applied one of the other known
methods that also can produce partial information about n (such as the Pollard-Strassen
algorithm). The running time of the method is heuristically sub-exponential in the lower
bound over a relatively wide initial range, and perhaps further. The method is based on
the explicit formula for the Dirichlet L-function associated with a suitably chosen real
character, and assuming the generalized Riemann hypothesis for that L-function.
Several optimizations of the method will be discussed. Examples of computations
using the method will be given. This is joint work
with Andy Booker and Jon Keating.