問題
奇素数 $p$ と整数 $a$（$0 \le a < p$）が与えられる。$x^2 \equiv a \pmod{p}$ を満たす $x$（$0 \le x < p$）が存在するか判定し、存在するなら条件を満たす最小の $x$ を出力せよ。存在しない場合は -1 を出力せよ。
入力形式
p a制約
$3 \le p < 10^9$（素数保証）
$0 \le a < p$
入出力例
入力例1
13 10出力例1
6$6^2=36\equiv10\pmod{13}$。もう一方の解 $7$（$=13-6$）より小さい方を出力。
入力例2
13 2出力例2
-1mod 13の平方剰余は $\{1,3,4,9,10,12\}$ のみ。$2$ は含まれないため解なし。
概念図
ヒント（段階的開示）
ヒント1: 方向性
$p \equiv 3 \pmod 4$ なら $x=a^{(p+1)/4} \bmod p$ が直接答え（オイラーの規準から導ける）。しかし $p \equiv 1 \pmod 4$ ではこの式は使えない。$p-1$ を2で何回割れるかに着目したより一般的な手法が必要。
ヒント2: アプローチ
まず $a^{(p-1)/2} \equiv 1 \pmod p$（オイラーの規準）で平方剰余か判定する。平方剰余なら $p-1=Q\cdot2^S$（Qは奇数）と分解し、平方非剰余 $z$ を1つ探して初期値 $c=z^Q,t=a^Q,R=a^{(Q+1)/2}$ を用意。「$t$ が1になるまで2乗し続けて最初に1になる回数」を見つけ更新するループ（Tonelli-Shanks法）を回す。
ヒント3: 誘導（コード骨格）
def tonelli_shanks(a, p):
a %= p
if a == 0:
return 0
if pow(a, (p - 1) // 2, p) != 1:
return None # 平方非剰余
if p % 4 == 3:
return pow(a, (p + 1) // 4, p)
q, s = p - 1, 0
while q % 2 == 0:
q //= 2; s += 1
z = 2
while pow(z, (p - 1) // 2, p) != p - 1:
z += 1
m, c, t, r = s, pow(z, q, p), pow(a, q, p), pow(a, (q + 1) // 2, p)
while t != 1:
t2i, i = t, 0
for i in range(1, m):
t2i = t2i * t2i % p
if t2i == 1:
break
b = pow(c, 1 << (m - i - 1), p)
m, c, t, r = i, b * b % p, t * b * b % p, r * b % p
return r模範解答 (Python)
import sys
def tonelli_shanks(a, p):
a %= p
if a == 0:
return 0
if pow(a, (p - 1) // 2, p) != 1:
return None # 平方非剰余 → 解なし
if p % 4 == 3:
return pow(a, (p + 1) // 4, p)
q = p - 1
s = 0
while q % 2 == 0:
q //= 2
s += 1
z = 2
while pow(z, (p - 1) // 2, p) != p - 1:
z += 1
m = s
c = pow(z, q, p)
t = pow(a, q, p)
r = pow(a, (q + 1) // 2, p)
while t != 1:
t2i = t
i = 0
for i in range(1, m):
t2i = (t2i * t2i) % p
if t2i == 1:
break
b = pow(c, 1 << (m - i - 1), p)
m = i
c = (b * b) % p
t = (t * c) % p
r = (r * b) % p
return r
def main():
data = sys.stdin.buffer.read().split()
p, a = int(data[0]), int(data[1])
x = tonelli_shanks(a, p)
if x is None:
print(-1)
else:
print(min(x, p - x))
main()計算量:
pow(base, exp, p) は $O(\log p)$。外側ループは $O(\log p)$ 回、内側探索も $O(\log p)$ で全体 $O(\log^2 p)$。Step-by-Step 解説
1自明ケースとオイラーの規準
$a=0$なら$x=0$。それ以外は$a^{(p-1)/2}\bmod p$で平方剰余判定。
$a=0$なら$x=0$。それ以外は$a^{(p-1)/2}\bmod p$で平方剰余判定。
2$p\equiv3\pmod4$の特殊ケース
$x=a^{(p+1)/4}$が直接解。$(a^{(p+1)/4})^2=a\cdot a^{(p-1)/2}=a\cdot1=a$より。
$x=a^{(p+1)/4}$が直接解。$(a^{(p+1)/4})^2=a\cdot a^{(p-1)/2}=a\cdot1=a$より。
3一般ケースの分解
$p-1=Q\cdot2^S$に分解し非剰余$z$から$c=z^Q$を用意。$R^2=a\cdot t$という不変条件を保ちながら$t$を1に近づける。
$p-1=Q\cdot2^S$に分解し非剰余$z$から$c=z^Q$を用意。$R^2=a\cdot t$という不変条件を保ちながら$t$を1に近づける。
4メインループでの縮小
各反復で$t$の位数（2べき）が真に小さくなるため高々$S=O(\log p)$回で終了。
各反復で$t$の位数（2べき）が真に小さくなるため高々$S=O(\log p)$回で終了。
5出力の正規化
解は$x$と$p-x$の2つ。小さい方を
解は$x$と$p-x$の2つ。小さい方を
min(x,p-x)で出力。よくあるミス
| ミス | 原因 | 正しい書き方 |
|---|---|---|
| オイラーの規準チェックを省略 | 事前判定を忘れる | pow(a,(p-1)//2,p)!=1なら即座にNone |
| $p\equiv1\pmod4$でも特殊式を使う | 適用条件の勘違い | p%4==3の場合のみ特殊式 |
| 非剰余判定の条件式の符号ミス | 剰余/非剰余の判定式の勘違い | 非剰余は結果がp-1になる方 |
| 出力を$x$のみにする | 「最小のもの」の指定を見落とし | min(x, p-x)を出力 |
次のステップ
- 発展: $p$が素数べき($p^k$)の場合への一般化（Hensel持ち上げ）
- 発展: $k$乗剰余への拡張（Adleman-Manders-Miller algorithm）
- 次回予告: FFTを用いたワイルドカード文字列マッチング