big.Int.Mod()

通常のGoの組み込み型（int, int64など）では表現できないような大きな数を扱う際に、math/bigパッケージのbig.Int型を使用します。

func (z *Int) Mod(x, y *Int) *Int

このメソッドは、以下のように動作します。

1. x を y で割ったときの剰余を計算します。
2. その結果をレシーバーである z に格納します。
3. そして z 自身を返します。

つまり、z = x % y と同じ計算を行います。

重要な点

• 戻り値の符号
  Goの組み込みの%演算子と同様に、Modメソッドによって返される剰余の符号は、被除数xの符号と同じになります。
  • 例:
    • 10 Mod 3 は 1
    • -10 Mod 3 は -1
    • 10 Mod -3 は 1
    • -10 Mod -3 は -1
• yはゼロであってはならない
  yがゼロの場合、ランタイムパニック（division by zero）が発生します。
• レシーバーへの格納
  結果はメソッドを呼び出したbig.Intオブジェクト（z）に直接格納されます。新しいbig.Intオブジェクトが生成されるわけではありません。
• 多倍長整数
  x, y, z はすべて*big.Int型（big.Intへのポインタ）である必要があります。

使用例

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// big.Int のインスタンスを生成
	a := new(big.Int)
	b := new(big.Int)
	result := new(big.Int)

	// 値を設定
	a.SetString("123456789012345678901234567890", 10) // 非常に大きな数
	b.SetInt64(7) // 7 で割る

	// Mod() メソッドを呼び出す
	// result = a % b
	result.Mod(a, b)

	fmt.Printf("a: %s\n", a.String())
	fmt.Printf("b: %s\n", b.String())
	fmt.Printf("a %% b (Mod): %s\n", result.String())

	fmt.Println("--- 負の数の例 ---")
	negA := new(big.Int)
	negA.SetString("-12345", 10)
	posB := new(big.Int)
	posB.SetInt64(7)
	
	result2 := new(big.Int)
	result2.Mod(negA, posB)
	fmt.Printf("%s %% %s (Mod): %s\n", negA.String(), posB.String(), result2.String()) // -12345 % 7 は -3 (Goの仕様)

	posA := new(big.Int)
	posA.SetString("12345", 10)
	negB := new(big.Int)
	negB.SetInt64(-7)

	result3 := new(big.Int)
	result3.Mod(posA, negB)
	fmt.Printf("%s %% %s (Mod): %s\n", posA.String(), negB.String(), result3.String()) // 12345 % -7 は 3 (Goの仕様)
}

出力例

a: 123456789012345678901234567890
b: 7
a % b (Mod): 3
--- 負の数の例 ---
-12345 % 7 (Mod): -3
12345 % -7 (Mod): 3

Go言語の組み込み整数型（int, int64など）は、固定のビット幅（32ビットまたは64ビット）で表現できる数値の範囲に制限があります。例えば、int64で扱える最大値は約9×1018です。

しかし、暗号技術（RSAなど）や科学計算など、非常に大きな整数（何百桁にも及ぶ数）を扱う必要がある場合があります。このような場合に、math/bigパッケージのbig.Int型が利用されます。big.Intは、メモリが許す限り任意の精度の整数を表現できます。

---

y（除数）がゼロの場合のパニック (Panic when y is zero)

エラー
big.Int.Mod(x, y)において、yがゼロである場合、runtime panic: division by zeroが発生します。通常の整数の割り算と同様に、ゼロ除算は許可されていません。

トラブルシューティング
Mod()を呼び出す前に、必ずyがゼロでないことを確認してください。y.Cmp(big.NewInt(0)) != 0 のようにしてゼロと比較することができます。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(10)
	b := big.NewInt(0) // 除数をゼロにする

	result := new(big.Int)

	// bがゼロでないかチェックする
	if b.Cmp(big.NewInt(0)) == 0 {
		fmt.Println("エラー: 除数がゼロです！")
		// エラーハンドリングのロジックを追加
		return
	}

	result.Mod(a, b) // ここでパニックが発生する
	fmt.Printf("結果: %s\n", result.String())
}

ポインタとしての引数 (*big.Int)

エラー
big.Intのメソッドは、多くの場合*big.Int（ポインタ）を引数として受け取ります。big.Intの値を直接渡そうとするとコンパイルエラーになります。

package main

import (
	"math/big"
)

