乗算において，19.7倍から 34.3倍，平均すると25.7 倍高速であることがわかった．
3.8.4 ソフトウェア Karatsuba 乗算との速度比較
FFT 乗算が，Karatsuba 乗算とほぼ同じ速度になる16 進数 221 桁 (10 進数約 252万桁)以上の乗算において，ソフトウェア実装された Karatsuba乗算(exflib) と FFT 乗算器の速度を比較した．比較にあたり，221 桁の乗算を行う最適な FFT乗算 器を実装した．その結果，ハードウェアFFT 乗算器の乗算時間が0.39s，exflibによ る乗算時間が 16.5s であった．この結果から，ハードウェアFFT乗算は，exflibと 比較して 42 倍の性能を実現できることがわかった．また同じ桁数において FFTW による FFT 乗算の実行時間は 13.9s であった．よって FFTWとの性能差は 35 倍 となる．
3.8.5 既存の FFT ハードウェアとの関連と他のハードウェア乗算器
との比較
FFT ハードウェア (butterfly，inv-butterfly，complex multiplier) はすでに用意 されているものとし，コストとしてカウントしないという条件で，ハードウェアFFT 乗算器と 32 ビットハードウェア Karatsuba 乗算器[23]の面積コストを比較した．
その結果，32ビット (16 進数 23 桁) FFT 乗算器の面積(scaler とrounder-carrier モジュールの合計面積) が 0.15mm2 であるのに対し，32 ビット Karatsuba乗算器 の面積は，0.18µm テクノロジに換算すると，最も小さいもので約 0.10mm2 であっ た．よって，32 ビットにおいては，FFT 乗算器とKaratsuba 乗算器の面積コスト は同程度であることがわかった．また，この比較から，FFT ハードウェアを乗算に 流用した場合に追加が必要なハードウェアの面積コストは小さいこともわかった．
3.8.6 チップ試作
最後に，16 進数 2桁版 16 ビット FFT 乗算器をチップに実装し，試作を行った．
その結果，2.8mm 角のチップサイズで実装可能であることが確認できた．この実装 により，16 進数 221 桁の乗算を行う FFT 乗算器でも 9mm 角かそれ以下のチップ サイズで実現できることがわかった．
第 4 章
Karatsuba 法によるハードウェア
多倍長乗算器
本章では，Karatsuba法をハードウェア実装し，その性能とコストを評価する．本 章の構成は次の通りである．
第 4.1 節 Karatsuba法を用いた乗算をハードウェア実装することの意義を述べる．
第 4.2 節 Karatsuba 法による乗算アルゴリズムを説明する．
第 4.3 節 Karatsuba 乗算器の設計にあたり，設計の選択肢を示す．
第 4.4 節 設計の1 つの選択肢であるRecursive Karatsuba乗算器の構成法を検討 し，実装結果を示す．
第 4.5 節 第 4.4 節の結果を踏まえて，設計のもう 1 つの選択肢である Iterative
Karatsuba 乗算器の構成法を検討し，実装結果を示す．
第 4.6 節 本章のまとめを述べる．
4.1 Karatsuba 法による乗算ハードウェア実装の意義
本章では 2-way 法によるハードウェア Karatsuba乗算器について述べる．2-way 法による Karatsuba 乗算は，n 桁の乗算を O(n1.58) の時間で行うことができる．
Karatsuba 法には，他にも 3-way，4-way，· · · がある．これらの方法は，2-way 法 よりも小さい計算量で乗算を行うことができるが，そのアルゴリズムは複雑であり性 能コスト比があまり良くない．
Karatsuba 法のハードウェア実装にあたり，O(n1.58) である計算量を面積として 消費する方法と時間として消費する方法がある．本章では，これら 2 通りの方法に ついてそれぞれ検討を行う．
Karatsuba 法のハードウェアについては，過去に楕円曲線暗号等に利用するため，
ガロア体 (Galois Field，GF) 上の乗算を行う演算器が実装，評価された例は多い [6, 20]．しかし，整数多倍長乗算を行うハードウェア Karatsuba 乗算器の実装と評 価に関する報告は少ない．過去に，32ビット整数 Karatsuba乗算器を実装，評価し た例[23]があるが，より大きなビット長に対応した整数 Karatsuba乗算器に関する 報告はない．本章では，アプリケーションでの利用が期待される数百ビット以上の整
数 Karatsuba 乗算器をハードウェア実装し，評価した結果を述べる．