最近、バイナリ拡張ユークリッド アルゴリズムがプロセッサ レベルでどのように機能するかを理解しようとしています。この質問は、多項式ベースで GF(2^m) の逆要素を見つけることに関するものです。
一般に、逆要素を評価するために拡張ユークリッド アルゴリズムに出くわしましたが、実際には、加算と乗算の操作が多すぎます。Binary EEA アルゴリズムでは、ビット シフト演算 (2 による除算、つまり論理右シフトに相当) のみが必要です。アルゴリズムは、このリンクのページ番号 8 にあります。
このアルゴリズムのステップ 3 と 5 では、反復ごとにパラメータがシフトされ、同時に MSB に 0 が追加されて右に 1 ビットuシフトされます。bループは終了しu == 1、 が返されますb。私の質問は、プロセッサ (たとえば 32 ビット プロセッサ) が各反復のステップ 3 またはステップ 5 で実行するプリミティブ操作の数はいくつですか?
バレルシフターに出くわしましたが、シフトの速さについてかなり混乱しています。これらのプリミティブ操作を本当に考慮する必要がありますか、それともシフトが高速になる可能性があるため無視する必要がありますか?
uサイズが 194 ビットの場合のプリミティブ操作を誰かが示してくれると、本当に助かります。
xアルゴリズムのステップ 3 と 5 の分母について疑問に思われるかもしれませんが、これは多項式表現であり、2 進法のみをx意味10し、パラメーターuは N ビットの 2 進数です。