func main() {
	a := big.NewInt(10)
	b := big.NewInt(3)

	// 間違い: result.Mod(a, *b) や result.Mod(*a, b) のように値で渡そうとする
	// result.Mod(*a, *b) // これはコンパイルエラー
}

トラブルシューティング
常にbig.Intのポインタ（&演算子で取得するか、new(big.Int)やbig.NewInt()で作成したもの）を渡すようにしてください。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(10)
	b := big.NewInt(3)

	result := new(big.Int) // 結果を格納する新しいbig.Intを生成

	result.Mod(a, b) // ポインタを渡す
	fmt.Printf("10 mod 3 = %s\n", result.String())
}

シャローコピーによる意図しない値の変更 (Unintended value changes due to shallow copy)

エラー
big.Intは内部的にスライス（[]uint）を使って大きな数を表現しています。*big.Intをコピーする際に、単純な代入（例: copyOfInt := *originalInt）を行うと、これはシャローコピーになります。つまり、新しいbig.Intは作成されますが、内部のスライスは元のものと共有されます。このため、コピーした値に対して演算を行うと、元の値も意図せず変更されてしまうことがあります。

これはMod()に限らず、big.Intの他の演算メソッドでも発生しうる一般的なエラーです。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	originalA := big.NewInt(100)
	divisor := big.NewInt(7)

	// 間違い: シャローコピー
	// `copyOfA := *originalA` は、originalAの指す underlying dataをcopyOfAも指すことになる
	// そのため、copyOfAへの操作がoriginalAにも影響する
	copyOfA := *originalA 

	// Mod演算を実行 (resultは新しいbig.Intにするが、copyOfA自体が変更される可能性がある)
	// この場合、Modはレシーバーを変更するが、copyOfAの基になるoriginalAの内部データが共有されているため問題になる
	result := new(big.Int)
	result.Mod(&copyOfA, divisor) // copyOfAのModを計算

	fmt.Printf("Original A: %s\n", originalA.String())
	fmt.Printf("Copied A after Mod: %s\n", copyOfA.String())
	fmt.Printf("Result: %s\n", result.String())
}

上記の例では、copyOfAは新しいbig.Intオブジェクトですが、その内部のabs []uintスライスはoriginalAと同じものを参照しています。そのため、result.Mod(&copyOfA, divisor)の呼び出しによってcopyOfAの内部データが変更されると、originalAも同じデータを見ているため、originalAの値も変わってしまいます。

トラブルシューティング
big.Intの値をコピーする場合は、必ずSet()メソッドを使用してディープコピーを行ってください。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	originalA := big.NewInt(100)
	divisor := big.NewInt(7)

	// 正しい方法: Set() メソッドでディープコピー
	copyOfA := new(big.Int).Set(originalA)

	result := new(big.Int)
	result.Mod(copyOfA, divisor) // copyOfAに対してModを計算

	fmt.Printf("Original A: %s\n", originalA.String())
	fmt.Printf("Copied A after Mod (should be same as original): %s\n", copyOfA.String())
	fmt.Printf("Result: %s\n", result.String())
}

この場合、copyOfA.Mod(copyOfA, divisor)のように、copyOfA自体をレシーバーにして演算を行っても、originalAには影響がありません。

組み込み型との混合 (Mixing with built-in types)

エラー
big.Intと通常のintやint64などの組み込み型を直接演算することはできません。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(100)
	b := 7 // int型

	// 間違い: big.Int と int を直接演算
	// result := new(big.Int).Mod(a, b) // コンパイルエラー
	
	// 間違い: big.Int のメソッドに int を渡す
	// result := new(big.Int)
	// result.Mod(a, b) // コンパイルエラー
}

トラブルシューティング
組み込み型の値をbig.Intに変換してから演算を行う必要があります。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(100)
	b := big.NewInt(7) // int を big.Int に変換

	result := new(big.Int)
	result.Mod(a, b)
	fmt.Printf("%s mod %s = %s\n", a.String(), b.String(), result.String())

	// または、一時的に変換することも可能
	var val int64 = 7
	result.Mod(a, big.NewInt(val))
	fmt.Printf("%s mod %d = %s\n", a.String(), val, result.String())
}

注意点
big.Int.Mod(x, y)の剰余の符号は、Goの組み込みの%演算子と同様に、被除数xの符号と同じになります。これは数学的なモジュロ演算（結果が常に非負になる）とは異なる場合があります。

