椭圆曲线和整数之间的映射点

#1 楼

我不知道有什么通用的方法可以创建想要的映射（如果有的话，它可能会变成一种有效的点计数算法，这会很棒），但是您可以在某些曲线上进行此操作。

考虑一个质数$ p $等于$ 2 $取模$ 3 $。在$ \ mathbb {Z} _p $中，每个值都有一个多维数据集根（因为$ 3 $然后是$ p-1 $的可逆模）。然后，查看曲线$ y ^ 2 = x ^ 3 + 1 $。对于$ y $的任何值，$ y ^ 2-1 $具有唯一的立方根$ x $，因此该曲线上的非无限点与其在$中的$ y $坐标之间存在一对一的映射。 \ mathbb {Z} _p $。为了完整起见，将“无穷大点”映射到整数$ p $，就可以设置好：在$ p + 1 $曲线元素和以模数$ p + 1 $进行整数之间的简单双射映射。 >
此外，该曲线是配对友好的，嵌入度仅为$ 2 $（因为$ p + 1 $除以$ p ^ 2-1 $）。它还允许使用失真图，这样您就可以进行对称配对：如果$ \ mu $是$ 1 $的立方根，与$ 1 $不同（所以$ GF（p ^ 2）$的元素，字段扩展），那么从$（x，y）$到$（\ mu x，y）$的映射$ m $是曲线上的一个态射。然后，您可以定义一个配对$ e（P，Q）$，其中$ P $和$ Q $都是原始曲线上的点（在$ \ mathbb {Z} _p $中），作为计算的Tate（或Weil）配对超过$ P $和$ m（Q）$。这使您可以尽可能多地停留在基本曲线上。

本·林恩（Ben Lynn）在其博士学位论文中展示了一些细节（他称该曲线为“ B型”）。请注意，由于存在一对嵌入度$ 2 $，因此曲线上的离散对数会“减少”为$ GF（p ^ 2）$字段中的离散对数。因此，为了获得适当的安全性，$ p $必须至少为512位长。


编辑：类似的技巧适用于等式为$ y ^ 2 = x的“ A型”曲线$ \ mathbb {Z} _p $中的^ 3 + ax $ for $ p = 3 \ mod 4 $和一个常数$ a $。对于给定的$ x $，则恰好出现以下三种情况之一：


有两个不同的值$ y $使得$（x，y）$是一个有效点，并且它们彼此相对，因此一个值小于$ p / 2 $而一个值较大。不是有效的$（x，y）$点，但是对于两个不同的$ y $值有两个有效的$（-x，y）$点。
$（x，0）$是有效点，因此$（-x，0）$也是如此（仅当$ -a $是平方模$ p $时才可能发生）。

因此可以映射点$（x， y）$ to：


$ x $ if $ 1 \ leq y \ lt p / 2 $
$ -x $ if $ p / 2 \ lt y \ lt p $
$ x $如果$ y = 0 $

然后将无穷大点映射到$ p $，就可以了。