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

このコミットは、Go言語の math/big パッケージにおける Int.Exp 関数（多倍長整数での冪剰余計算）のバグ修正に関するものです。具体的には、指数 y が0以下の場合や、法（モジュラス）m が1の場合の挙動が修正され、関連するテストが追加されました。

コミット

コミットハッシュ: 2653386ce8dfd497fb9b8f65bc75ef9adf8e7b58
Author: Robert Griesemer gri@golang.org
Date: Mon Apr 21 15:54:51 2014 -0700

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

https://github.com/golang/go/commit/2653386ce8dfd497fb9b8f65bc75ef9adf8e7b58

元コミット内容

math/big: fix Int.Exp

Fixes #7814.

LGTM=agl, adonovan
R=agl, adonovan
CC=golang-codereviews
https://golang.org/cl/90080043

変更の背景

このコミットは、Go言語の math/big パッケージの Int.Exp 関数におけるバグ（Issue 7814）を修正するために行われました。Int.Exp(x, y, m) は x^y mod m を計算する関数ですが、特に以下のエッジケースでの挙動が問題となっていました。

指数 y が0以下の場合: x^0 は通常1と定義されますが、Int.Exp の実装がこのケースを正しく扱っていませんでした。
法 m が1の場合: 任意の整数 A に対して A mod 1 は常に 0 となります。しかし、Int.Exp が m=1 の場合に x^y mod 1 を正しく 0 として返さないケースがありました。特に x^0 mod 1 の結果が 1 となるべきか 0 となるべきかについて議論があり、最終的に 0 が正しいという結論に至りました。

これらの不正確な挙動は、math/big パッケージの正確性と信頼性を損なうものであり、修正が急務でした。

前提知識の解説

`math/big` パッケージ

math/big パッケージは、Go言語で任意精度の算術演算（多倍長整数、有理数、浮動小数点数）を扱うための標準ライブラリです。通常のGoの組み込み型（int, int64 など）では表現できない非常に大きな数や、高い精度が要求される計算に用いられます。

冪剰余 (Modular Exponentiation)

冪剰余とは、(base^exponent) mod modulus の形式で計算される演算です。これは、暗号技術（RSA暗号など）や数論において非常に重要な演算であり、効率的なアルゴリズム（バイナリ法など）が用いられます。

Int.Exp 関数は、この冪剰余を多倍長整数で行うためのものです。

z.Exp(x, y, m) は z = x^y mod |m| を計算します。
x: 基数 (base)
y: 指数 (exponent)
m: 法 (modulus)

`nat` 型

math/big パッケージの内部では、符号なしの多倍長整数を表現するために nat 型が使用されています。これは []Word のエイリアスであり、Word はプラットフォームのワードサイズ（通常は uint）に対応します。nat 型のメソッドは、多倍長整数の基本的な算術演算（加算、減算、乗算、除算など）を実装しています。

`expNN` メソッド

nat.expNN(x, y, m) は、nat 型の数値に対する冪剰余計算を行う内部ヘルパー関数です。Int.Exp はこの expNN を呼び出して実際の計算を行います。

技術的詳細

このコミットの技術的な修正は、主に Int.Exp 関数と、それが内部で呼び出す nat.expNN メソッドに集中しています。

`Int.Exp` の修正点

元の Int.Exp 関数では、指数 y が負またはゼロの場合 (y.neg || len(y.abs) == 0) に、無条件に z.SetInt64(1) を返していました。これは x^0 = 1 という数学的定義に基づいたものでしたが、法 m が存在する場合（特に m=1 の場合）に問題が生じました。

修正後のコードでは、まず y が負でない場合に y.abs を yWords として使用するように変更されました。これにより、y が負の場合でも yWords が空（ゼロ）となり、expNN に渡される指数が正しく処理されるようになります。

最も重要な変更は、z.neg の設定ロジックです。元のコード: z.neg = len(z.abs) > 0 && x.neg && y.abs[0]&1 == 1 修正後: z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1

この変更は、y がゼロの場合（len(yWords) == 0）に yWords[0] にアクセスしようとするとパニックを起こす可能性があったため、len(yWords) > 0 のチェックが追加されました。これにより、y がゼロの場合に x.neg と y.abs[0]&1 == 1 の条件が評価されなくなり、z.neg が正しく false に設定されるようになります（x^0 は常に正の1であるため）。

`nat.expNN` の修正点

nat.expNN メソッドでは、以下の2つの重要な修正が行われました。

