big.Int.ModSqrt()の活用術：Go言語でのモジュラ平方根プログラミング例

2025-06-01

`big.Int.ModSqrt()`とは何か？

Go言語のmath/bigパッケージのInt型は、任意の精度を持つ整数（非常に大きな整数）を扱うためのものです。ModSqrt(x, p)は、次のような合同式を満たすyを計算します。

y2≡x(modp)

ここで：

y が求められる平方根です。
p は法（モジュラス）となる数で、素数である必要があります。
x は平方根を求めたい数です。

つまり、ModSqrt(x, p)は「pを法としてxの平方根となるyを求める」関数です。

どのような値を返すのか？

そのようなyが存在しない場合（つまり、xがpを法とする二次剰余でない場合）、nilを返します。
もし、y2≡x(modp) となるyが存在する場合、ModSqrtはそのようなyの1つを返します。

使用例

この関数は主に、暗号学の分野で利用されます。例えば、楕円曲線暗号において、ある点（公開鍵など）の圧縮解除を行う際に、特定の座標値のモジュラ平方根を計算する必要がある場合があります。

Goのコードでは、以下のように使用されます。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	// 例1: 4 の 7 を法とする平方根
	// 2^2 = 4 (mod 7) なので、結果は 2
	x := big.NewInt(4)
	p := big.NewInt(7)
	y := new(big.Int).ModSqrt(x, p)

	if y != nil {
		fmt.Printf("%s の %s を法とする平方根は %s です\n", x, p, y) // 出力: 4 の 7 を法とする平方根は 2 です
	} else {
		fmt.Printf("%s の %s を法とする平方根は存在しません\n", x, p)
	}

	// 例2: 3 の 7 を法とする平方根
	// 3 (mod 7) の平方根は存在しない
	x2 := big.NewInt(3)
	p2 := big.NewInt(7)
	y2 := new(big.Int).ModSqrt(x2, p2)

	if y2 != nil {
		fmt.Printf("%s の %s を法とする平方根は %s です\n", x2, p2, y2)
	} else {
		fmt.Printf("%s の %s を法とする平方根は存在しません\n", x2, p2) // 出力: 3 の 7 を法とする平方根は存在しません
	}

	// 例3: 大きな数の例 (実際の暗号で使われるようなケース)
	// 任意の大きな数と素数を定義
	// 実際にはもっと複雑な計算が行われる
	largeX, _ := new(big.Int).SetString("123456789012345678901234567890", 10)
	largeP, _ := new(big.Int).SetString("987654321098765432109876543210987654321", 10) // 実際には素数であることの確認が必要

	// largePが素数でない場合は、ModSqrtの結果は保証されません。
	// largePは例として適当な数値を使っていますが、実際にはProperlyPrime()などで素数であることを確認するのが一般的です。

	largeY := new(big.Int).ModSqrt(largeX, largeP)
	if largeY != nil {
		fmt.Printf("大きな数 %s の %s を法とする平方根は %s です\n", largeX, largeP, largeY)
	} else {
		fmt.Printf("大きな数 %s の %s を法とする平方根は存在しません\n", largeX, largeP)
	}
}

big.Int型は可変（mutable）であるため、操作の結果を格納するために新しいbig.Intを割り当てるか、既存のbig.Intポインタを渡す必要があります。
モジュラ平方根は、存在する場合でも通常2つ存在します（yとp−y）。ModSqrtはどちらか一方を返します。
ModSqrtは、法となる数pが素数であることを前提としています。pが素数でない場合、結果は未定義または期待通りではない可能性があります。

法（モジュラス）pが素数ではない

エラーの原因
ModSqrt()関数のドキュメントには明記されていますが、法となるpは素数である必要があります。素数でない数をpとして渡すと、ModSqrt()は正しく動作しないか、場合によっては無限ループに陥る可能性があります。特にp=1のような場合が典型例です。

