Go言語 math/big モジュラ逆元 ModInverse の使い方と注意点

モジュラ逆数とは？

整数 a の m を法とするモジュラ逆数とは、以下の合同式を満たす整数 x のことです。

(a×x)≡1(modm)

ここで、a と m は整数であり、m は正の整数です。モジュラ逆数 x は、m を法として一意に定まります（存在する場合）。

big.Int.ModInverse() の働き

ModInverse() メソッドは、レシーバー（メソッドを呼び出す big.Int 型の変数）の値を a とみなし、引数として渡された big.Int 型の値を m とみなして、a の m を法とするモジュラ逆数を計算します。

メソッドのシグネチャは以下の通りです。

func (z *Int) ModInverse(a, m *Int) *Int

• z: 結果を格納する big.Int 型のポインタです。もし z が nil であれば、新しい big.Int が割り当てられます。
• m: 法となる正の big.Int 型の整数です。
• a: 逆数を求めたい big.Int 型の整数です。

戻り値

• モジュラ逆数が存在しない場合（つまり、a と m が互いに素でない場合）、ModInverse() は nil を返します。
• a の m を法とするモジュラ逆数が存在する場合、ModInverse() はその逆数を格納した big.Int 型のポインタを返します。

モジュラ逆数が存在する条件

整数 a の m を法とするモジュラ逆数が存在するための必要十分条件は、a と m が互いに素であること、つまり、それらの最大公約数（GCD）が 1 であることです。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(7)
	m := big.NewInt(11)

	inv := new(big.Int)
	inv = inv.ModInverse(a, m)

	if inv != nil {
		fmt.Printf("%s の %s を法とする逆元は %s です\n", a.String(), m.String(), inv.String())
		// 出力: 7 の 11 を法とする逆元は 8 です (7 * 8 = 56 ≡ 1 mod 11)
	} else {
		fmt.Printf("%s と %s は互いに素ではないため、逆元は存在しません\n", a.String(), m.String())
	}

	b := big.NewInt(6)
	n := big.NewInt(9)

	inv2 := new(big.Int)
	inv2 = inv2.ModInverse(b, n)

	if inv2 != nil {
		fmt.Printf("%s の %s を法とする逆元は %s です\n", b.String(), n.String(), inv2.String())
	} else {
		fmt.Printf("%s と %s は互いに素ではないため、逆元は存在しません\n", b.String(), n.String())
		// 出力: 6 と 9 は互いに素ではないため、逆元は存在しません
	}
}

---

法 (modulus) が正の整数でない場合のエラー

エラー内容
ModInverse() のドキュメントには、法 m は正の整数である必要があると明記されています。もし負の整数やゼロを法として渡した場合、メソッドの動作は保証されず、予期しない結果（パニックを含む）を引き起こす可能性があります。

トラブルシューティング

• 対処
  法として使用する変数が意図した通りの正の値を持っているか、その生成過程を見直してください。必要であれば、絶対値を取るなどの処理を追加することも検討してください。
• 確認
  ModInverse() に渡す m の値が big.Int 型で表現された正の整数であることを確認してください。m.Sign() > 0 であるかどうかをチェックすることで確認できます。

逆元が存在しない場合 (a と m が互いに素でない場合)

エラー内容
前述の通り、整数 a の m を法とするモジュラ逆元が存在するための必要十分条件は、a と m が互いに素であること（最大公約数 GCD(a, m) = 1）です。もし a と m が互いに素でない場合、ModInverse() は nil を返します。これはエラーではありませんが、nil チェックを怠ると、返り値の big.Int ポインタに対してメソッドを呼び出そうとしてランタイムエラー（panic: invalid memory address or nil pointer dereference）が発生する可能性があります。

トラブルシューティング

• 対処
  
  • 逆元が存在しない場合に備えて、ModInverse() の戻り値が nil でないことを必ず確認するコードを追加してください。
  • そもそも a と m が互いに素になるような入力値を設計できるか検討してください。
• 確認
  逆元を計算しようとしている a と m が本当に互いに素であるかを確認してください。math/big パッケージの GCD() 関数を使って最大公約数を計算し、その結果が 1 であるかをチェックできます。

結果を格納する big.Int が適切に初期化されていない場合

