如何確定橢圓曲線組中二次殘差的比例？
我正在使用“嘗試和遞增”方法來散列到橢圓曲線點，如下所述。
帶安全參數 $ k $ , EC 方程 $ y^2 = x^3 + ax + b \mbox{ mod } q $ ， 我們有：
$ u = sha256(\mbox{message}) $
$ \mbox{for } i = 0 \mbox{ to } k - 1, \mbox{ do:} $
$ \quad x = (u + i) \mbox{ mod } q $
$ \quad \mbox{if } x^3 + ax + b \mbox{ is a quadratic residue in } \mathbb{F}_q \mbox{ then } $
$ \quad \quad \mbox{ return } Q = (x, \sqrt{(x^3 + ax + b}) $
$ \mbox{return Q = nil, nil} $
使用 EC 組生成器訂單 $ n $ 和現場順序 $ q $ , 我想這個比例 $ x \in \mathbb{F}_q $ 計算不產生二次殘差的 $ \frac{q - n}{q} $ ，這可以忽略不計，因此需要一個非常小的安全參數，但我已經讀過（例如這里和這裡？）該比例接近 $ \frac{1}{2} $ ，這將需要使用更大的 $ k $ . 這也說明了here，與 $ p $ 作為 $ q $ 和 $ E $ 作為 EC 組：
一個元素 $ a $ 的 $ \mathbb{F}_p $ 如果存在非零，則稱其為二次餘數 $ b \in \mathbb{F}_p $ 這樣 $ b^2 \equiv a \mbox{ mod }p $ . 在 $ \mathbb{F}_p $ , 正好有 $ (p-1)/2 $ 二次殘差。
尋找點 $ (x, y) $ 上 $ E $ 相當於找到這些值 $ x $ 這樣 $ x^3 + ax + b $ 是二次餘數模 $ p $ ; 因此我們可能期望 $ x^3 + ax + b $ 是一個平方模 $ p $ 大約一半的時間。
安全參數應該有多大？
我如何工作的比例 $ x $ 座標，知道 $ n $ 和 $ q $ ，這不會導致 $ x^3 + ax + b $ 那是二次餘數？
我讀過這個比例接近 $ \frac{1}{2} $
那實際上是正確的；它是（對於大 $ p $ )非常接近 $ \frac{1}{2} $ ; 因此，如果你需要你的散列過程最多失敗的機率 $ 2^{-64} $ ，你需要你的參數 $ k \ge 64 $
我可以想像這個比例 $ x \in \mathbb{F}_q $ 計算不產生二次殘差的 $ \frac{q - n}{q} $ , 這可以忽略不計
我相信這就是您感到困惑的地方；你似乎在推理“我們知道一定有 $ n-1 $ 解決方案 $ y^2 = x^3 + ax + b $ ; 有 $ q $ 的可能值 $ x $ ， 並作為 $ q \approx n $ , 那麼幾乎所有可能的值 $ x $ 必須是解決方案的一部分。
您缺少的部分是，對於（幾乎）每個值 $ x $ 這是一個解決方案，有兩種可能 $ y $ 與之對應的值；也就是說，如果對 $ (x,y) $ 是一個解決方案 $ y^2 = x^3 + ax + b $ , 那麼也是 $ (x, -y) $ . 唯一的例外是如果 $ (x, 0) $ 是一個解決方案，最多有3種可能 $ x $ 滿足這一點的值；因為 3 與 $ q $ ，我們可以忽略這個分析。
正因為如此，大約有 $ (n-1)/2 $ 可能的 $ x $ 等式的可能解的值；也就是說，這會導致二次殘差。因為 $ n \approx q $ , $ (n - 1) / 2 / q \approx \frac{1}{2} $