トラブルシューティング
ModSqrt()を呼び出す前に、pが素数であることを確認することが最も重要です。math/bigパッケージには、確率的素数判定を行うProbablyPrime()関数があります。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(4)
	p := big.NewInt(9) // 素数ではない (3*3)

	// pが素数でない場合
	if !p.ProbablyPrime(20) { // 20は信頼度を表す値。大きいほど正確だが計算時間がかかる。
		fmt.Printf("エラー: 法 %s は素数ではありません。\n", p)
		// エラーハンドリング: nilを返したり、適切なエラーメッセージを出力したりする
		return
	}

	y := new(big.Int).ModSqrt(x, p)

	if y != nil {
		fmt.Printf("%s の %s を法とする平方根は %s です\n", x, p, y)
	} else {
		fmt.Printf("%s の %s を法とする平方根は存在しません\n", x, p)
	}
}

xがpを法とする二次剰余ではない

エラーの原因
y2≡x(modp) となるyが存在しない場合、ModSqrt()はnilを返します。これはエラーではなく、計算の結果として平方根が存在しないことを示しています。しかし、コードでnilチェックを怠ると、後続の処理でパニックが発生する可能性があります。

トラブルシューティング
ModSqrt()の戻り値がnilでないことを常に確認してください。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(3) // 7を法とする3の平方根は存在しない
	p := big.NewInt(7) // 素数

	y := new(big.Int).ModSqrt(x, p)

	if y != nil {
		fmt.Printf("%s の %s を法とする平方根は %s です\n", x, p, y)
	} else {
		// ここで適切なエラーハンドリングを行う
		fmt.Printf("%s の %s を法とする平方根は存在しません。\n", x, p)
	}
}

big.Intのポインタの扱いに関する誤解

エラーの原因
math/bigパッケージの関数は、多くの場合、結果をレシーバー（メソッドを呼び出すインスタンス）に書き込み、そのレシーバーのポインタを返します。これにより、メモリ割り当てを最小限に抑え、計算を効率化できます。しかし、これに慣れていないと、意図せず値が上書きされたり、予期せぬ結果になったりすることがあります。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	x := big.NewInt(4)
	p := big.NewInt(7)
	
	// 誤った例: xが上書きされてしまう
	// x = x.ModSqrt(x, p) // これだと x が平方根に上書きされる可能性があり、混乱を招く
	
	// 正しい例: 新しい big.Int を作成して結果を格納するか、
	// 別の既存の big.Int に格納する
	y := new(big.Int)
	y.ModSqrt(x, p) // ModSqrt は y に結果を書き込み、y を返す

	if y != nil {
		fmt.Printf("x: %s, p: %s, 平方根: %s\n", x, p, y) // xは元の値のまま
	} else {
		fmt.Printf("平方根は存在しません。\n")
	}
}

トラブルシューティング
新しいbig.Intをnew(big.Int)で作成し、そのインスタンスでModSqrt()を呼び出すか、結果を格納するための別のbig.Int変数を明示的に用意してください。

符号付き整数と符号なし整数の混同（間接的影響）

ModSqrt()自体は符号付き整数を扱いますが、他のbig.Int操作と組み合わせる際に、符号の扱いで混乱が生じることがあります。例えば、big.Int.Bytes()やbig.Int.SetBytes()などは符号なしバイト表現を扱います。

トラブルシューティング
big.Intの各メソッドが符号をどのように扱うかをドキュメントで確認し、意図しない符号の反転やビット表現の誤解が生じないように注意してください。特に、バイト列との変換を行う場合は、big.Int.Sign()などで符号を確認し、必要に応じて処理を分岐させるのが安全です。

非常に大きな数でのパフォーマンス問題

エラーの原因
ModSqrt()は、特に法pが非常に大きな素数である場合、計算に時間がかかることがあります。暗号学的な用途では数千ビットの素数が使われることもあり、処理が遅いと感じるかもしれません。

