FFTを使用して、非常に大きな整数をある基数/基数から別の基数に変換するにはどうすればよいですか？

Question

nの数字を1つの基数/基数で符号化し、それを別の任意の基底に変換する既知のアルゴリズムはありますか？ （ベース7からベース19まで）nは実際には10000を超える のように大きくなる可能性があるので、O（n ）よりも優れたものを探しています。

Iは、桁数であるN O（NログN）の理論的な複雑さと、高速フーリエ変換を使用して、2つの大きな整数（FFT）を掛けることができ、いくつかのアルゴリズムを見ていますだから、ベース/基数変換に類似したものが存在するのだろうか？

Answer 1

私はよく話題に自分自身を精通ないんだけど、ここでは少し速くナイーブ余り-と除算アルゴリズムよりも基数変換を行う方法でヒントページがあります：

• GNU MP - Binary to Radix

このページでは、高速除算アルゴリズム（Karatsuba、Toom-Cook、FFTなど）を必要とする高速除算および征服アルゴリズムが必要であることを示しています。