例えば、数学では-10 mod 3 = 2とされることがありますが、Goでは-10 % 3 = -1となります。big.Int.Mod()もこれに従います。

トラブルシューティング
もし常に非負の剰余が必要な場合は、結果が負になった場合に除数yを足すなどの追加の処理が必要になります。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(-10)
	b := big.NewInt(3)
	result := new(big.Int)

	result.Mod(a, b)
	fmt.Printf("%s mod %s (Go's Mod) = %s\n", a.String(), b.String(), result.String()) // -1

	// 数学的なモジュロ（常に非負）が必要な場合
	if result.Sign() < 0 { // 結果が負の場合
		result.Add(result, b) // 除数を足す
	}
	fmt.Printf("%s mod %s (Mathematical Mod) = %s\n", a.String(), b.String(), result.String()) // 2
}

---

基本的な剰余計算

これは最も基本的な使用例で、大きな整数同士の剰余を計算します。

package main

import (
	"fmt"
	"math/big" // big.Int を使うためにインポート
)

func main() {
	// 非常に大きな数
	numStr := "987654321098765432109876543210"
	divisorInt64 := 7 // 割る数

	// big.Int のインスタンスを生成
	// new(big.Int) は、big.Int型のゼロ値へのポインタを返します
	a := new(big.Int)
	b := new(big.Int)
	result := new(big.Int)

	// 文字列から big.Int に値をセット
	// SetString(s string, base int) (*Int, bool)
	// 第1引数: 数値の文字列
	// 第2引数: 基数（10進数の場合は10）
	// 戻り値: *big.Int と、成功したかどうかのbool値
	a.SetString(numStr, 10)

	// int64 から big.Int に値をセット
	// SetInt64(x int64) *Int
	b.SetInt64(divisorInt64)

	fmt.Printf("a: %s\n", a.String())
	fmt.Printf("b: %s\n", b.String())

	// Mod() メソッドを呼び出し
	// result = a % b
	// func (z *Int) Mod(x, y *Int) *Int
	// 結果はレシーバー (z、この場合はresult) に格納され、z自身が返される
	result.Mod(a, b)

	fmt.Printf("a %% b (Mod): %s\n", result.String()) // 結果は3
}

解説

• String()メソッドはbig.Intの値を文字列として返します。
• result.Mod(a, b)でaをbで割った剰余を計算し、その結果をresultに格納します。
• SetString()メソッドで文字列から、SetInt64()メソッドでint64から、それぞれbig.Intに値をセットします。
• new(big.Int)を使ってbig.Intの新しいインスタンス（へのポインタ）を作成します。
• math/bigパッケージをインポートします。

負の数と剰余の符号

Go言語の%演算子と同様に、big.Int.Mod()の結果の符号は、被除数（割られる数）の符号と同じになります。数学的なモジュロ演算（結果が常に非負）とは異なることに注意が必要です。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// ケース1: 被除数が負、除数が正
	a1 := big.NewInt(-10)
	b1 := big.NewInt(3)
	result1 := new(big.Int)
	result1.Mod(a1, b1)
	fmt.Printf("%s mod %s (Go's Mod) = %s\n", a1.String(), b1.String(), result1.String()) // 出力: -1

	// ケース2: 被除数が正、除数が負
	a2 := big.NewInt(10)
	b2 := big.NewInt(-3)
	result2 := new(big.Int)
	result2.Mod(a2, b2)
	fmt.Printf("%s mod %s (Go's Mod) = %s\n", a2.String(), b2.String(), result2.String()) // 出力: 1

	// ケース3: 両方負
	a3 := big.NewInt(-10)
	b3 := big.NewInt(-3)
	result3 := new(big.Int)
	result3.Mod(a3, b3)
	fmt.Printf("%s mod %s (Go's Mod) = %s\n", a3.String(), b3.String(), result3.String()) // 出力: -1

	fmt.Println("\n--- 数学的なモジュロ（結果を常に非負にする） ---")

	// 数学的なモジュロが必要な場合の処理
	mathModResult := new(big.Int)
	mathModResult.Mod(a1, b1) // まずGoのModで計算
	if mathModResult.Sign() < 0 { // 結果が負の場合
		// 除数b1を足す
		// big.NewInt(0).Abs(b1) は b1 の絶対値を取得 (b1が負の場合も考慮)
		// しかし、GoのModの結果はxの符号と同じなので、b1の符号は気にせずb1を足せばよい
		mathModResult.Add(mathModResult, b1)
	}
	fmt.Printf("%s mod %s (Mathematical Mod) = %s\n", a1.String(), b1.String(), mathModResult.String()) // -10 mod 3 = 2
}

