A.3.1 Double-Base Number System
DBNS（Double-Base Number System）は，正の整数kの表現形式の１つであり，整数kを下式のように 2及び3のべき乗の和で表すものである．
∑m
si2bi3tisi∈ {−1,1} bi, ti =0 (17)
DBNSは，1つの正の整数が多くの別表現をもつ表現形式である．例えば，10は5個のDBNS表現を，ま た，100は402個，1,000は1,295,579個のDBNS表現をもつ．一般には正の整数kの表現形式の個数nに 関して，最大で以下の個数になることがDimitrovらによって示されている[2]．
O
( logk log logk
)
(18) DBNS表現を使用すると，バイナリ表現に比べ，加算の数が減らせ，これによってスカラー倍算における加 算の数が減少するメリットがある．ランダムに選択された160ビットの整数に対するスカラー倍算の加算数 の平均値は，バイナリ表現の場合で80，NAFで53，DBNSで22である．具体な例をとると，例えばスカ ラーkが127の時，バイナリ表現の場合，
127 = 64 + 32 + 16 + 8 + 4 + 2 + 1
= 26+ 25+ 24+ 23+ 22+ 21+ 20（加算6回）
また，DBNS表現の場合，
127 = 96 + 27 + 4
= 2531+ 2033+ 2230（加算2回）
となり，実際にDBNS表現の方が加算の数が少ないことが確認できる．
一方で，バイナリ表現と異なり，2及び3のべき乗が降べき順とは限らず，降べき順でない場合，スカラー 倍算における2倍算及び3倍算が増えるという課題がある．例えば，先の整数127の場合，バイナリ表現では，
127 = 64 + 32 + 16 + 8 + 4 + 2 + 1
= 21(21(21(21(21(21+ 20) + 20) + 20) + 20) + 20) + 20) で，2倍算が6回（加算は6回）となるが，DBNS表現では，
127 = 96 + 27 + 4 = 2531+ 2033+ 2230
= 2230(2331+ 2030) + 2032
であり，2倍算，3倍算がそれぞれ5回，3回（加算は2回）となり，2倍算，3倍算だけで2533= 864À127 となり，明らかに不要な計算をすることになり，非効率である．
A.3.2 DBNSに関わる既存研究
前節で述べたスカラー倍算に置いてDBNSを使用する際の課題を解決する手法がDimitrovらによって提 案されたDBchainsである[3]．
DBChiansはDBNS表現の1種で，下記のようにDBNS表現を2及び3の降べき順のものに限定したも のである．
k=
∑n
i=0
si2bi3ti
si∈ {−1,1}b0≥b1≥ · · · ≥bn ≥0, t0≥t1≥ · · · ≥tn ≥0
DBChainsでは，下式のようにbi，tiの値が小さいときの計算結果を，bi，tiの値が大きい時の計算に利用 出来るため，スカラー倍算の2倍算及び3倍算が増える問題を回避可能である．
k =
∑n
i=0
si2bi3ti
= 2b03t0(2b1−b03t1−t0(2b2−b13t2−t1+ 1)・・・・・+ 1) 例えば，k=127の場合，前節のようなDBchainsでないDBNS表現の場合，
127 = 96 + 27 + 4 = 2531+ 2033+ 2230
= 2230(2331+ 1) + 2032
となり，2倍算，3倍算がそれぞれ5回と3回であったが，DBchainsとなるDBNS表現を使用すると，
127 = 108 + 18 + 1 = 2233+ 2132+ 2030
= 2030(2132(2131+ 1) + 1)
となり，2倍算，3倍算はそれぞれ2回と3回に減ることが確認できる．また，2233= 108<127であり，
不要な2倍算，3倍算は行われていない．
一方，DBChainsでは，2及び3のべき乗の値が降順になるようなDBNS表現に限定するため，選択可能 なDBNS表現の数が大幅に削減される．このため，必ずしも加算の数を最小化するようなDBNS表現の選 択が出来るとは限らない．この制約を緩和する手法としてYao’s algorithmを利用した手法をMeloniらが提 案している[6]．Meloniらの手法は，DBNS表現を3のべき乗が同一の項をまとめ，以下のように変形する．
k=d(0) + 3d(1) + 32d(2) +・・・+ 3max(ti)d(max(ti))
= (3(・・・3(3d(max(ti)) +d(max(ti)−1)) +・・・+d(1)) +d(0) 但し，d(j) =∑
ti=j
2i
ここで，20,21,22,・・・・・,2max(bi) を事前に計算しておくことで，スカラー倍算の計算コストは，2 倍算
がmax(bi)， 3倍算がmax(ti)となり，DBchainsと同一の計算コストとなる．一方，加算の計算コストは
DBNSの項数−1となりDBchainsと同一に見えるが，DBchainsに比べ，選択可能なDBNS表現の数が増 えるため，DBNSの項数もより小さいものを選択可能であり，DBchainsよりも加算の計算コストが下がる 可能性が高い手法である．
しかしながら，多くの2のべき乗の事前計算が必要になるため，メモリ容量が小さいデバイスでは利用が
表12: DBNSの既存研究
Dimitrovら(2005年) [3] Meloniら(2009年) [6]
DBNS表現 2及び3の降べき順 2と3のべき乗の最大値 (b0≥b1≥ · · · ≥bm≥0, の積がスカラーK以内 t0≥t1≥ · · · ≥tm≥0) (k≥2max(bi)3max(ti)) DBNS表現 Greedy algorithm n/a
導出方法
スカラー倍算 Left to Right 3のべきが同一の項 の計算方法 をまとめてLeft to Right 計算コスト 2のべきの最大値 2のべきの最大値
(2倍算) （=初項の2のべきb0）
計算コスト 3のべきの最大値 3のべきの最大値 (3倍算) （=初項の3のべきt0）
計算コスト DBNS表現の項数-1 DBNS表現の項数-1 (加算) ※Meloniらの手法 ※Dimitrovらの手法
に比べ，DBNS表現の に比べ制限が緩やかで，
項数は増加傾向 DBNS表現の項数は 減少傾向
プレ計算 不要 2のべきの最大値までの 全ての2のべき乗のプレ計算 が必要．
（20P,21P,· · ·,2max(bi))
A.3.3 既存研究の課題
Dimitrovらの手法であるDBchainsでは，スカラーkからDBNS表現を導出するためにGreedy algorithm を用いている．Greedy algorithmは，スカラーkに対して，|k−2b3t|を最小にするようなb, tを求め，その ようなb, tに対して，|k−2b3t| →kと置いて，同様に|k−2b3t|を最小にするようなb, tを求める処理を，
kの値が0になるまで繰り返すというものである．
—————————————————————————
Algorithm 1. Greedy algorithm for DBchains
—————————————————————————
Inputk, a n-bit positive integer;bmax, tmax>0, the largest allowed binary and ternary exponents OutputThe sequence (si, bi, ti)i≥0 such thatk=∑m
i=1si2bi3ti, withb0≥ · · · ≥bm≥0 andt0≥ · · · ≥ tm≥0
1: s←0
2: whilek >0 do
3: definez= 2b3t, the best approximation ofkwith 0≤b≤bmaxand0≤t≤tmax
4: print (s, b, t) 5: bmax←b, tmax←t 6: ifk < z then 7: s← −s 8: k← |k−z|
—————————————————————————
ここでDBchainsの条件を満たすDBNS表現は，下式のように変形することができる．
k = 2b03t0+ 2b13t1 +· · ·+ 2bm−13tm−1 + 2bm3tm = 2bm3tm(2bm−1−bm3tm−1−tm(· · ·(2b0−b13t0−t1 + 1) + 1)· · ·+ 1)
上式から，DBchainsのスカラー倍算の計算量は，2倍算がb0回，3倍算がt0回，加算がm回であること が分かる．すなわち，2倍算，3倍算の回数は，それぞれDBchainsの初項の2のべき，3のべきとなる．
一方で，2倍算に比べ3倍算の計算コストは高く(表11参照)なるため，3倍算の回数は極力小さくするこ とが望ましい．しかしながら，Greedy algorithmでは，初項(2b03t0)をスカラーkに最も近い値になるとい う条件のみで設定するため，初項の3のべきは小さい値になるとは限らず，初項の算出方法に問題があると 考えられる．