ここでは，PFA や WFTA で使用可能な Short DFT ルーチンの設計方法に ついて考えます．この Short DFT は素数の長さが多く，通常の FFT の 考え方は適用できません．一般に，素数の長さの高速 DFT アルゴリズムを 設計する方法は，何らかの方法で DFT を畳み込みに変換し，FFT や，FFT の 考えに基づいた高速畳み込み算法を用いることです．ここでは，Rader の 方法と呼ばれる，素数の長さの DFT を簡単な添字の変換により巡回畳み込みに 変換する方法について示します．
Rader の方法はまず，素数の長さの DFT
N-1 -2πij / N
Ａ(k) ＝ Σ ａ(j) Ｗ(N; jk) ， Ｗ(N; j) ＝ ｅ
j=0
に対して，添字の変換
q
k ＝ ｇ mod N
-p
j ＝ ｇ mod N
を行います．ここで，ｇ は原始根と呼ばれる整数です．数論によると N が 素数であれば，上の式において k = 1,2,...,N-1 の N-1 個の要素と q = 0,1,...,N-2 の N-1 個の要素との間に一対一写像をなすような原始根 ｇ が存在することがわかっています．この変換を DFT に施すと
q N-2 -p q-p
Ａ(ｇ ) ＝ ａ(0) ＋ Σ ａ(ｇ ) Ｗ(N; ｇ )
p=0
となり，さらに
j 〜
Ａ(ｇ ) ＝ Ａ
j
-j 〜
ａ(ｇ ) ＝ ａ
j
j
Ｗ(N; ｇ ) ＝ ｈ
j
と置き直せば，もとの DFT は長さ N-1 の巡回畳み込み
〜 N-2 〜
Ａ ＝ ａ(0) ＋ Σ ａ ｈ
q p=0 p q-p
に変換されます．この方法はさらに，N が奇の素数の整数乗の場合にも 拡張できます．この方法と FFT により，素数の長さ N の DFT は， N*log(N) の演算量で設計できることになります．しかし，これは N が非常に 大きいときに有効な方法です．実際の Short DFT アルゴリズムは，畳み込みを 二つの多項式の積の計算であるとみなして，多項式の剰余分解に基づく方法で 設計します．詳しくは[参考文献]を参照して ください．これには，Rader の方法で設計された長さ N = 2,3,4,5,7,8,9,16 の 乗算回数の少ない Short DFT アルゴリズムが与えられています．