m == 1 のケースの追加:
```
// x**y mod 1 == 0
if len(m) == 1 && m[0] == 1 {
    return z.setWord(0)
}
```
このコードブロックが追加され、法 m が1である場合（len(m) == 1 && m[0] == 1）には、結果が常に 0 となるように明示的に処理されます。これは、任意の整数 A に対して A mod 1 = 0 という数学的性質に基づいています。これにより、x^0 mod 1 のようなケースでも正しい 0 が返されるようになります。
y == 0 のケースの簡素化: 元のコード:
```
if len(y) == 0 {
    z = z.make(1)
    z[0] = 1
    return z
}
```
修正後:
```
if len(y) == 0 {
    return z.setWord(1)
}
```
指数 y がゼロの場合（len(y) == 0）、x^0 は 1 となります。この修正では、z.setWord(1) を使用して、より簡潔かつ効率的に 1 を設定するように変更されました。

これらの修正により、Int.Exp 関数は、指数がゼロまたは負の場合、および法が1の場合を含む、より広範なエッジケースで数学的に正しい結果を返すようになりました。

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

`src/pkg/math/big/int.go`

--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -576,21 +576,22 @@ func (x *Int) BitLen() int {
 }
 
 // Exp sets z = x**y mod |m| (i.e. the sign of m is ignored), and returns z.
-// If y <= 0, the result is 1; if m == nil or m == 0, z = x**y.
+// If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y.
 // See Knuth, volume 2, section 4.6.3.
 func (z *Int) Exp(x, y, m *Int) *Int {
-	if y.neg || len(y.abs) == 0 {
-		return z.SetInt64(1)
+	var yWords nat
+	if !y.neg {
+		yWords = y.abs
 	}
-	// y > 0
+	// y >= 0
 
 	var mWords nat
 	if m != nil {
 		mWords = m.abs // m.abs may be nil for m == 0
 	}
 
-	z.abs = z.abs.expNN(x.abs, y.abs, mWords)
-	z.neg = len(z.abs) > 0 && x.neg && y.abs[0]&1 == 1 // 0 has no sign
+	z.abs = z.abs.expNN(x.abs, yWords, mWords)
+	z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 // 0 has no sign
 	return z
 }

`src/pkg/math/big/nat.go`

--- a/src/pkg/math/big/nat.go
+++ b/src/pkg/math/big/nat.go
@@ -1233,10 +1233,15 @@ func (z nat) expNN(x, y, m nat) nat {
 		z = nil
 	}
 
+	// x**y mod 1 == 0
+	if len(m) == 1 && m[0] == 1 {
+		return z.setWord(0)
+	}
+	// m == 0 || m > 1
+
+	// x**0 == 1
 	if len(y) == 0 {
-		z = z.make(1)
-		z[0] = 1
-		return z
+		return z.setWord(1)
 	}
 	// y > 0

yWords の導入:
- 以前は y.abs を直接使用していましたが、y が負の場合に y.abs が空（nil）になる可能性がありました。
- var yWords nat を宣言し、if !y.neg { yWords = y.abs } とすることで、y が負の場合でも yWords が適切にゼロ値（空の nat）に初期化され、expNN に渡される指数が常に有効な nat 型として扱われるようになりました。これにより、y <= 0 のケースがより堅牢に処理されます。
コメントの更新:
- // If y <= 0, the result is 1; if m == nil or m == 0, z = x**y. から // If y <= 0, the result is 1 mod |m|; if m == nil or m == 0, z = x**y. に変更されました。これは、y <= 0 の場合の 1 が法 m の影響を受けることを明確に示しています。
- // y > 0 から // y >= 0 に変更され、指数がゼロの場合も考慮されるようになりました。
z.neg の条件修正:
- z.neg = len(z.abs) > 0 && x.neg && y.abs[0]&1 == 1 から z.neg = len(z.abs) > 0 && x.neg && len(yWords) > 0 && yWords[0]&1 == 1 に変更されました。
- len(yWords) > 0 の条件が追加されたことで、yWords が空（つまり指数がゼロ）の場合に yWords[0] への不正なアクセスを防ぎます。これにより、x^0 の結果の符号が常に正しく false に設定されることが保証されます。

`src/pkg/math/big/nat.go` の変更解説

m == 1 の特殊ケース処理:
- if len(m) == 1 && m[0] == 1 { return z.setWord(0) } が追加されました。
- これは、法 m が 1 である場合、どのような基数 x と指数 y であっても、x^y mod 1 の結果は常に 0 になるという数学的性質を直接実装したものです。これにより、m=1 のエッジケースが正確に処理されます。
y == 0 の簡素化:
- if len(y) == 0 { return z.setWord(1) } に変更されました。
- 以前は z.make(1) と z[0] = 1 を使っていましたが、z.setWord(1) は nat 型のインスタンスを生成し、その値を 1 に設定するヘルパー関数であり、コードがより簡潔で読みやすくなりました。これは、x^0 = 1 という定義を効率的に実装しています。

これらの変更は、math/big パッケージの堅牢性と正確性を向上させ、特にエッジケースにおける冪剰余計算の信頼性を高めるものです。

参考にした情報源リンク

Go Change List 90080043 の議論内容
Go言語の math/big パッケージのドキュメント (GoDoc)
冪剰余に関する一般的な数学的定義とアルゴリズム

comemo