解説

• 数学的なモジュロ演算（結果が常に非負）が必要な場合は、Mod()の結果が負だった場合に、除数（y）をその結果に加算することで対応できます。result.Sign() < 0 で負かどうかを判定します。
• GoのMod()は被除数（x）の符号に結果の符号を合わせます。

ゼロ除算の回避

big.Int.Mod()にゼロを渡すとパニックが発生するため、事前にチェックが必要です。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(123)
	b := big.NewInt(0) // ゼロ

	result := new(big.Int)

	// 除数bがゼロでないことを確認
	// b.Cmp(big.NewInt(0)) == 0 は b が 0 と等しいことを意味する
	if b.Cmp(big.NewInt(0)) == 0 {
		fmt.Println("エラー: 除数がゼロです。Mod() を実行できません。")
		return // 処理を終了
	}

	result.Mod(a, b) // この行は実行されない
	fmt.Printf("結果: %s\n", result.String())
}

解説

• この比較結果が0であればbがゼロなので、Mod()を呼び出す前にエラーメッセージを表示して処理を中断します。
• b.Cmp(big.NewInt(0))は、bとbig.NewInt(0)を比較します。
  • b < 0 なら -1
  • b == 0 なら 0
  • b > 0 なら 1

big.IntにはMod()の他に、冪剰余を計算するExp()メソッドがあります。これは(base^exponent) % modulusを効率的に計算するために使用されます。Mod()と混同しないように注意が必要です。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// 例: (2^100) % 7 を計算する
	base := big.NewInt(2)
	exponent := big.NewInt(100)
	modulus := big.NewInt(7)

	// big.Int.Exp() を使用
	// func (z *Int) Exp(x, y, m *Int) *Int
	// z = (x^y) mod m
	// mがnilの場合、(x^y)を計算
	expResult := new(big.Int)
	expResult.Exp(base, exponent, modulus)
	fmt.Printf("(%s^%s) %% %s (Exp) = %s\n", base.String(), exponent.String(), modulus.String(), expResult.String())

	// 参考: 単純に Mod() を使う場合
	// まず (2^100) を計算
	powResult := new(big.Int)
	powResult.Exp(base, exponent, nil) // modulusをnilにすると単なる冪乗
	fmt.Printf("2^100 = %s\n", powResult.String())

	// その後で Mod()
	modResult := new(big.Int)
	modResult.Mod(powResult, modulus)
	fmt.Printf("2^100 %% 7 (Mod after Exp) = %s\n", modResult.String())
	// powResultが非常に大きな数になるため、Exp(x, y, m) の方が効率的

}

• そのため、冪乗と剰余を同時に行いたい場合は、Exp()メソッドの第三引数（modulus）を使用するのが一般的です。
• Mod()は単なる剰余演算であり、$ \text{base}^{\text{exponent}} $ の結果が巨大な値になる場合、先に$ \text{base}^{\text{exponent}} $ を計算してからMod()を適用するとメモリや計算時間が非効率になる可能性があります。
• Exp(base, exponent, modulus)は、$ \text{base}^{\text{exponent}} \pmod{\text{modulus}} $ を計算します。これはRSA暗号などで非常に重要です。

---

主な代替・関連手法としては、以下の点が挙げられます。

big.Int.ModInverse() (Modular Multiplicative Inverse)

これは単純な剰余計算とは異なりますが、**モジュラ逆数（Modular Multiplicative Inverse）**を計算する際に使用します。 (a⋅x)(modm)=1 となる x を見つける操作です。これは公開鍵暗号（RSAなど）で非常に重要です。

