[mathjax]基本的には前回の加算公式の話と同じ．
変更点のみを書く．正直加算公式とほぼ同じだし眠いし早くMontgomery ladder組みたいので時間はかけない．
1.前回の話
加算公式の回路を組んだものの，乗算と\(mod\ p\)の高速化をするべきという指摘を受け，一度はその方針で進めようとした．
しかし最初に動くものをつくり，あとから高速化手法を取り入れ比較することで，効果を確認しつつ見栄えを良くするという小狡い手を使うことにしたのであった…
2.構成
加算公式とほぼ同じだが，いくつかの変更点がある．計算が変わったためステップ数が変更されており，in_sel,out_selのビット幅も変わっている．メモリへの初期値も\(\alpha,X_n,Z_n\)とした．なお，\(\alpha=(A+2)/4\)であり，\(A\)はMontgomery curvesのパラメータである．
in_sel，out_sel，メモリ，各信号の説明は加算公式のものを参照．
3.制御信号の設計
$$4X_nZ_n=(X_n+Z_n)^2-(X_n-Z_n)^2$$
$$X_{2n}=(X_n+Z_n)^2(X_n-Z_n)^2$$
$$Z_{2n}=4X_nZ_n((X_n-Z_n)^2+((A+2)/4)(4X_nZ_n))$$
の式に従い逐次実行的に書き下してみる．
なお，メモリには初期値としてM[0]=\(\alpha\),M[1]=\(X_n\),M[2]=\(Z_n\)が入ってるものとする．
step1
M[1]=M[1]+M[2]
M[2]=M[1]-M[2]
step2
M[3]=M[1]*M[1]
step3
M[4]=M[2]*M[2]
step4
M[2]=M[3]-M[4]
M[3]=M[3]*M[4]
step5
M[1]=M[0]*M[2]
step6
M[1]=M[4]+M[1]
step7
M[4]=M[2]*M[1]
実際の制御信号は以下のようになる．
step1
in : 101 010 001
out: 000 000 010 001 010 001
step2
in : 011 101 101
out: 001 001 000 000 000 000
step3
in : 100 101 101
out: 010 010 000 000 000 000
step4
in : 011 010 101
out: 100 011 100 011 000 000
step5
in : 001 101 101
out: 010 000 000 000 000 000
step6
in : 101 101 001
out: 000 000 000 000 001 100
step7
in : 100 101 101
out: 001 010 000 000 000 000
4.SystemVerilogによる実装
4.1.memory
4.2.control unit
5.動作確認
使用する曲線は\(y^2=x^3+84x^2+x\)で，\(p=65521\)とする．\(\alpha=(A+2)/4=32782\)となり，点については\(P_n=(19336,65265)\) ，\(2P_n=(16050,30992)\)とする．
上記のシミュレーション結果から，結果が正しいということが分かる．
それはともかく，今は午前2時であり，私はとても眠い．今日はここまでとしてもう寝ようと思う．