go-modular-square-root-tonelli-shanks
Done. A verified Tonelli–Shanks solution is implemented in ~/tonelli-shanks/main.go with the full write-up in ~/tonelli-shanks/SOLUTION.md.
Root causes addressed:
- Naive O(p) scanning is unusable at 1e5 queries → Tonelli–Shanks (O(log² p)), with math/big.Exp for fast modular exponentiation.
- a = 0 must short-circuit before Euler's criterion (else it'd be misclassified as non-residue).
- Non-residues detected exactly via Euler's criterion a^((p-1)/2) ≡ 1 (mod p).
- Print min(x, p-x) — the two roots are distinct for a > 0 — not an arbitrary root.
- math/big avoids 64-bit overflow for large primes.
Verification results (all PASS):
- go vet + go build clean.
- Exhaustive brute-force cross-check for every odd prime p ≤ 3000, all a < p (roots square back to a, pair {x, p-x}, distinct for a>0, -1 iff non-residue, a=0 → 0).
- 3000 random 63-bit primes (validated by ProbablyPrime): all roots verified.
- CLI end-to-end: p=7 sample → 0 1 3 -1 2 -1 -1; large prime 1e9+7 cases correct; both n-prefixed and bare-pair input formats accepted.
- Performance: 1e5 queries on random 63-bit primes solve in 0.9 s, with all 1e5 outputs independently re-validated in Python (zero invalid lines, distinct roots for a>0, -1 only for true non-residues).
Files (in ~/tonelli-shanks/):
- main.go — the solution (single file, no dependencies beyond stdlib)
- brute_test.go — exhaustive + randomized correctness tests (go test .)
- SOLUTION.md — self-contained markdown: root-cause analysis, full code, verification section
# Evidence - Problem class: go-modular-square-root-tonelli-shanks - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-16T10:23:17.933Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "For each of up to 1e5 queries (a, p) with p an odd prime and 0 <= a < p, compute both modular square roots x with x^2 == a (mod p) and print the smaller root, or -1 if a is a quadratic non-residue. Implement Tonelli-Shanks with fast modular exponentiation; a=0 must yield 0 and the two roots must be distinct for a>0.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-modular-square-root-tonelli-shanks", "provider": "openrouter", "solved_at": "2026-08-16T10:23:17.933Z", "version": "1.26"}Done. A verified Tonelli–Shanks solution is implemented in ~/tonelli-shanks/main.go with the full write-up in ~/tonelli-shanks/SOLUTION.md.
Root causes addressed:
- Naive O(p) scanning is unusable at 1e5 queries → Tonelli–Shanks (O(log² p)), with math/big.Exp for fast modular exponentiation.
- a = 0 must short-circuit before Euler's criterion (else it'd be misclassified as non-residue).
- Non-residues detected exactly via Euler's criterion a^((p-1)/2) ≡ 1 (mod p).
- Print min(x, p-x) — the two roots are distinct for a > 0 — not an arbitrary root.
- math/big avoids 64-bit overflow for large primes.
Verification results (all PASS):
- go vet + go build clean.
- Exhaustive brute-force cross-check for every odd prime p ≤ 3000, all a < p (roots square back to a, pair {x, p-x}, distinct for a>0, -1 iff non-residue, a=0 → 0).
- 3000 random 63-bit primes (validated by ProbablyPrime): all roots verified.
- CLI end-to-end: p=7 sample → 0 1 3 -1 2 -1 -1; large prime 1e9+7 cases correct; both n-prefixed and bare-pair input formats accepted.
- Performance: 1e5 queries on random 63-bit primes solve in 0.9 s, with all 1e5 outputs independently re-validated in Python (zero invalid lines, distinct roots for a>0, -1 only for true non-residues).
Files (in ~/tonelli-shanks/):
- main.go — the solution (single file, no dependencies beyond stdlib)
- brute_test.go — exhaustive + randomized correctness tests (go test .)
- SOLUTION.md — self-contained markdown: root-cause analysis, full code, verification section
# Evidence - Problem class: go-modular-square-root-tonelli-shanks - Model: openrouter/deepseek/deepseek-v4-flash-0731 - Solved: 2026-08-16T10:23:17.933Z - Verification: solution produced by pi in sandbox; see signatures.json
{"description": "For each of up to 1e5 queries (a, p) with p an odd prime and 0 <= a < p, compute both modular square roots x with x^2 == a (mod p) and print the smaller root, or -1 if a is a quadratic non-residue. Implement Tonelli-Shanks with fast modular exponentiation; a=0 must yield 0 and the two roots must be distinct for a>0.", "environment": "go1.26", "language": "go", "model": "openrouter/deepseek/deepseek-v4-flash-0731", "problem_class": "go-modular-square-root-tonelli-shanks", "provider": "openrouter", "solved_at": "2026-08-16T10:23:17.933Z", "version": "1.26"}