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

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

このコミットは、Go言語の標準ライブラリmath/bigパッケージにおけるAPIとドキュメンテーションのクリーンアップを目的としています。特に、ProbablyPrime関数とGcdInt関数がパッケージレベルの関数から*Int型のメソッドへと変更され、よりオブジェクト指向的なアプローチが採用されました。これにより、これらの関数がbig.Intのインスタンスに直接関連付けられ、コードの可読性と一貫性が向上しています。

コミット

commit b80c7e5dfd71508ed754ec2a02caa51f4444ba10
Author: Robert Griesemer <gri@golang.org>
Date:   Thu Feb 2 19:21:55 2012 -0800

    math/big: API, documentation cleanup
    
    Fixes #2863.
    
    R=golang-dev, rsc
    CC=golang-dev
    https://golang.org/cl/5620058

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

https://github.com/golang/go/commit/b80c7e5dfd71508ed754ec2a02caa51f4444ba10

元コミット内容

math/big: API, documentation cleanup

Fixes #2863.

変更の背景

このコミットの主な背景は、Go言語のmath/bigパッケージのAPI設計の一貫性を向上させることと、関連するドキュメンテーションを整理することにあります。コミットメッセージにあるFixes #2863は、GoのIssueトラッカーにおける特定の課題を解決することを示唆しています。

Issue #2863（"math/big: ProbablyPrime should be a method"）の内容は、math/big.ProbablyPrime関数がパッケージレベルの関数として定義されていることに対し、big.Int型のメソッドとして提供されるべきではないかという提案でした。これは、ProbablyPrimeが特定のbig.Intインスタンスに対して素数判定を行うため、そのインスタンスのメソッドとして存在することがより自然で、APIの利用方法を直感的にするという考えに基づいています。

同様に、GcdInt関数もパッケージレベルの関数でしたが、これもbig.Int型のメソッドとして再設計することで、math/bigパッケージ全体のAPIデザインがより統一され、利用者が混乱することなく、よりGoらしい（idiomatic Go）コードを書けるようにすることが意図されています。

これらの変更は、Go言語がまだ比較的新しい時期に行われたものであり、ライブラリのAPIが成熟し、より使いやすく、一貫性のあるものになるように継続的に改善されていた過程の一部です。

前提知識の解説

math/bigパッケージ

math/bigパッケージは、Go言語で任意精度（arbitrary-precision）の算術演算を可能にするためのパッケージです。通常のGoの組み込み型（int, int64など）では表現できない非常に大きな整数や、高精度な浮動小数点数、有理数を扱う際に使用されます。暗号化、科学計算、金融アプリケーションなど、精度が非常に重要となる分野で不可欠です。

big.Int型

math/bigパッケージの主要な型の一つで、任意精度の整数を表します。この型は、通常の整数型ではオーバーフローしてしまうような巨大な数値を扱うことができます。big.Intのインスタンスは、その値を変更するメソッド（例: Add, Mul, SetBytesなど）や、その値に関する情報を提供するメソッド（例: Cmp, Signなど）を持っています。

ミラー-ラビン素数判定法 (Miller-Rabin Primality Test)

ProbablyPrime関数（変更後はメソッド）は、ミラー-ラビン素数判定法を実装しています。これは、与えられた数が素数であるかどうかを確率的に判定するアルゴリズムです。

  • 確率的: このテストは、ある数が素数であると「確信」する確率を返しますが、100%の確実性はありません。ただし、テストの繰り返し回数（n）を増やすことで、誤って合成数を素数と判定する確率を非常に低くすることができます（1 - 1/4^n）。
  • 用途: 暗号学において、大きな素数を生成する際に広く利用されます。例えば、RSA暗号やDSA（Digital Signature Algorithm）のような公開鍵暗号システムでは、安全な鍵を生成するために非常に大きな素数が必要です。

最大公約数 (Greatest Common Divisor, GCD)

