I remember (if that is not a false memory) that Sarnak once expressed the opinion that factoring has polynomial complexity.