The best algorithm isn't quadratic. It's M(n)log(n) where M(n) is the cost of your integer multiply (M(n) theoretically be as low as nlog(n), but in practice th

The best algorithm isn't quadratic. It's M(n)log(n) where M(n) is the cost of your integer multiply (M(n) theoretically be as low as nlog(n), but in practice the best algorithms used are nlog(n)log(log(n))). Python just didn't bother to implement them.