Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

[インデックス 14158] ファイルの概要

このコミットは、Go言語の標準ライブラリ math/big パッケージにおける Int.Exp 関数（多倍長整数に対する冪乗剰余演算）のバグ修正と改善に関するものです。具体的には、指数が0以下の場合の挙動の修正、法（modulus）の符号の扱いに関する明確化、そして法がゼロの場合のゼロ除算パニックの防止が主な変更点です。これにより、関数の堅牢性と正確性が向上し、より予測可能な動作が保証されます。

コミット

  • Author: Robert Griesemer gri@golang.org
  • Date: Tue Oct 16 13:46:27 2012 -0700
  • Commit Message: 
    math/big: fix big.Exp and document better

- always return 1 for y <= 0
- document that the sign of m is ignored
- protect against div-0 panics by treating
  m == 0 the same way as m == nil
- added extra tests

Fixes #4239.

R=agl, remyoudompheng, agl
CC=golang-dev
https://golang.org/cl/6724046

GitHub上でのコミットページへのリンク

https://github.com/golang/go/commit/7565726875d96e4a2bd927ebabc5ea614e602ac4

元コミット内容

math/big: fix big.Exp and document better

- always return 1 for y <= 0
- document that the sign of m is ignored
- protect against div-0 panics by treating
  m == 0 the same way as m == nil
- added extra tests

Fixes #4239.

R=agl, remyoudompheng, agl
CC=golang-dev
https://golang.org/cl/6724046

変更の背景

このコミットは、Go言語の math/big パッケージにおける Int.Exp 関数の既存のバグを修正するために行われました。特に、Fixes #4239 との記述から、GitHub Issue #4239「math/big: Int.Exp returns ±1 whenever the exponent is <= 0」で報告された問題に対処していることがわかります。

元の実装では、指数 y が0以下の場合に Int.Exp が常に ±1 を返してしまうという不正確な挙動がありました。数学的には、任意の非ゼロの数 x に対して x^0 = 1 であり、負の指数 y に対しては x^y = 1/x^(-y) と定義されます。しかし、多倍長整数演算において、特に剰余演算を伴う場合、負の指数やゼロの指数に対する挙動は慎重に定義される必要があります。

また、法 m が nil または 0 の場合にゼロ除算パニックが発生する可能性がありました。これは、剰余演算が定義されない状況であり、関数がクラッシュする原因となります。さらに、法 m の符号が結果に影響を与えるかどうかが不明確であり、ドキュメントによる明確化が求められていました。

これらの問題に対処し、Int.Exp 関数の正確性、堅牢性、および使いやすさを向上させることが、このコミットの背景にあります。

前提知識の解説

math/big パッケージ

math/big パッケージは、Go言語で任意精度の算術演算（多倍長整数、有理数、浮動小数点数）を扱うための標準ライブラリです。通常のGoの組み込み整数型（int, int64など）は固定のビット幅を持つため、非常に大きな数や非常に小さな数を扱う場合には精度が不足したり、オーバーフローが発生したりする可能性があります。math/big パッケージは、これらの制限を克服し、暗号学、科学計算、金融アプリケーションなど、高精度な数値計算が要求される分野で利用されます。

Int.Exp 関数

Int.Exp 関数は、math/big パッケージの Int 型（多倍長整数）に対して、冪乗剰余演算 z = x^y mod m を実行します。

  • x: 基数 (base)
  • y: 指数 (exponent)
  • m: 法 (modulus)

この関数は、特に大きな数 x, y, m を扱う際に効率的なアルゴリズム（例えば、バイナリ法やモンゴメリ法）を用いて計算されます。

冪乗剰余演算 (x^y mod m)

冪乗剰余演算は、x を y 乗した結果を m で割った余りを求める演算です。これは、公開鍵暗号（RSAなど）やハッシュ関数など、多くの暗号学的アルゴリズムの基盤となる重要な演算です。

ゼロ除算

数学において、ゼロによる除算は未定義です。プログラミングにおいては、ゼロ除算を試みると、通常は実行時エラー（パニック、例外など）が発生し、プログラムが異常終了します。Int.Exp 関数において、法 m がゼロである場合、剰余演算がゼロ除算となり、パニックを引き起こす可能性があります。

指数が負の場合の冪乗

通常の整数演算では、x^(-y) は 1 / x^y と定義されます。しかし、整数演算の文脈では、結果が分数になるため、特別な扱いが必要です。math/big の Int 型は整数を扱うため、負の指数に対する冪乗は通常、結果が整数にならないため、定義域外となるか、特定のルール（例えば、常に1を返すなど）が適用されます。

技術的詳細