エラー内容
ModInverse() のレシーバー (z ポインタ) が nil の場合、メソッド内部で新しい big.Int が割り当てられ、そのポインタが返されます。しかし、もし既存の big.Int 変数に結果を格納しようとする場合、その変数が適切に初期化されていることを確認する必要があります。通常は new(big.Int) でポインタを取得するか、既存の big.Int 変数のポインタを渡します。

トラブルシューティング

• 対処
  結果を格納する変数を宣言する際には、inv := new(big.Int) のように初期化するか、既存の big.Int 変数のアドレス (&existingInt) を渡してください。
• 確認
  結果を格納する変数が nil でない big.Int 型のポインタであることを確認してください。

大きすぎる数値や計算コスト

エラー内容
big.Int は非常に大きな整数を扱うことができますが、扱う数値が極端に大きい場合、ModInverse() の計算には相応の時間がかかることがあります。特に、法 m が非常に大きい素数の積である場合など、計算が複雑になることがあります。

トラブルシューティング

• リソース
  計算を実行する環境のリソース（CPU、メモリ）が十分であるかを確認してください。
• 最適化
  もし計算が遅すぎる場合は、他のアルゴリズムやライブラリの利用を検討する余地があるかもしれません（ただし、big.Int は高度に最適化されています）。
• 検討
  アルゴリズム全体を見直し、本当にそのサイズの数値でのモジュラ逆数計算が必要かどうかを検討してください。

誤った変数の使用

エラー内容
コードが複雑になるにつれて、意図しない変数（例えば、法として使うべき変数を誤って被除数として渡してしまうなど）を ModInverse() に渡してしまう可能性があります。

トラブルシューティング

• 確認
  ModInverse(a, m) の呼び出しにおいて、a が逆数を求めたい数、m が法であることを再度確認してください。変数の名前と役割を明確にし、コードを注意深くレビューしてください。

• ドキュメントの再読
  math/big パッケージのドキュメントを再度読み、ModInverse() の仕様と注意点を確認してください。
• テストケース
  さまざまな入力値（互いに素な場合、そうでない場合、境界値など）に対するテストケースを作成し、ModInverse() の動作を確認してください。
• ログ出力
  計算前後の a と m の値をログに出力して確認することで、予期せぬ値が渡されていないかをチェックできます。

---

例1: 基本的なモジュラ逆元の計算

この例では、7 の 11 を法とするモジュラ逆元を計算します。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(7)
	m := big.NewInt(11)

	inv := new(big.Int)
	inv = inv.ModInverse(a, m)

	if inv != nil {
		fmt.Printf("%s の %s を法とする逆元は %s です\n", a.String(), m.String(), inv.String())
	} else {
		fmt.Printf("%s と %s は互いに素ではないため、逆元は存在しません\n", a.String(), m.String())
	}
}

解説

1. big.NewInt(7) と big.NewInt(11) で、それぞれ整数 7 と 11 を big.Int 型として作成しています。
2. inv := new(big.Int) で、結果を格納するための新しい big.Int 型のポインタ inv を作成しています。
3. inv = inv.ModInverse(a, m) で、a (7) の m (11) を法とするモジュラ逆元を計算し、その結果を inv に格納しています。
4. if inv != nil で、逆元が存在するかどうか（つまり、a と m が互いに素であるか）をチェックしています。存在する場合はその値を、存在しない場合はその旨をメッセージとして出力します。

例2: 逆元が存在しない場合の処理

この例では、6 の 9 を法とするモジュラ逆元を計算します。6 と 9 は互いに素ではないため、逆元は存在しません。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	b := big.NewInt(6)
	n := big.NewInt(9)

	inv2 := new(big.Int)
	inv2 = inv2.ModInverse(b, n)

	if inv2 != nil {
		fmt.Printf("%s の %s を法とする逆元は %s です\n", b.String(), n.String(), inv2.String())
	} else {
		fmt.Printf("%s と %s は互いに素ではないため、逆元は存在しません\n", b.String(), n.String())
	}
}

解説

このコードは例1とほぼ同じ構造ですが、入力の値が異なります。b (6) と n (9) は最大公約数が 3 であるため、互いに素ではありません。したがって、ModInverse() は nil を返し、"6 と 9 は互いに素ではないため、逆元は存在しません" というメッセージが出力されます。

例3: 大きな整数のモジュラ逆元計算