アルゴリズムの選択（低レベルでの検討）
ModSqrt()はTonelli-Shanksアルゴリズムなどの標準的なアルゴリズムを内部で使用しています。通常、この関数自体を最適化する必要はありませんが、もし極端なパフォーマンス要件がある場合は、より低レベルでの最適化（例：並列処理、特殊な法に対する高速化）を検討する必要があるかもしれません。ただし、これは非常に専門的な分野であり、通常はmath/bigパッケージに任せるのが安全です。
ベンチマークとプロファイリング
処理が遅いと感じる場合は、Goの標準ツールであるgo test -bench .やgo tool pprofを使って、どこにボトルネックがあるのかを特定します。
pのサイズを適切に選択する
必要なセキュリティレベルに応じてpのビット長を決定します。不必要に大きな素数を使用しないようにしましょう。

big.Int.ModSqrt()は、合同式 y2≡x(modp) を満たすy（モジュラ平方根）を計算する関数です。ただし、法pは素数である必要があります。

基本的な使用例：平方根が存在する場合としない場合

この例では、ModSqrt()の基本的な使い方と、平方根が存在する場合と存在しない場合の戻り値の確認方法を示します。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	fmt.Println("--- 基本的な使用例 ---")

	// 例1: 4 の 7 を法とする平方根
	// 2^2 = 4 (mod 7) なので、結果は 2 (または 5, 5^2=25=4 mod 7)
	x1 := big.NewInt(4)
	p1 := big.NewInt(7) // 7は素数

	fmt.Printf("計算: %s の %s を法とする平方根\n", x1, p1)
	y1 := new(big.Int).ModSqrt(x1, p1) // 結果を格納する新しい big.Int を作成

	if y1 != nil {
		fmt.Printf("結果: %s です\n", y1) // 2 が出力されることが多い
		// 平方根が本当に正しいか検証
		check1 := new(big.Int).Mul(y1, y1)
		check1.Mod(check1, p1)
		fmt.Printf("検証: %s^2 mod %s = %s (期待値: %s)\n", y1, p1, check1, x1)
	} else {
		fmt.Printf("結果: 平方根は存在しません\n")
	}
	fmt.Println()

	// 例2: 3 の 7 を法とする平方根
	// 3 (mod 7) は二次剰余ではないため、平方根は存在しない
	x2 := big.NewInt(3)
	p2 := big.NewInt(7) // 7は素数

	fmt.Printf("計算: %s の %s を法とする平方根\n", x2, p2)
	y2 := new(big.Int).ModSqrt(x2, p2)

	if y2 != nil {
		fmt.Printf("結果: %s です\n", y2)
	} else {
		fmt.Printf("結果: 平方根は存在しません\n") // これが出力される
	}
	fmt.Println()
}

解説

Mod(val, p): valをpで割った余り（モジュロ演算）を計算します。これにより、計算した平方根が本当にx(modp)に一致するかを検証できます。
Mul(y, y): yの2乗を計算します。
if y != nil: 平方根が存在しない場合はnilが返されるため、必ずこのチェックが必要です。
new(big.Int).ModSqrt(x, p): ModSqrtメソッドは、レシーバー（この場合はnew(big.Int)で作成した新しいbig.Intインスタンス）に計算結果を格納し、そのレシーバーへのポインタを返します。
big.NewInt(val): 指定した値を持つbig.Intを新しく作成します。

法が素数であることの確認を含める例

ModSqrt()の最も重要な前提条件は、法が素数であることです。ProbablyPrime()を使って、この条件をチェックする例です。

package main

import (
	"fmt"
	"math/big"
	"errors" // エラーハンドリングのためにerrorsパッケージをインポート
)

// safeModSqrt は ModSqrt を安全に呼び出すためのラッパー関数
func safeModSqrt(x, p *big.Int) (*big.Int, error) {
	// p が素数であることを確率的に判定
	// 20 は信頼度を表す値 (Miller-Rabinテストの繰り返し回数)。大きいほど信頼度が高い。
	if !p.ProbablyPrime(20) {
		return nil, errors.New("法 (modulus) は素数でなければなりません")
	}

	result := new(big.Int).ModSqrt(x, p)
	if result == nil {
		return nil, errors.New("指定された数に対する平方根は存在しません")
	}
	return result, nil
}

