If p^2+p+1 is smooth or if p^2+1 is smooth then n can be factored with cyclotomic methods. http://www.ams.org/journals/mcom/1989-52-185/S0025-5718-1989...