暗号理論などで用いられるような大きな整数のモジュラ逆元を計算する例です。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	aStr := "123456789012345678901234567890"
	mStr := "987654321098765432109876543211"

	a := new(big.Int)
	_, ok := a.SetString(aStr, 10)
	if !ok {
		fmt.Println("a の設定に失敗しました")
		return
	}

	m := new(big.Int)
	_, ok = m.SetString(mStr, 10)
	if !ok {
		fmt.Println("m の設定に失敗しました")
		return
	}

	inv := new(big.Int)
	inv = inv.ModInverse(a, m)

	if inv != nil {
		fmt.Printf("%s の %s を法とする逆元は %s です\n", a.String(), m.String(), inv.String())
	} else {
		fmt.Printf("%s と %s は互いに素ではないため、逆元は存在しません\n", a.String(), m.String())
	}
}

解説

1. ここでは、文字列として非常に大きな整数を定義し、big.Int の SetString() メソッドを使って big.Int 型に変換しています。
2. その後は、例1と同様に ModInverse() を呼び出し、結果をチェックしています。この例では、a と m が互いに素である可能性が高いため（特に明示的にそうでないように選んでいない場合）、逆元が存在するでしょう。

例4: エラーハンドリングを明示的に行う

法 m が正の整数でない場合に ModInverse() がどのように振る舞うかは、Go のバージョンや内部実装に依存する可能性があります。一般的には正の整数を期待するため、事前にチェックを行うことが推奨されます。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(5)
	m := big.NewInt(-7) // 負の数を法として使用 (通常は避けるべき)

	if m.Sign() <= 0 {
		fmt.Println("エラー: 法は正の整数である必要があります")
		return
	}

	inv := new(big.Int)
	inv = inv.ModInverse(a, m)

	if inv != nil {
		fmt.Printf("%s の %s を法とする逆元は %s です\n", a.String(), m.String(), inv.String())
	} else {
		fmt.Printf("%s と %s は互いに素ではないため、逆元は存在しません\n", a.String(), m.String())
	}
}

1. この例では、意図的に負の数を法 m として設定しています。
2. if m.Sign() <= 0 で、m が正の整数でない場合にエラーメッセージを出力し、処理を中断しています。このように、ModInverse() を呼び出す前に法が適切な値であることを確認することで、予期しない動作を防ぐことができます。

---

拡張ユークリッド互除法 (Extended Euclidean Algorithm) の実装

モジュラ逆元が存在するための条件は、与えられた整数 a と法 m が互いに素であることです。この条件が満たされる場合、拡張ユークリッド互除法を用いることでモジュラ逆元を計算できます。

拡張ユークリッド互除法は、2つの整数 a と b の最大公約数 (GCD) を求めると同時に、以下のベズーの等式を満たす整数 x と y を見つけるアルゴリズムです。

ax+by=gcd(a,b)

もし a と m が互いに素であれば、gcd(a,m)=1 となり、上記の等式は以下のようになります。

ax+my=1

この式を法 m で考えると、

ax+my≡1(modm) ax≡1(modm)

となり、このときの x が a の m を法とするモジュラ逆元となります。

Go での拡張ユークリッド互除法の実装例

package main

import (
	"fmt"
	"math/big"
)

// 拡張ユークリッド互除法
func extendedGCD(a, b *big.Int) (*big.Int, *big.Int, *big.Int) {
	if b.Cmp(big.NewInt(0)) == 0 {
		return new(big.Int).Set(a), big.NewInt(1), big.NewInt(0)
	}

	gcd, x1, y1 := extendedGCD(b, new(big.Int).Mod(a, b))
	x := new(big.Int).Set(y1)
	y := new(big.Int).Sub(x1, new(big.Int).Mul(new(big.Int).Div(a, b), y1))

	return gcd, x, y
}

// モジュラ逆元を拡張ユークリッド互除法で計算
func modInverseExtendedGCD(a, m *big.Int) *big.Int {
	gcd, x, _ := extendedGCD(a, m)

	if gcd.Cmp(big.NewInt(1)) != 0 {
		return nil // 互いに素でないため、逆元は存在しない
	}

	// x が負の値の場合があるので、m を足して正の値にする
	result := new(big.Int).Mod(x, m)
	if result.Sign() < 0 {
		result.Add(result, m)
	}
	return result
}

