颂哈吉-施特拉森算法
维基百科,自由的 encyclopedia
颂哈吉-施特拉森算法(英语:Schönhage–Strassen algorithm)是渐近快速的大整数乘法算法。是由阿诺德·颂哈吉(英语:Arnold Schönhage)和沃尔克·施特拉森在1971年发明[1]。若针对二个n位元的整数,其运行的位元复杂度(英语:bit complexity),若以大O符号表示,是。算法使用在有2n+1个元素的环上的迭代快速傅里叶变换,这是一种特别的数论转换。
颂哈吉-施特拉森算法是1971年至2007年之间,渐近最快的乘法算法,2007年时有一个新的乘法算法Fürer算法(英语:Fürer's algorithm),其渐近复杂度较低[2],不过Fürer算法只有在大到天文数字的程度时,其速度才会比颂哈吉-施特拉森算法快,实务上不会使用Fürer算法(参考银河式算法)。
在实务上,当数字大于2215至2217(十进制下的10,000到40,000位数)时,颂哈吉-施特拉森算法的速度会比较早期的卡拉楚巴算法和图姆-库克算法要快[3][4][5]。GNU多重精度运算库用这个算法计算至少1728至7808个64位元字节的数值(十进制下的33,000至150,000位数),依硬件架构而定[6],有一个用Java实现的颂哈吉-施特拉森算法,可以计算十进制超过74,000位数[7]。
颂哈吉-施特拉森算法的应用包括数学哲学(例如互联网梅森素数大搜索以及计算圆周率近似值),实务的应用包括克罗内克代入(英语:Kronecker substitution),其中将整系数多项式的乘法有效的简化为大数的乘法,GMP-ECM中用此算法来计算Lenstra椭圆曲线分解(英语:Lenstra elliptic curve factorization)[8]。