Programming Bitcoin をRust で実装していく(Part 2)
Part1.
1. 有限体の実装
- 前回の記事で取り上げたモジュロ演算等を使った有限体の実装に写っていきます.
といっても, ほぼPython で書かれたコードをRust で書き換えてあげてるだけですが.
Python の場合コンストラクタで例外処理を入れたりしてるのですが,Rust では一旦Optionを使った処理で適合しない値が引数に与えられて初期化された際はNoneを返すというのをやろうと思います.
なので,処理を実行している側で責任持ってError処理しろよ.というやり方で攻めていこうと思います(いいのかはわからん)
まずは構造体の定義
有限体の位数(規模) をpとしたとき集合の各要素を 1,2,3,・・・・p-1 という.
つまり, 位数pの有限体はp-1までの値を持った集合ということなんだろうなと.
一旦構造体として下記のように定義
(Medium ってわざわざGist使わないと行けないのがだるいよね)
構造体のプロパティ?(パラメータ?) の名前でわかるように,位数は素数にする必要があるようです.
続いてコンストラクタとデバッグ用のprintln!()マクロのオーバーライド, ==演算子のオーバーライドを定義します.
Rust にはクラスがなく,struct で定義したあとにimpl というので関数を追加していきます. C++ から来たのでこの辺見たときふへーってなりました.
ここでは一旦マイナス値を考慮しないように考えたためusizeを使っていますが,今後読み進めていく上で使えないってなった場合は書き直していきますのであしからず..(なのであえてusize なのにif文内でnum≥=0とか見てます.コンパイラにwarnで怒られます)
fmt::Debugは
println!(FieldElement{num: 1, prime:13});
とかやった際にErrorなく内容を表示するとき用のもので,Trait を使ってオーバーライドしてます.
また, 同じくTrait を使って==演算子もオーバーライドするためにPartialEq を定義してお互いのnumとprime がそれぞれ同じだった際にTrueを返せるように定義しています.
Rust は引数に変数を渡すと渡し元のほうが所有権を譲ってしまい使えなくなってしまうので一応引数には借用のため&をつけたもので受け取るようにしています.
このあたりはRustのチュートリアルで詳細あるので確認してみてください.
あとは作業的な感じで加算,乗算,べき乗などを追加していきます.
以下がその実装になります.
位数が同じ有限体同士でしか演算できないのでprime が同一か確認をしています.
どれもモジュロ演算を活用して計算結果の値も有限体の集合に含まれる値になるようになっています.
基本的には各種計算後にprimeでモジュロ演算するという感じです.
ちょっと正直なところ,PowとDivに関してはあってるのかわからんけど,計算結果は書籍と同じになったから大丈夫かなぁとか思ってます.(間違ってたらすみません,修正します)
適当なテストを追加して書籍で表されている計算と同じ結果になるか確認しました. Rustは同一ファイルで #[cfg(test)]とやってmod test{} でくくったものはテストコードとして認識してくれるようでそれに従い,実装してます. (テストコードには書いてるけど実装部分にuse など記載忘れたので適宜追加していただかないとImport Error 吐くと思います.
use super::* により 上で実装したコードをテスト内でも使えるようにインポートしています. 有限体の実装の1章がだいたいこんな感じだったかと思います. 薄いですが,今回はこんな感じで次回,2章の楕円曲線の実装に移ります.
今後の実装ですがまだ終わってないのとLive Coding でやろうとも思ってるので次回更新は未定です.
また!=演算子の実装をしてないので是非真似して試してみてください. 楕円曲線の実装には必要になる演算子になります.