big.Int.Mod()の目的とは異なりますが、モジュロ演算に関連する重要な機能です。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	a := big.NewInt(7)
	m := big.NewInt(26) // mod 26

	// 7 の mod 26 でのモジュラ逆数を計算
	// func (z *Int) ModInverse(x, m *Int) *Int
	// z = x^-1 mod m
	// mは正でなければならない。gcd(x, m) == 1 (xとmが互いに素)でないと結果はnil
	inv := new(big.Int)
	inv.ModInverse(a, m)

	if inv != nil {
		fmt.Printf("%s の mod %s における逆数: %s\n", a.String(), m.String(), inv.String())
		// 検算: (7 * 15) % 26 = 105 % 26 = 1
		check := new(big.Int).Mul(a, inv)
		check.Mod(check, m)
		fmt.Printf("検算: (%s * %s) %% %s = %s\n", a.String(), inv.String(), m.String(), check.String())
	} else {
		fmt.Printf("%s の mod %s における逆数は存在しません。\n", a.String(), m.String())
	}

	// 互いに素でない場合 (例: 2 と 26)
	a2 := big.NewInt(2)
	inv2 := new(big.Int)
	inv2.ModInverse(a2, m)
	if inv2 != nil {
		fmt.Printf("%s の mod %s における逆数: %s\n", a2.String(), m.String(), inv2.String())
	} else {
		fmt.Printf("%s の mod %s における逆数は存在しません。(互いに素ではない)\n", a2.String(), m.String())
	}
}

解説

• これはMod()のように一般的な剰余を求めるものではなく、特定の数学的目的に使用されます。
• x と m が互いに素でない場合、逆数は存在せず、nilが返されます。
• ModInverse(x, m)は、$ x \pmod m $ の逆数を計算します。

big.Int.Exp() (Modular Exponentiation - 冪剰余)

これは前に少し触れましたが、特定の大きな数（$ \text{base}^{\text{exponent}} $）の剰余を計算する際に、big.Int.Mod()を直接使うよりもはるかに効率的な方法です。

big.Int.Exp(x, y, m) は (xy)(modm) を計算します。

もしあなたが大きな数の冪乗の剰余を求めたいのであれば、big.Int.Mod()の代替というよりは、より適切なアプローチとしてbig.Int.Exp()を使うべきです。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	base := big.NewInt(3)
	exponent := big.NewInt(1000) // 非常に大きな指数
	modulus := big.NewInt(101)  // 割る数

	// 方法1: Exp() を使用 (推奨される効率的な方法)
	// z = (x^y) mod m
	resultExp := new(big.Int)
	resultExp.Exp(base, exponent, modulus)
	fmt.Printf("(%s^%s) %% %s using Exp(): %s\n",
		base.String(), exponent.String(), modulus.String(), resultExp.String())

	// 方法2: 最初に冪乗を計算し、その後で Mod() を使用 (非効率)
	// exponent が大きい場合、powResult は非常に大きくなる
	powResult := new(big.Int)
	powResult.Exp(base, exponent, nil) // modulus を nil にすると単純な冪乗
	// fmt.Printf("powResult (too big to print reliably): %s\n", powResult.String()) // 非常に長くなる可能性あり

	resultMod := new(big.Int)
	resultMod.Mod(powResult, modulus)
	fmt.Printf("(%s^%s) %% %s using Mod() after Exp(nil): %s\n",
		base.String(), exponent.String(), modulus.String(), resultMod.String())
}

解説

• したがって、冪剰余が目的であればExp()の第三引数を利用するのが常に正しい選択です。
• もしmodulusがnilの場合、単純に冪乗（base^exponent）を計算します。その後でMod()を使うことも可能ですが、base^exponentが非常に大きくなるとメモリを大量に消費したり、計算が非効率になったりします。
• Exp(base, exponent, modulus)は、モジュラスmが指定されている場合、途中の計算で数が爆発的に大きくなるのを防ぎながら剰余を計算します。

これはbig.Intの代替ではありませんが、もし扱う数値がint64の範囲に収まるのであれば、math/bigパッケージを使う必要はなく、Goの組み込みの%演算子で十分です。

package main

import "fmt"

func main() {
	var a int64 = 1234567890
	var b int64 = 7

	result := a % b
	fmt.Printf("%d %% %d = %d\n", a, b, result) // 剰余計算
}

• ほとんどの一般的な整数演算では、組み込み型と%演算子で十分であり、big.Intを使うとオーバーヘッドが発生します。
• 扱いたい数が多倍長整数である場合にのみmath/bigを使用します。

• 範囲が収まる場合: 組み込みのint64型と%演算子を使用します。
• 関連するが異なる目的:
  • big.Int.ModInverse(): モジュラ逆数を計算する。
  • big.Int.Exp(): 冪剰余を効率的に計算する。これは、$ (x^y) \pmod m $ の形式の計算が必要な場合に、Mod()の「代替」としてではなく「より適切な選択」として使われます。
• big.Int.Mod()の直接的な代替: 基本的には存在しません。これは多倍長整数の一般的な剰余計算のための標準的なメソッドです。