GCD関数（変更後はメソッド）は、2つの整数の最大公約数を計算します。最大公約数とは、2つの整数に共通する約数の中で最大のものです。

  • ユークリッドの互除法: GCDの計算には、通常、ユークリッドの互除法が用いられます。
  • 拡張ユークリッドの互除法: GCD関数は、単に最大公約数を計算するだけでなく、拡張ユークリッドの互除法に基づいて、d = a*x + b*yとなるような整数xとyも計算できます。ここでdはaとbの最大公約数です。
  • 用途: 暗号学において、モジュラ逆元（Modular Multiplicative Inverse）の計算などに不可欠です。例えば、RSA暗号の鍵生成プロセスでは、公開鍵と秘密鍵の導出にGCDやモジュラ逆元の計算が使われます。

APIの設計原則（パッケージレベル関数 vs. メソッド）

Go言語におけるAPI設計では、特定のデータ型に密接に関連する操作は、その型のメソッドとして定義することが推奨されます。これにより、コードの可読性が向上し、オブジェクト指向的なアプローチが促進されます。

  • パッケージレベル関数: func F(x T, args...) の形式。T型とは直接関連しない汎用的な操作や、複数の型にまたがる操作に適しています。
  • メソッド: func (recv T) M(args...) の形式。recv（レシーバ）であるT型のインスタンスに対して操作を行う場合に適しています。このコミットでは、ProbablyPrimeとGCDがbig.Intのインスタンスに対する操作であるため、メソッド化されました。

技術的詳細

このコミットの核心的な変更は、math/bigパッケージ内の2つの重要な関数、ProbablyPrimeとGcdIntが、パッケージレベルの関数から*big.Int型のメソッドへと移行した点です。

ProbablyPrimeの変更

  • 変更前: func ProbablyPrime(x *Int, n int) bool
    • math/bigパッケージのグローバル関数として定義されていました。
    • 呼び出し例: big.ProbablyPrime(q, numMRTests)
  • 変更後: func (x *Int) ProbablyPrime(n int) bool
    • *big.Int型のメソッドとして定義されました。
    • 呼び出し例: q.ProbablyPrime(numMRTests)
  • 理由: ProbablyPrimeは、特定のbig.Intインスタンス（x）が素数であるかどうかを判定する機能を提供します。この機能はxというインスタンスに密接に関連しているため、パッケージレベルの関数としてではなく、xのメソッドとして提供する方が、より自然でGoのイディオムに沿ったAPI設計となります。これにより、コードの可読性が向上し、「qという大きな数が素数かどうかを判定する」という意図がq.ProbablyPrime()という記述からより明確に伝わるようになります。

GcdIntの変更

  • 変更前: func GcdInt(d, x, y, a, b *Int)
    • math/bigパッケージのグローバル関数として定義されていました。
    • 呼び出し例: big.GcdInt(gcd, x, y, totient, e)
  • 変更後: func (z *Int) GCD(x, y, a, b *Int) *Int
    • *big.Int型のメソッドとして定義され、関数名もGCDに短縮されました。
    • 呼び出し例: gcd.GCD(x, y, totient, e)
  • 理由: GcdIntは、2つの大きな整数aとbの最大公約数を計算し、その結果をdに格納します。また、拡張ユークリッドの互除法によりa*x + b*y = dとなるxとyも計算します。この関数も、結果を格納するd（変更後はz）がbig.Intのインスタンスであるため、そのインスタンスのメソッドとして提供する方が適切です。メソッド化により、gcdというbig.Intインスタンスが自身の最大公約数を計算する、という直感的な操作が可能になります。また、関数名がGcdIntからGCDに短縮されたことで、より簡潔なAPIになりました。

ドキュメンテーションのクリーンアップ

コミットメッセージに「documentation cleanup」とあるように、これらのAPI変更に伴い、関連するドキュメンテーションも更新されています。特に、QuoRemとDivModのコメントが修正され、それぞれの関数がGoのT-division/modulusとEuclidean division/modulusのどちらに対応しているかが明確化されました。これは、Goの整数除算と剰余演算の挙動が他の言語と異なる場合があるため、利用者が混乱しないようにするための重要な改善です。

影響範囲

これらのAPI変更は、math/bigパッケージを利用している他の標準ライブラリパッケージにも影響を与えています。具体的には、crypto/dsa、crypto/rand、crypto/rsaといった暗号関連のパッケージで、big.ProbablyPrimeやbig.GcdIntの呼び出しが、それぞれInt型のメソッド呼び出しに修正されています。これは、APIの変更が下位互換性を損なう可能性があるため、ライブラリ全体で一貫した修正が必要であることを示しています。

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