func main() {
	fmt.Println("--- 法が素数であることの確認を含む例 ---")

	// 例1: 正常なケース (法が素数)
	x1 := big.NewInt(9)
	p1 := big.NewInt(11) // 11は素数

	fmt.Printf("計算: %s の %s を法とする平方根\n", x1, p1)
	y1, err1 := safeModSqrt(x1, p1)

	if err1 != nil {
		fmt.Printf("エラー: %s\n", err1)
	} else {
		fmt.Printf("結果: %s です\n", y1) // 3 または 8
	}
	fmt.Println()

	// 例2: 法が素数ではないケース
	x2 := big.NewInt(4)
	p2 := big.NewInt(10) // 10は素数ではない

	fmt.Printf("計算: %s の %s を法とする平方根\n", x2, p2)
	y2, err2 := safeModSqrt(x2, p2)

	if err2 != nil {
		fmt.Printf("エラー: %s\n", err2) // "法 (modulus) は素数でなければなりません" が出力される
	} else {
		fmt.Printf("結果: %s です\n", y2)
	}
	fmt.Println()

	// 例3: 平方根が存在しないケース
	x3 := big.NewInt(2)
	p3 := big.NewInt(7) // 7は素数

	fmt.Printf("計算: %s の %s を法とする平方根\n", x3, p3)
	y3, err3 := safeModSqrt(x3, p3)

	if err3 != nil {
		fmt.Printf("エラー: %s\n", err3) // "指定された数に対する平方根は存在しません" が出力される
	} else {
		fmt.Printf("結果: %s です\n", y3)
	}
	fmt.Println()
}

解説

ProbablyPrime(confidence): confidenceの値は、ミラー・ラビン素数判定法の繰り返し回数を指定します。数値が大きいほど素数である信頼度が高まりますが、計算時間も長くなります。
errors.New(): カスタムエラーメッセージを作成するためにerrorsパッケージを使用しています。
safeModSqrt関数: ModSqrt()を呼び出す前にp.ProbablyPrime(20)を使って、pが素数であるかを確率的にチェックしています。これにより、無効な入力に対するエラーハンドリングを強化しています。

大きな数での使用例（暗号学的な文脈を意識）

暗号学では、非常に大きな素数と数を扱います。この例では、SetString()を使って大きな数を文字列からbig.Intに変換し、ModSqrt()を適用する様子を示します。

package main

import (
	"fmt"
	"math/big"
)

