fft - 如何使用 FFT 将一个非常大的整数从一个基数/基数转换为另一个？

Question

是否有已知的算法将采用一个以一个基数/基数编码的n位数字的大整数并将其转换为另一个任意基数？（假设从 7 到 19。）n可以非常大，比如超过 100 000 位，所以我正在寻找比 O( n ² ) 运行时间更好的东西。

我已经看到一些算法可以使用快速傅里叶变换 (FFT) 将两个大整数相乘，其理论复杂度为 O( n log n )，其中n是位数，所以我想知道基数/基数转换？

Answer 1

我自己并不精通这个主题，但这里有一个页面提示如何比简单的余数和除法算法更快地进行基数转换：

• GNU MP - 二进制到基数

该页面提示您需要快速分治除法算法，而后者又需要快速乘法算法（Karatsuba、Toom-Cook、FFT 等）。