情報セキュリティ試験の授業で出会った問題
1037 ワード
最近、情報セキュリティのテストを勉強していて、サボっている私は、本のアルゴリズムに従って書いていて、アルゴリズムを理解していませんが、間違いが相次いでいて、本のアルゴリズムが間違っていると思っていましたが、今日は一歩追跡してから問題の所在を発見しました.この問題も実は非常に典型的です.
テーマは拡張ユークリッドアルゴリズムで乗算逆元を求めることである.
まずエラー箇所のアルゴリズムt 1=(u-q*v 1)mod mを見てみると、最初は先生がすべてのデータがunsigned intであることを要求していたので、私はまったく考えずにすべての変数をunsined intと宣言したが、本にはt 1=-13が現れたので、私はその場ですべての変数を立断してintに変更したが、結果は依然として間違っていて、追跡を続けた.やはりこの点が間違っていて、mかunsigned intか、modの演算を求めると前の-13がunsigned intタイプ、つまりINT_に変換されることを思い出しました.MAX-13は、この数字で余剰を求めるのは当然間違っているので、mをintタイプに変えるだけでいいのですが、呼び出すときは強制的にタイプ変換したほうがいいです.
ソースコードを次に示します
また、このような学習方法は望ましくない.
テーマは拡張ユークリッドアルゴリズムで乗算逆元を求めることである.
まずエラー箇所のアルゴリズムt 1=(u-q*v 1)mod mを見てみると、最初は先生がすべてのデータがunsigned intであることを要求していたので、私はまったく考えずにすべての変数をunsined intと宣言したが、本にはt 1=-13が現れたので、私はその場ですべての変数を立断してintに変更したが、結果は依然として間違っていて、追跡を続けた.やはりこの点が間違っていて、mかunsigned intか、modの演算を求めると前の-13がunsigned intタイプ、つまりINT_に変換されることを思い出しました.MAX-13は、この数字で余剰を求めるのは当然間違っているので、mをintタイプに変えるだけでいいのですが、呼び出すときは強制的にタイプ変換したほうがいいです.
ソースコードを次に示します
int Euclid_inv(int a, int m)
{
// step 1
int u = 1, g = a, v1 = 0, v3 = m;
int t3;
do
{
// step 2
int q = g / v3;
t3 = g % v3;
// step 3
if (t3 != 0) {
int t1 = (u - q*v1) % m;
u = v1;
g = v3;
v1 = t1;
v3 = t3;
}
// step 4
} while (t3 != 0);
g = v3;
// step 5
if (g != 1)
return 0; // inverse element did not existed
if (g == 1)
{
if (v1 > 0)
return v1;
else
return m + v1;
}
}
また、このような学習方法は望ましくない.