情報セキュリティ試験の授業で出会った問題

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タイプに変えるだけでいいのですが、呼び出すときは強制的にタイプ変換したほうがいいです.
ソースコードを次に示します
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;
	}
}

また、このような学習方法は望ましくない.