secp256k1点密度

Question

我正在使用secp256k1椭圆曲线做一个密码项目。

我知道，通过随机选择第一个坐标P = (x, y) (其中p是椭圆曲线场\mathbb{F}_p的素数)，并使用曲线方程y^2 = x^3 + 7计算第二个坐标y，我可以从曲线中选择一个随机点D4。因为曲线的辅助因子是h = 1，所以对于每个生成有效y \in \mathbb{Z}_p的值x \in \mathbb{Z}_p，曲线上都有一个坐标为x, y的点。如果有一个x \in \mathbb{Z}_p值，而曲线方程找不到y \in \mathbb{Z}_p的有效值，这就意味着在x坐标下曲线上根本没有点。

我也知道曲线的顺序是q和q < p。这意味着曲线上存在q有效点，这比x在\mathbb{Z}_p中可以得到的所有值都少。

我的问题是:相对于x坐标，各点相距有多远？曲线上两点之间的最大距离是多少？这方面是否有任何文件？

Answer 1

我也知道曲线的顺序是q和q。这意味着曲线上存在q有效点，

真的

，这比x在\mathbb{Z}_p中可能拥有的所有值都少。

实际上，这不像你想象的那么重要。

• 对于具有有效解的x值，\mathbb{Z}_p中有两个满足方程的y值(因此对应于两点)。很容易看出，如果(x, y)是一个解决方案，那么(x, -y) (又名(x, p-y))也是一个解决方案。

注意:一些椭圆曲线的1或3个x值对应于单个y值(即y值0) -- secp256k1不是这些曲线中的一条。

此外，还有一个“无穷大点”，它不对应于方程的解，而是作为一个附加的组元素加入。

因此，确实存在对应于(至少一个)有效点的(q-1)/2 x值。从p \approx. q开始，如果您随机选择一个x值，那么您几乎完全有50%的概率选择一个有解决方案的值。