このコミットでは、Int.Exp 関数の以下の主要な問題に対処しています。

  1. 指数 y <= 0 の場合の挙動の修正:

    • 以前は、y <= 0 の場合に x の符号に応じて ±1 を返していました。
    • 修正後は、y <= 0 の場合は常に 1 を返すように変更されました。これは、数学的な定義 x^0 = 1 に従い、負の指数に対する冪乗剰余演算の一般的な慣例（特に暗号学的な文脈で）に合わせたものです。これにより、関数の予測可能性と一貫性が向上します。

  2. 法 m の符号の無視の明確化:

    • 関数のドキュメントが更新され、z = x**y mod |m| と明記されました。これは、法 m の絶対値が剰余演算に用いられ、m の符号は結果に影響を与えないことを明確にしています。これにより、ユーザーは m の符号について迷うことなく関数を使用できます。

  3. m == 0 の場合のゼロ除算パニックの防止:

    • 以前は、m が nil でないが m.abs がゼロ（つまり m == 0）の場合に、内部の剰余演算でゼロ除算パニックが発生する可能性がありました。
    • 修正後は、m == 0 の場合を m == nil と同じように扱うことで、ゼロ除算パニックを防止しています。m == nil の場合は剰余演算を行わず、単純に x^y を計算します。これにより、m == 0 の場合も同様に剰余演算なしで x^y が計算され、堅牢性が向上します。

  4. 追加テストの導入:

    • これらの修正の正確性を検証するために、新しいテストケースが int_test.go に追加されました。これには、負の指数、ゼロの指数、および m == 0 の場合のテストが含まれます。テストの追加は、回帰を防ぎ、将来の変更に対する安全網を提供します。

これらの変更は、math/big パッケージの Int.Exp 関数の信頼性と使いやすさを大幅に向上させます。

コアとなるコードの変更箇所

このコミットでは、主に以下の3つのファイルが変更されています。

  1. src/pkg/math/big/int.go: Int.Exp 関数の本体が含まれるファイル。

    • func (z *Int) Exp(x, y, m *Int) *Int 関数内の if y.neg || len(y.abs) == 0 { ... } ブロックが変更されました。
      • 以前は z.SetInt64(1) の後に z.neg = neg という行がありましたが、これが削除され、return z.SetInt64(1) と簡潔に記述されるようになりました。これにより、指数が0以下の場合に常に 1 を返すことが保証されます。
    • var mWords nat の初期化部分で、m != nil のチェックに加えて、コメント // m.abs may be nil for m == 0 が追加され、m == 0 の場合の考慮が示唆されています。
    • 関数のドキュメントコメントが // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z. に変更され、法 m の符号が無視されることが明記されました。また、If y <= 0, the result is 1; if m == nil or m == 0, z = x**y. という記述が追加され、y <= 0 と m == nil または m == 0 の場合の挙動が明確化されました。

  2. src/pkg/math/big/int_test.go: Int.Exp 関数のテストが含まれるファイル。

    • expTests スライスに新しいテストケースが追加されました。
      • {"5", "-7", "", "1"}: 正の基数と負の指数
      • {"-5", "-7", "", "1"}: 負の基数と負の指数
      • {"-5", "0", "", "1"}: 負の基数とゼロの指数（以前は -1 を期待していたが 1 に変更）
      • {"0x8000000000000000", "-1000000", "6719", "1"}: 非常に大きな基数と負の指数、剰余あり
    • TestExp 関数内で、m == nil の場合の追加テストロジックが追加されました。
      • m == nil の場合、m = &Int{abs: nat{}} (つまり m == 0 を表現) を設定して再度 Exp を呼び出し、m == nil の場合と m == 0 の場合の結果が同じになることを検証しています。これは、m == 0 の場合もゼロ除算パニックを起こさずに x^y を計算することを確認するためです。

  3. src/pkg/math/big/nat.go: nat 型（多倍長自然数）の内部演算が含まれるファイル。Int.Exp から呼び出される expNN 関数が変更されています。

    • func (z nat) expNN(x, y, m nat) nat 関数のドキュメントコメントが // If m != 0 (i.e., len(m) != 0), expNN sets z to x**y mod m; // otherwise it sets z to x**y. The result is the value of z. に変更され、m == 0 の場合の挙動が明確化されました。
    • if m != nil { ... } の条件が if len(m) != 0 { ... } に変更されました。これは、m が nil でないが m の内部表現である nat スライスが空（つまり m == 0）の場合を適切に処理するためです。これにより、m == 0 の場合も剰余演算を行わないパスに入るようになります。
    • v := y[len(y)-1] の行に // v > 0 because y is normalized and y > 0 というコメントが追加され、y が正規化されており、y > 0 であることが前提となっていることを示しています。

