存在比O（N ^ 2）效率更高的算法，可以将两个数字相乘（请参阅Karatsuba，Pollard，Schönhage–Strassen等）。
两个问题“乘以两个任意的n位数字”和“平方一个任意的n位数字”具有相同的复杂度。
我们有
4*x*y = (x+y)^2 - (x-y)^2
因此，如果对n位整数进行平方运算需要O（f（N））时间，那么也可以在O（f（N））中获得两个任意n位整数的乘积。（即2x n位和，2x n位平方，1x 2n位和和1x 2n位移位）
显然，我们有
x^2 = x * x
因此，如果将两个n位整数相乘需要O（f（N）），则可以在O（f（N））中对n位整数进行平方。
任何计算乘积（重平方）的算法都提供了一种算法，以相同的渐近成本计算平方（重平方）。
如其他答案所述，在平方的情况下，可简化用于快速乘法的算法。增益将取决于f（N）前面的常数，而不取决于f（N）本身。
602392714
清零编程群