func main() {
	a := big.NewInt(7)
	m := big.NewInt(11)
	inv1 := new(big.Int).ModInverse(a, m)
	inv2 := modInverseExtendedGCD(a, m)

	fmt.Printf("%s の %s を法とする逆元 (ModInverse): %s\n", a.String(), m.String(), inv1.String())
	fmt.Printf("%s の %s を法とする逆元 (拡張ユークリッド互除法): %s\n", a.String(), m.String(), inv2.String())

	b := big.NewInt(6)
	n := big.NewInt(9)
	inv3 := new(big.Int).ModInverse(b, n)
	inv4 := modInverseExtendedGCD(b, n)

	fmt.Printf("%s の %s を法とする逆元 (ModInverse): %v\n", b.String(), n.String(), inv3)
	fmt.Printf("%s の %s を法とする逆元 (拡張ユークリッド互除法): %v\n", b.String(), n.String(), inv4)
}

解説

• modInverseExtendedGCD(a, m) 関数は、extendedGCD を利用してモジュラ逆元を計算します。まず、a と m の GCD が 1 であるかを確認し、そうであればベズー係数 x を法 m で剰余演算することで逆元を求めます。x が負の値になる可能性があるので、その場合は m を足して正の値に調整しています。
• extendedGCD(a, b) 関数は、拡張ユークリッド互除法を実装し、gcd(a,b) とベズー係数 x と y を返します。

フェルマーの小定理 (Fermat's Little Theorem) を利用 (法が素数の場合)

法 m が素数 p である場合、a が p の倍数でなければ、フェルマーの小定理より以下の合同式が成り立ちます。

ap−1≡1(modp)

この式を変形すると、

a⋅ap−2≡1(modp)

となり、したがって、ap−2(modp) が a の p を法とするモジュラ逆元となります。

Go でのフェルマーの小定理を利用したモジュラ逆元の計算例

package main

import (
	"fmt"
	"math/big"
)

// 法が素数の場合にフェルマーの小定理を用いてモジュラ逆元を計算
func modInverseFermat(a, p *big.Int) *big.Int {
	if p.ProbablyPrime(1) { // p が素数である可能性が高いかチェック
		exponent := new(big.Int).Sub(p, big.NewInt(2))
		result := new(big.Int).Exp(a, exponent, p)
		return result
	}
	return nil // 法が素数でないか、素数判定に失敗
}

func main() {
	a := big.NewInt(7)
	p := big.NewInt(11) // 11 は素数
	inv1 := new(big.Int).ModInverse(a, p)
	inv2 := modInverseFermat(a, p)

	fmt.Printf("%s の %s を法とする逆元 (ModInverse): %s\n", a.String(), p.String(), inv1.String())
	fmt.Printf("%s の %s を法とする逆元 (フェルマーの小定理): %s\n", a.String(), p.String(), inv2.String())

	b := big.NewInt(5)
	q := big.NewInt(9) // 9 は素数ではない
	inv3 := new(big.Int).ModInverse(b, q)
	inv4 := modInverseFermat(b, q)

	fmt.Printf("%s の %s を法とする逆元 (ModInverse): %v\n", b.String(), q.String(), inv3)
	fmt.Printf("%s の %s を法とする逆元 (フェルマーの小定理): %v\n", b.String(), q.String(), inv4)
}

解説

• 法が素数でない場合や素数判定に失敗した場合は nil を返します。
• もし p が素数であれば、フェルマーの小定理に基づいて ap−2(modp) を計算し、それを逆元として返します。Exp(a, exponent, p) は、aexponent(modp) を効率的に計算する関数です。
• modInverseFermat(a, p) 関数は、法 p が素数である可能性が高いかを ProbablyPrime(1) でチェックします（確率的な判定です）。

注意点

• ProbablyPrime() は確率的な素数判定であり、ごくわずかな確率で合成数を素数と判定する可能性があります。
• フェルマーの小定理は、法が素数の場合にのみ有効です。合成数の場合には一般的に成り立ちません。

• フェルマーの小定理を利用する方法は、法が素数であることが保証されている場合に限って有効です。素数判定のコストや、合成数に対する誤った結果のリスクを考慮する必要があります。
• 拡張ユークリッド互除法を自分で実装する場合は、アルゴリズムの理解を深めるのに役立ちますが、big.Int.ModInverse() ほど効率的でない可能性や、実装ミスによるバグのリスクがあります。
• 一般的には、big.Int.ModInverse() が最も簡潔で効率的な方法です。内部で高度に最適化されたアルゴリズム（通常は拡張ユークリッド互除法の改良版）が使用されています。