コアとなるコードの解説

int.go の変更

 func (z *Int) Exp(x, y, m *Int) *Int {
 	if y.neg || len(y.abs) == 0 {
-		neg := x.neg
-		z.SetInt64(1)
-		z.neg = neg
-		return z
+		return z.SetInt64(1)
 	}
+	// y > 0

この変更は、指数 y が負またはゼロの場合の Int.Exp の挙動を修正しています。以前は、x の符号に応じて z.neg を設定していましたが、これは x^0 = 1 という数学的定義や、負の指数に対する冪乗剰余演算の一般的な慣例（結果が常に 1 となる）と一致しませんでした。新しいコード return z.SetInt64(1) は、y <= 0 の場合に常に 1 を返すことを保証します。これにより、関数の動作がより予測可能で、数学的に正確になります。

 	var mWords nat
 	if m != nil {
-		mWords = m.abs
+		mWords = m.abs // m.abs may be nil for m == 0
 	}

この変更は、m が nil でない場合に m.abs を mWords に代入する部分にコメントを追加しています。m.abs は m の絶対値を表す nat 型のスライスですが、m が 0 の場合、m.abs は空のスライス（nil と同等に扱われることがある）になる可能性があります。このコメントは、その可能性を指摘し、後続の expNN 関数が m == 0 の場合を適切に処理する必要があることを示唆しています。

int_test.go の変更

 var expTests = []struct {
 	x, y, m string
 	out     string
 }{
+	{"5", "-7", "", "1"},
+	{"-5", "-7", "", "1"},
 	{"5", "0", "", "1"},
-	{"-5", "0", "", "-1"},
+	{"-5", "0", "", "1"},
 	// ...
+	{"0x8000000000000000", "-1000000", "6719", "1"},
 	// ...
 }

テストケースの変更は、y <= 0 の場合の Int.Exp の新しい挙動を反映しています。特に、{"-5", "0", "", "-1"} が {"-5", "0", "", "1"} に変更されたことは、負の基数であっても指数がゼロの場合は結果が 1 になるという修正を直接テストしています。負の指数を持つ新しいテストケースも追加され、この修正が広範囲にわたって正しいことを確認しています。

 	z1 := new(Int).Exp(x, y, m)
 	if !isNormalized(z1) {
 		t.Errorf("#%d: %v is not normalized", i, *z1)
 	}
 	if z1.Cmp(out) != 0 {
 		t.Errorf("#%d: got %s want %s", i, z1, out)
 	}

 	if m == nil {
 		// the result should be the same as for m == 0;
 		// specifically, there should be no div-zero panic
 		m = &Int{abs: nat{}} // m != nil && len(m.abs) == 0
 		z2 := new(Int).Exp(x, y, m)
 		if z2.Cmp(z1) != 0 {
 			t.Errorf("#%d: got %s want %s", i, z1, z2)
 		}
 	}

このテストロジックの追加は非常に重要です。m == nil の場合と m == 0 の場合（m = &Int{abs: nat{}} でシミュレート）で Int.Exp の結果が同じになることを検証しています。これは、m == 0 の場合にゼロ除算パニックが発生せず、m == nil の場合と同様に剰余演算なしで x^y が計算されることを保証するためのものです。

nat.go の変更

 // If m != 0 (i.e., len(m) != 0), expNN sets z to x**y mod m;
 // otherwise it sets z to x**y. The result is the value of z.
 func (z nat) expNN(x, y, m nat) nat {
 	// ...
-	if m != nil {
+	if len(m) != 0 {
 		// We likely end up being as long as the modulus.
 		z = z.make(len(m))
 	}
 	// ...
 }

nat.go の expNN 関数は、Int.Exp から呼び出される内部関数で、実際の冪乗剰余計算を行います。この変更は、if m != nil の条件を if len(m) != 0 に変更しています。

  • m != nil: これは m がポインタとして nil でないことをチェックします。しかし、math/big の Int 型は内部で nat 型のスライス abs を持っており、Int が 0 の場合、その abs スライスは空（len(abs) == 0）になることがあります。
  • len(m) != 0: これは m が表す nat スライスが空でないことをチェックします。m が 0 の場合、len(m) は 0 になります。

この変更により、m が 0 の場合（m.abs が空のスライスの場合）でも、len(m) != 0 の条件が false となり、剰余演算を行うブロックに入らなくなります。これにより、m == 0 の場合にゼロ除算パニックを回避し、m == nil の場合と同様に剰余なしの冪乗計算が行われるようになります。

関連リンク

参考にした情報源リンク