このコミットにおける主要なコード変更は、src/pkg/math/big/int.goにおけるProbablyPrimeとGcdIntのシグネチャ変更と、それらの関数を呼び出していた他のファイル（src/pkg/crypto/dsa/dsa.go, src/pkg/crypto/rand/util.go, src/pkg/crypto/rsa/rsa.go, src/pkg/math/big/int_test.go）における呼び出し箇所の修正です。

src/pkg/crypto/dsa/dsa.go

--- a/src/pkg/crypto/dsa/dsa.go
+++ b/src/pkg/crypto/dsa/dsa.go
@@ -102,7 +102,7 @@ GeneratePrimes:
 		qBytes[0] |= 0x80
 		q.SetBytes(qBytes)
 
-		if !big.ProbablyPrime(q, numMRTests) {
+		if !q.ProbablyPrime(numMRTests) {
 			continue
 		}
 
@@ -123,7 +123,7 @@ GeneratePrimes:
 				continue
 			}
 
-			if !big.ProbablyPrime(p, numMRTests) {
+			if !p.ProbablyPrime(numMRTests) {
 				continue
 			}
  • big.ProbablyPrime(q, numMRTests) が q.ProbablyPrime(numMRTests) に変更。
  • big.ProbablyPrime(p, numMRTests) が p.ProbablyPrime(numMRTests) に変更。

src/pkg/crypto/rand/util.go

--- a/src/pkg/crypto/rand/util.go
+++ b/src/pkg/crypto/rand/util.go
@@ -39,7 +39,7 @@ func Prime(rand io.Reader, bits int) (p *big.Int, err error) {
 		bytes[len(bytes)-1] |= 1
 
 		p.SetBytes(bytes)
-		if big.ProbablyPrime(p, 20) {
+		if p.ProbablyPrime(20) {
 			return
 		}
 	}
  • big.ProbablyPrime(p, 20) が p.ProbablyPrime(20) に変更。

src/pkg/crypto/rsa/rsa.go

--- a/src/pkg/crypto/rsa/rsa.go
+++ b/src/pkg/crypto/rsa/rsa.go
@@ -62,7 +62,7 @@ func (priv *PrivateKey) Validate() error {
 	// ProbablyPrime are deterministic, given the candidate number, it's
 	// easy for an attack to generate composites that pass this test.
 	for _, prime := range priv.Primes {
-		if !big.ProbablyPrime(prime, 20) {
+		if !prime.ProbablyPrime(20) {
 			return errors.New("prime factor is composite")
 		}
 	}
@@ -85,7 +85,7 @@ func (priv *PrivateKey) Validate() error {
 	gcd := new(big.Int)
 	x := new(big.Int)
 	y := new(big.Int)
-	big.GcdInt(gcd, x, y, totient, e)
+	gcd.GCD(x, y, totient, e)
 	if gcd.Cmp(bigOne) != 0 {
 		return errors.New("invalid public exponent E")
 	}
@@ -156,7 +156,7 @@ NextSetOfPrimes:
 		priv.D = new(big.Int)
 		y := new(big.Int)
 		e := big.NewInt(int64(priv.E))
-		big.GcdInt(g, priv.D, y, e, totient)
+		g.GCD(priv.D, y, e, totient)
 
 		if g.Cmp(bigOne) == 0 {
 			priv.D.Add(priv.D, totient)
@@ -284,7 +284,7 @@ func modInverse(a, n *big.Int) (ia *big.Int, ok bool) {
 	g := new(big.Int)
 	x := new(big.Int)
 	y := new(big.Int)
-	big.GcdInt(g, x, y, a, n)
+	g.GCD(x, y, a, n)
 	if g.Cmp(bigOne) != 0 {
 		// In this case, a and n aren't coprime and we cannot calculate
 		// the inverse. This happens because the values of n are nearly
  • big.ProbablyPrime(prime, 20) が prime.ProbablyPrime(20) に変更。
  • big.GcdInt(gcd, x, y, totient, e) が gcd.GCD(x, y, totient, e) に変更。
  • big.GcdInt(g, priv.D, y, e, totient) が g.GCD(priv.D, y, e, totient) に変更。
  • big.GcdInt(g, x, y, a, n) が g.GCD(x, y, a, n) に変更。

src/pkg/math/big/int.go

--- a/src/pkg/math/big/int.go
+++ b/src/pkg/math/big/int.go
@@ -211,6 +211,7 @@ func (z *Int) Rem(x, y *Int) *Int {
 //
 // (See Daan Leijen, ``Division and Modulus for Computer Scientists'''.)
 // See DivMod for Euclidean division and modulus (unlike Go).
+// See DivMod for Euclidean division and modulus (unlike Go).
 //
 func (z *Int) QuoRem(x, y, r *Int) (*Int, *Int) {
  z.abs, r.abs = z.abs.div(r.abs, x.abs, y.abs)
@@ -268,6 +269,7 @@ func (z *Int) Mod(x, y *Int) *Int {
 // div and mod'''. ACM Transactions on Programming Languages and
 // Systems (TOPLAS), 14(2):127-144, New York, NY, USA, 4/1992.
 // ACM press.)
+// See QuoRem for T-division and modulus (like Go).
 //
 func (z *Int) DivMod(x, y, m *Int) (*Int, *Int) {
  y0 := y // save y
@@ -579,20 +581,20 @@ func (z *Int) Exp(x, y, m *Int) *Int {
  return z
 }
 
-// GcdInt sets d to the greatest common divisor of a and b, which must be
-// positive numbers.
-// If x and y are not nil, GcdInt sets x and y such that d = a*x + b*y.
-// If either a or b is not positive, GcdInt sets d = x = y = 0.
-func GcdInt(d, x, y, a, b *Int) {
+// GCD sets z to the greatest common divisor of a and b, which must be
+// positive numbers, and returns z.
+// If x and y are not nil, GCD sets x and y such that z = a*x + b*y.
+// If either a or b is not positive, GCD sets z = x = y = 0.
+func (z *Int) GCD(x, y, a, b *Int) *Int {
  if a.neg || b.neg {
- d.SetInt64(0)
+ z.SetInt64(0)
  if x != nil {
  x.SetInt64(0)
  }
  if y != nil {
  y.SetInt64(0)
  }
- return
+ return z
  }
 
  A := new(Int).Set(a)
@@ -634,13 +636,14 @@ func GcdInt(d, x, y, a, b *Int) {
  *y = *lastY
  }
 
- *d = *A
+ *z = *A
+ return z
 }
 
 // ProbablyPrime performs n Miller-Rabin tests to check whether x is prime.
 // If it returns true, x is prime with probability 1 - 1/4^n.
 // If it returns false, x is not prime.
-func ProbablyPrime(x *Int, n int) bool {
+func (x *Int) ProbablyPrime(n int) bool {
  return !x.neg && x.abs.probablyPrime(n)
 }
 
@@ -659,7 +662,7 @@ func (z *Int) Rand(rnd *rand.Rand, n *Int) *Int {
 // p is a prime) and returns z.
 func (z *Int) ModInverse(g, p *Int) *Int {
  var d Int
- GcdInt(&d, z, nil, g, p)
+ d.GCD(z, nil, g, p)
  // x and y are such that g*x + p*y = d. Since p is prime, d = 1. Taking
  // that modulo p results in g*x = 1, therefore x is the inverse element.
  if z.neg {
  • func GcdInt(d, x, y, a, b *Int) が func (z *Int) GCD(x, y, a, b *Int) *Int に変更。
  • func ProbablyPrime(x *Int, n int) bool が func (x *Int) ProbablyPrime(n int) bool に変更。
  • GcdInt(&d, z, nil, g, p) が d.GCD(z, nil, g, p) に変更。
  • QuoRemとDivModのコメントが更新され、それぞれがGoのT-division/modulusとEuclidean division/modulusのどちらに対応しているかが明確化。

src/pkg/math/big/int_test.go

--- a/src/pkg/math/big/int_test.go
+++ b/src/pkg/math/big/int_test.go
@@ -824,7 +824,7 @@ func checkGcd(aBytes, bBytes []byte) bool {
  y := new(Int)
  d := new(Int)
 
- GcdInt(d, x, y, a, b)
+ d.GCD(x, y, a, b)
  x.Mul(x, a)
  y.Mul(y, b)
  x.Add(x, y)
@@ -852,7 +852,7 @@ func TestGcd(t *testing.T) {
  expectedY := NewInt(test.y)
  expectedD := NewInt(test.d)
 
- GcdInt(d, x, y, a, b)
+ d.GCD(x, y, a, b)
 
  if expectedX.Cmp(x) != 0 ||
  expectedY.Cmp(y) != 0 ||
@@ -903,14 +903,14 @@ func TestProbablyPrime(t *testing.T) {
  }
  for i, s := range primes {
  p, _ := new(Int).SetString(s, 10)
- if !ProbablyPrime(p, nreps) {
+ if !p.ProbablyPrime(nreps) {
  t.Errorf("#%d prime found to be non-prime (%s)", i, s)
  }
  }
 
  for i, s := range composites {
  c, _ := new(Int).SetString(s, 10)
- if ProbablyPrime(c, nreps) {
+ if c.ProbablyPrime(nreps) {
  t.Errorf("#%d composite found to be prime (%s)", i, s)
  }
  if testing.Short() {
  • GcdInt(d, x, y, a, b) が d.GCD(x, y, a, b) に変更。
  • ProbablyPrime(p, nreps) が p.ProbablyPrime(nreps) に変更。
  • ProbablyPrime(c, nreps) が c.ProbablyPrime(nreps) に変更。

コアとなるコードの解説

このコミットの主要な変更は、math/bigパッケージのProbablyPrimeとGcdIntという2つの関数が、*big.Int型のメソッドへと移行したことです。

ProbablyPrimeのメソッド化

変更前は、ProbablyPrimeはmath/bigパッケージのトップレベル関数として、big.ProbablyPrime(x, n)のように呼び出されていました。これは、xがbig.Intのポインタであるにもかかわらず、関数がbigパッケージの名前空間に属しているため、xという特定のインスタンスに対する操作であることが直感的に分かりにくいという問題がありました。

変更後は、func (x *Int) ProbablyPrime(n int) boolというメソッドシグネチャになりました。これにより、x.ProbablyPrime(n)のように、big.Intのインスタンスxが直接この素数判定を行うという、より自然でオブジェクト指向的な呼び出し方が可能になります。これはGo言語のイディオムに沿った設計であり、コードの可読性と保守性を向上させます。

GcdIntのメソッド化と名称変更

GcdIntも同様に、変更前はbig.GcdInt(d, x, y, a, b)というトップレベル関数でした。この関数は、aとbの最大公約数を計算し、その結果をdに格納するとともに、拡張ユークリッドの互除法の結果であるxとyも計算します。

変更後は、func (z *Int) GCD(x, y, a, b *Int) *Intというメソッドシグネチャになり、関数名もGCDに短縮されました。これにより、z.GCD(x, y, a, b)のように呼び出すことで、zというbig.Intインスタンスが、aとbの最大公約数を計算し、その結果を自身（z）に格納するという意味合いが明確になります。メソッドが自身のレシーバを結果として返す（return z）ことで、メソッドチェーンのような記述も可能になり、APIの柔軟性が向上します。

ドキュメンテーションの改善

QuoRemとDivModのコメント修正は、Goの整数除算と剰余演算の挙動に関する一般的な混乱を解消するためのものです。Goの%演算子は「T-division」と呼ばれる挙動（結果の符号が被除数と同じになる）をしますが、数学的な文脈では「Euclidean division」（結果の符号が除数と同じになるか、常に非負になる）が好まれることがあります。このコミットでは、QuoRemがGoの%演算子と同様のT-divisionに対応し、DivModがEuclidean divisionに対応することを明記することで、利用者が適切な関数を選択できるようにしています。

これらの変更は、math/bigパッケージのAPIをより一貫性があり、直感的で、Goの設計原則に沿ったものにするための重要なステップでした。これにより、math/bigパッケージを利用する開発者は、より効率的かつ安全に任意精度演算を扱うことができるようになります。

関連リンク

参考にした情報源リンク