func main() {
	fmt.Println("--- 大きな数での使用例 ---")

	// 非常に大きな素数 (ここでは例として、実際の暗号で使われるようなビット長の素数の一部を表現)
	// 実際には、安全な素数を生成する関数などを使用します
	// これは単なる例であり、実際に暗号に使われる素数ではありません
	largePrimeStr := "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF

#### 4. `x`と`p`の関係による結果の確認

`ModSqrt()`は、$x$が$p$の倍数である場合や$p$が小さい場合など、いくつかの特殊なケースでどのように動作するかを確認する例です。

```go
package main

import (
	"fmt"
	"math/big"
)

func main() {
	fmt.Println("--- x と p の関係による結果の確認 ---")

	// 例1: x = 0 の場合 (0^2 = 0 mod p)
	x1 := big.NewInt(0)
	p1 := big.NewInt(13) // 13は素数

	fmt.Printf("計算: %s の %s を法とする平方根\n", x1, p1)
	y1 := new(big.Int).ModSqrt(x1, p1)
	if y1 != nil {
		fmt.Printf("結果: %s です\n", y1) // 0 が出力される
	} else {
		fmt.Printf("結果: 平方根は存在しません\n")
	}
	fmt.Println()

	// 例2: x が p よりも大きい場合 (ModSqrtは内部で x mod p を計算する)
	// 10 の 7 を法とする平方根 = 3 の 7 を法とする平方根 (存在しない)
	x2 := big.NewInt(10)
	p2 := big.NewInt(7) // 7は素数

	fmt.Printf("計算: %s の %s を法とする平方根\n", x2, p2)
	y2 := new(big.Int).ModSqrt(x2, p2)
	if y2 != nil {
		fmt.Printf("結果: %s です\n", y2)
	} else {
		fmt.Printf("結果: 平方根は存在しません\n") // これが出力される
	}
	fmt.Println()

	// 例3: x が負の数の場合 (ModSqrtは内部で x mod p を計算する)
	// -3 の 7 を法とする平方根 = 4 の 7 を法とする平方根
	x3 := big.NewInt(-3)
	p3 := big.NewInt(7) // 7は素数

	fmt.Printf("計算: %s の %s を法とする平方根\n", x3, p3)
	y3 := new(big.Int).ModSqrt(x3, p3)
	if y3 != nil {
		fmt.Printf("結果: %s です\n", y3) // 2 または 5
	} else {
		fmt.Printf("結果: 平方根は存在しません\n")
	}
	fmt.Println()
}

x = 0の場合、平方根は常に$0$になります。
ModSqrtは、内部的に$x \pmod p$を計算するため、$x$が$p$より大きくても、または負の数であっても適切に処理されます。重要なのは、$x$が$p$を法とする二次剰余であるかどうかです。

Go言語のbig.Int.ModSqrt()関数は、モジュラ平方根（法平方根）を計算するための標準的で効率的な方法を提供しますが、場合によっては代替手段を検討することもあります。主な代替方法は、手動でアルゴリズムを実装することですが、これは通常、特定の最適化や特殊なケースに対応する必要がある場合に限られます。

基本的に、ほとんどのGoプログラマーは、big.Int.ModSqrt()の内部実装（Tonelli-Shanksアルゴリズムの効率的なGoでの実装）を利用するのが最適です。しかし、理論的な理解を深めるためや、非常に特殊な要件がある場合に、独自のモジュラ平方根アルゴリズムを実装する選択肢もあります。

Tonelli-Shanks（トネリ・シャンクス）アルゴリズムを自分で実装する

big.Int.ModSqrt()は、内部的にTonelli-Shanksアルゴリズムを使用しています。これは、奇素数を法とするモジュラ平方根を計算するための標準的なアルゴリズムです。もし、big.Int.ModSqrt()の動作を深く理解したい場合や、非常に特定のユースケース（例えば、特定の最適化を施したい、あるいは教育目的など）がある場合は、このアルゴリズムをGoで手動で実装することができます。

利点

特定の法や入力に対して、カスタムの最適化を適用できる可能性がある（ただし、これは非常に高度な知識を必要とします）。
アルゴリズムの動作を完全に制御できる。

欠点

パフォーマンス
math/bigパッケージの実装は、Goの標準ライブラリの専門家によって高度に最適化されています。自分で実装した場合、通常はこれより遅くなる可能性が高いです。
バグの可能性
自分で実装すると、バグが混入するリスクが格段に高まります。数学的な正しさとセキュリティが非常に重要な暗号関連の計算では、これは致命的です。
実装の複雑さ
Tonelli-Shanksアルゴリズムは非自明であり、正確かつ効率的に実装するのは非常に難しいです。多くのコーナーケース（例えば、Legendre記号の計算、特殊な法p≡3(mod4)の場合など）を考慮する必要があります。

実装の簡単な概念
Tonelli-Shanksアルゴリズムは、フェルマーの小定理とオイラーの規準を用いて、繰り返し計算によって平方根を求めます。プロセスは、法pがp≡3(mod4)の形式である場合と、そうでない場合で少し異なります。

コード例（非常に簡略化された概念で、実用的なものではありません）

package main

import (
	"fmt"
	"math/big"
)

// これは教育目的の概念的なスケッチであり、
// 実用的な Tonelli-Shanks 実装ではありません。
// 実際の ModSqrt() はもっと複雑で堅牢です。
func myModSqrt(x, p *big.Int) *big.Int {
	if !p.ProbablyPrime(20) {
		fmt.Println("Error: Modulus is not prime.")
		return nil
	}

	// 0の平方根は0
	if x.Cmp(big.NewInt(0)) == 0 {
		return big.NewInt(0)
	}

	// Legendre Symbol (x/p) を計算して、平方根が存在するかチェック
	// (x/p) == -1 の場合、平方根は存在しない
	// big.Jacobi は Legendre Symbol を計算する
	jacobi := big.Jacobi(x, p)
	if jacobi == -1 {
		fmt.Printf("Debug: %s は %s を法とする二次非剰余です。\n", x, p)
		return nil
	}

	// ここから Tonelli-Shanks アルゴリズムの実際のロジックが始まる
	// (簡略化のため省略)
	// p % 4 == 3 の特殊ケースは比較的簡単ですが、
	// それ以外のケースは複雑になります。
	
	// 例えば、p % 4 == 3 の非常に単純なケース:
	// y = x^((p+1)/4) mod p
	if new(big.Int).Mod(p, big.NewInt(4)).Cmp(big.NewInt(3)) == 0 {
		exp := new(big.Int).Add(p, big.NewInt(1))
		exp.Div(exp, big.NewInt(4))
		res := new(big.Int).Exp(x, exp, p)
		// 検証: res*res mod p == x
		check := new(big.Int).Mul(res, res)
		check.Mod(check, p)
		if check.Cmp(x) == 0 {
			return res
		}
		// もう一つの解があればそれも考慮する必要がある (p-res)
		// この簡略化された例ではそこまで考慮していません。
	}

	// 実際には Tonelli-Shanks の完全なアルゴリズムが必要
	fmt.Println("Debug: Fully implementing Tonelli-Shanks is complex and omitted here.")
	return nil // 実装されていない
}

func main() {
	x := big.NewInt(4)
	p := big.NewInt(7) // 7は素数、7 % 4 == 3

	fmt.Printf("%s の %s を法とする平方根を計算 (自作関数):\n", x, p)
	result := myModSqrt(x, p)
	if result != nil {
		fmt.Printf("結果: %s\n", result)
	} else {
		fmt.Println("平方根は存在しないか、計算できませんでした。")
	}

	x2 := big.NewInt(3)
	p2 := big.NewInt(7)
	fmt.Printf("\n%s の %s を法とする平方根を計算 (自作関数):\n", x2, p2)
	result2 := myModSqrt(x2, p2)
	if result2 != nil {
		fmt.Printf("結果: %s\n", result2)
	} else {
		fmt.Println("平方根は存在しないか、計算できませんでした。")
	}
}

ポラードのRhoアルゴリズムや他の因数分解アルゴリズム（間接的な関連）

これは直接的な代替手段ではありませんが、もし法pが素数ではない場合（つまり、ModSqrtが使えない場合）、モジュラ平方根を求めることは、一般に因数分解問題と同程度に難しいとされています。この場合、ポラードのRhoアルゴリズムや二次ふるい法などの因数分解アルゴリズムを使ってpを素因数分解し、その後に中国剰余定理（CRT）を用いて各素因数に対する平方根を結合する方法が考えられます。

利点

合成数を法とするモジュラ平方根を扱える唯一の方法。

欠点

実装の複雑さ
因数分解アルゴリズムも中国剰余定理も、実装は複雑です。
非常に計算コストが高い
大きな合成数の因数分解は非常に計算コストが高く、現在の計算能力では事実上不可能です（RSA暗号の安全性はこの困難性に基づいています）。

いつ検討するか

研究目的や、特定の問題（例：教科書の問題を解く）で、因数分解を前提としたモジュラ平方根の計算が必要な場合。
法が確実に素数ではない場合、そしてその合成数を因数分解できるほど小さいことが分かっている場合。

Go言語でモジュラ平方根を計算する場合、big.Int.ModSqrt()が最も推奨される方法です。 これは、Goの標準ライブラリチームによって徹底的にテストされ、最適化された実装であり、正確性とパフォーマンスの両面で優れています。

代替方法の検討は、以下のような非常に特殊な状況に限られます。

法が素数でない場合
この場合はModSqrt()は使えず、因数分解と中国剰余定理を組み合わせる必要がありますが、これは一般的に非常に困難です。
極端なパフォーマンス要件と特定の法構造
標準ライブラリの実装では対応できないような、非常にニッチな最適化が必要な場合（これは極めて稀です）。
教育目的
Tonelli-Shanksアルゴリズムの内部動作を理解するため。