Nicol So <email@example.com> wrote in message news:<3CD94FC5.4826E3A2@no.spam.please>... > Phil Carmody wrote: > > > > nospam wrote: > > > > > > How do I determine if a number is square free, > > > without knowing its factors? > > > > The problem is as hard as factoring. > > How do you do factoring given the ability to decide square-freeness?
Good question! :o)
To rephrase Phil's statement, the fastest method *known* for testing squarefreeness requires factoring (AFAIK). See page 8 of the paper "The factorization of the 9th Fermat number" for more details. You can download it from Mark Manesse's web page: