ICPC 4270 Discret Square Roots

本星期 Individual Training 的題目
是 Hefei 2008 的題目

聲明：以下算法仍然有漏洞... 有待修補

---

題意：

給定 x, r, N
求出所有 y (1 ≤ y < N) 使得
y² = x (mod N)
其中已知
r² = x (mod N)

數據範圍：

• 2 ≤ N < 1,000,000,000
• 1 ≤ x, r < N

---

分析：

首先，你只有以下的公式：

y² = x (mod N) ──── (1)
r² = x (mod N) ──── (2)

(1) - (2) 得
(y-r)(y+r) = 0 (mod N)
⇒ (y-r)(y+r) = aN


對於所有 y，必然 存在 f 及 N/f 使得
f | y-r　及
N/f | y+r
其中 f | N ──── (*)

所以我們可以用 窮舉法

窮舉 N 的因數 - f
窮舉 y = fK - r 及 y = fK + r（限制 0 ≤ y < N)
對每個 y，驗證 (1)，若通過記錄答案

如果 f 很小
（例如 f=2 而 N=10910⁹）
窮舉過程會很慢... 大約 O(N)...

然而，考慮到在 (*) 之中， f 與 N/f 的對稱性
我們只需要以兩者較大的一個（ i.e., max{f, N/f} ）窮舉 y

［修補 @ 2010-07-18 4:13am］
可是，這樣又會遺漏了一某些 y

設某 y = (N/f)k + r
則

［／修補中... 未完］

---

算法：

窮舉 N 的因數 - f ，其中 f ≥ sqrt(N)　　　　　　　［O(#因數)]
窮舉 y = fK - r 及 y = fK + r（限制 1 ≤ y < N）［O(sqrt(N))]
對每個 y，驗證 (1)，若通過記錄答案
對每個 N - y，驗證 (1)，若通過記錄答案

時間複雜度 = O( #因數 × sqrt(N) )

---

Subtlety：

y 滿足 (1) ⇒ N-y 滿足 (1)
所以只需考慮 1 ≤ y ≤ N/2
somehow 將算法加快一倍

然而實驗證實，為此所需的 overhead 使實現快不了多少...