高速乗算法(1)(→[F3])で導入したT(n)を再度使用する。とおくとが成り立つ。T(n),n=0,1,2,3,4,5,6を素数判定すると次のようになる。T(5)が素数になるのでこれを使用する。T(5)を法とする整数の剰余環Z_T(5)は有限体となるが、この元は1語を32bitとするとき2語で表現できる。この積はと128bit長で表現されるが、このとき、より除算を使わずに剰余演算ができる。

　T(5)は素数であり、F_T(5)上に長さNの離散フーリエ変換が存在するための必要十分条件は、であるが、はこの条件を満たし、さらにこのときT(5)の最小原始根7を使ってF_T(5)上の1の原始N乗根をと表現することができる。

　T(5)によって係数の評価式のを2語で表現できる素数によって上から押さえることができた。次にを1語で表現できる素数によって上から押さえることを考える。とおくとこれは1語で表現できる。この中で素数となるものは、の２つである。離散フーリエ変換の長さをなるべく長くするためにV(30)を使う。が成り立っているので、である。V(30)を法とする整数の剰余環Z_V(30)は有限体となるが、この元は1語で表現できる。この積はと64bit長で表現されるが、このとき、より除算を使わずに剰余演算ができる。

　V(30)は素数であり、F_V(30)上に長さNの離散フーリエ変換が存在するための必要十分条件は、であるが、はこの条件を満たし、さらにこのときV(30)の最小原始根5を使ってF_V(30)上の1の原始N乗根をと表現することができる。

Step 1. 数のP進表現
　基数をP=2³²とし、長さをとする。正の整数a,bが次のようにP進表現されるものとする。この積について0≦ab＜P^Nが成り立つと仮定する。

Step 2. 多項式としての積の計算
　P^K≡1(mod P^N-1)より、となる。この係数c_r=��_{s+t≡r(mod N)}a_sb_tの大きさを評価すると、となる。

Step 3. 離散フーリエ変換による係数の計算
　c_rは、(N, F_U(5), ζ), ζ=11^t, t=2^32-n(2⁶⁴-1)型の離散Fourier変換を利用して次のように計算する。

Step 4. 桁上げ処理
　最後にc_r, r=0,…,K-1に桁上げ処理を施すことで、c=abのP進表現が得られる。