[mathjax]以前作成した加算公式と２倍算とを用いてMontgomery ladderの実装を行った．
基本的には加算公式と２倍算を，\(k\)の各ビットの値に合わせて順繰り実行する．
1.ソースコード
特に複雑なアルゴリズムではないので，最初からソースコードを示す．
なお，加算公式と２倍算についてはリセット関連の処理を少し変えている．
2.必要なクロック数について
ここで，加算公式，２倍算，Montgomery ladderのそれぞれについて必要となるクロック数をまとめておく．
2.1.加算公式に必要なクロック数
リセット １クロック
処理 ８クロック
出力 １クロック
合計１０クロックとなる．
2.2.2倍算に必要なクロック数
リセット １クロック
処理 7クロック
出力 １クロック
合計9クロックとなる．
2.3.Montgomery ladderに必要なクロック数
1ビットあたりは，
セット １クロック
処理 １０クロック
取り出し １クロック
合計１２クロックとなる．
ここで，点を\(k\)倍するときに，\(k\)のビット数だけ処理を繰り返すので，\(k\)のビット数を\(b_k\)とすると\(b_k\times12\)クロックかかることになる．
さらに，結果の取り出しに１クロックかかるので，Montgomery ladderのクロック数は\(b_k\times12+1\)となる．
FPGAの最大周波数が550MHzだとすると，\((b_k\times12+1)\times1.818[ns]\)となる？？ほんとか？？
3.動作確認
今回テストに使用した曲線は\(y^2=x^3+84x^2+x,p=65521\)であり，ベースポイント\(P=(58745,1)\)を
\(k=12\)倍する計算をテストとして実行した．なお，\(12P=(48694,42622)\)である．
以下にPARI/GPで計算した結果と途中計算を示す．
上記の結果とタイミングチャートを見比べると，正しく実行できていることが分かる．
4.次回やること
y座標の復元