一类退化三次曲线及其在离散域的应用

作者: LostAbaddon | 来源:发表于2021-01-27 17:30 被阅读0次

模p整数域中椭圆曲线上的加法群

我们通常使用的椭圆曲线加密算法，都是建立在模p整数域 $\mathrm{F}_p$ 中椭圆曲线上的加法群上的，其主要使用的特点，是这个加法群中计算 $P = n G, G \in \mathrm{F}_p \land n \in N$ 是相对很简单的，但如果知道P和G要反过来求n则非常困难。它是循环群上离散对数问题（应用它的加密算法是ElGamal加密算法）在椭圆曲线加法群上的推广。

我们这里就来简要介绍一下这个群是什么样的。

椭圆曲线及其上的加法

椭圆曲线是形如下式的曲线：

$y^2 = x^3 + a x + b$

其中为了避免奇点，我们要求 $4 a^3 + 27 b^2 \neq 0$ 。

下面就是一个椭圆曲线的示例：

椭圆曲线

接下来，我们过曲线上两点来做一条直线，显然由于椭圆曲线是三次曲线而直线是一次，最后交点方程是一个三次方程，它有三个解，其中两个是我们已知的两点，而第三个解就是直线与椭圆曲线相交的第三点。也即，任意一条直线最多与椭圆曲线相交与三点，我们将其记为A、B、C。

接着，我们定义上述三个交点满足椭圆曲线上的加法： $A + B + C = 0$ 。

注意，这里的加法并不是通常意义上我们在实数域上所定义的加法，而是椭圆曲线上的加法，只不过依然用“+”这个符号来表示而已。

由于直线与椭圆曲线相交最多只有三个交点，最少可以没有交点，所以我们为椭圆曲线补上无穷远点，这样如果发现在通常的无限大平面上直线与椭圆曲线的交点不足三个，那我们可以说还有一到三个交点在无穷远处，即都是无穷远点。

这样的椭圆曲线称为“射影椭圆曲线”，但我们一般直接称它为椭圆曲线就足够了，只是大家要记住这里要补上了一个无穷远点。

因此，我们现在可以说：任何一条直线与椭圆曲线的交点都有三个。

实际上我们可以说必然有四个，因为等式右边的0也可以视为无穷远点，而实际上无穷远点并不是真的只是一个点，直线的两端都会在无穷远点上和椭圆曲线“相交”。

而加法运算也就可以通过直线与椭圆曲线的交点来给出。

比如，如果我们已知椭圆曲线上两点A和B，过它们的直线与椭圆曲线还会有第三个交点C'，那么C'关于x轴的对称点C就是A和B在椭圆曲线加法操作下的结果，如下图：

image

我们下面来手算一下这样定义的加法的结果：

$\begin{cases} y^2 = x^3 + a x + b\\ y = k x + m \end{cases} \Rightarrow\\ x^3 - k^2 x + (a - 2 k m) x + b - m^2 = 0\\ \because \left( x- x_A \right) \left( x- x_B \right) \left( x- x_C \right) = 0\\ \therefore \begin{cases} x_A + x_B + x_C = k^2\\ x_A x_B + x_B x_C + x_C x_A = a - 2 k m\\ x_A x_B x_C = m^2 - b \end{cases}\\ \therefore \begin{cases} x_C = \left( \frac{y_A - y_B}{x_A - x_B} \right)^2 - \left( x_A + x_B \right)\\ y_C = \frac{ \left( x_A - x_C \right) \left( y_A - y_B \right) }{ x_A - x_B } - y_A \end{cases}$

上述结果是在A和B的x坐标不相等时成立的，因此我们还需要补充考虑两个例外情况。

首先，如果A和B关于x轴对称，那结果直线与y轴平行，结果是第三交点为无穷远点，答案就是0（体现在x坐标上就是无穷大）。

而如果A和B是同一个点，那此时直线与椭圆曲线相切，结果便调整为：

$\begin{cases} x_C = \left( \frac{3 x_A^2 + a}{2 y_A} \right)^2 - 2 x_A\\ y_C = \frac{ \left( x_A - x_C \right) \left( 3 x_A^2 + a \right) }{ 2 y_A } - y_A \end{cases}$

这么一来，加法的定义就完成了，下面来看它是否构成群。

群是满足如下四条定义的带二元运算“+”的集合G：

封闭性：如果a和b都是G的元素，那a+b也必须是G的元素；
单位元：存在单位元e，使 $a+e=e+a=a$ ；
可逆性：必然存在唯一的元素b使 $a+b=b+a=e$ ；
结合律： $(a+b)+c=a+(b+c)$

如果还满足交换律 $a+b=b+a$ ，那这样的群就被称为阿贝尔群。

我们前面在椭圆曲线上定义的加法运算，封闭性、单位元和可逆性是显然满足的，甚至交换律也是显然满足的，关键就是是否满足结合律。所以我们下面用一个“巧妙”的方式来证明这点。

首先要介绍一下Cayley-Bacharach定理：

Cayley-Bacharach定理：射影平面内，任意两条不同的平面三次曲线会相交于9点（相切算两点），那么如果第三条不同的平面三次曲线经过了其中任意8点，则它必然经过第九点。

接着，我们用 $A \circ B$ 表示通过A和B的直线与给定椭圆曲线E相交的第三点，因此就有 $A + B = O \circ (A \circ B)$ ，这里O为无穷远点，它还能给出一个很有用的性质： $O \circ (O \circ A) = A$ 。

于是，我们可以构造这么三条直线：

$\begin{cases} L_1 = \overline{A, B, A \circ B}\\ L_2 = \overline{C, A + B, C \circ (A + B)}\\ L_3 = \overline{B + C, B \circ C, O} \end{cases}$

用这三条直线可以构造一个很“奇特”的三次曲线，一条退化三次曲线：

$C_1: \left( y - k_1 x - m_1 \right) \left( y - k_2 x - m_2 \right) \left( y - k_3 x - m_3 \right) = 0$

这里三个括号中的就是上述三条直线的标椎方程。

显然，退化三次曲线 $C_1$ 与原椭圆曲线 $E$ 相交于9个点（这九个点记录 $\left< C_1, E \right>$ ）： $C \circ (A + B)$ 、 $A$ 、 $B$ 、 $C$ 、 $A \circ B$ 、 $A + B$ 、 $B + C$ 、 $B \circ C$ 以及无穷远点 $O$ 。

接下来，我们再构造三条直线：

$\begin{cases} \Gamma_1 = \overline{C, B, C \circ B}\\ \Gamma_2 = \overline{A, C + B, A \circ (C + B)}\\ \Gamma_3 = \overline{B + A, B \circ A, O} \end{cases}$

它们一样可以构成一条退化三次曲线 $C_2$ ，它和 $E$ 一样相较于九个点 $\left< C_2, E \right>$ ，和 $\left< C_1, E \right>$ 可知有8个点是相同的，差别在于第九个点，之前是 $C \circ (A + B)$ 而现在是 $A \circ (C + B)$ 。

根据上面提到的Cayley-Bacharach定理，我们可以断定 $C \circ (A + B) = A \circ (C + B)$ 。再结合 $A + B = O \circ (A \circ B)$ 与 $O \circ (O \circ A) = A$ ，就可以得到我们所要的结合律（别忘了椭圆曲线上的加分满足交换律）： $(A + B) + C = A + (B + C)$ 。

那如果A、B、C中有点相同怎么办？别忘了Cayley-Bacharach定理中切点算两个点，所以一样可以用。

至此，我们就证明了上面所定义的椭圆曲线上的加分可以构成群。

附带一提，除了很少的几个例外，几乎所有平面三次曲线都可以通过坐标变换变成椭圆曲线。其中有几类很有趣的特例：三条直线（一次曲线）的并（也就是我们上面构造的两条退化曲线），以及，一条圆锥曲线与一条直线的并，都被归类为“退化椭圆曲线”。

实数域子域上的椭圆曲线

从前面关于椭圆曲线的定义可以看出，虽然我们将其定义在实数域的射影平面上，但实际上可以定义在各类域上，比如最常见的复数域。

我们可以先看有理数域上的椭圆曲线，即只考虑一条椭圆曲线上的所有有理点（x和y都是有理数），按照之前得到的结果，其加法结果为：

$\begin{cases} x_C = k^2 - \left( x_A + x_B \right)\\ y_C = k \left( x_A - x_C \right) - y_A \end{cases}\phantom{wwwwwww}\\ k = \begin{cases} \frac{y_A - y_B}{x_A - x_B} \phantom{www} x_A \neq x_B\\ \infty \phantom{wwwaaa} x_A = x_B \land y_A \neq y_B\\ \frac{3 x_A^2 + a}{2 y_A} \phantom{wwai} x_A = x_B \land y_A = y_B \end{cases}$

很显然，只要A和B本身是有理点、曲线E的参数a和b也都是有理数，那A+B也必然是有理点。

Mordell-Weil定理告诉我们：有理数域上的任意（非退化）椭圆曲线加法群都是有限生成阿贝尔群： $E(\mathbb{Q}) = \mathbb{Z}^r \oplus T$ ，r被称为E的秩，T是E的挠点集。

也就是说，我们只需要有限个有理点，然后通过椭圆曲线加法就可以找出它的所有有理点——当然，要找到所有这些基点（用来生成其它有理点的初始有理点）本身是非常困难的，但我们至少知道它数量有限。

我们可以将数域做进一步限制：如果是整数域呢？

Siegel定理告诉我们：任意（非退化）椭圆曲线的整点，或者x与y之一为整数的点，只有有限多个。

如果我们再将数域进一步压缩，压缩到有限域，那就有另一个定理了——

Hasse定理：有q个元素的有限域上任意（非退化）椭圆曲线的点的数量N满足 $|N - (q + 1)| \leq 2 \sqrt{q}$ 。

在椭圆曲线密码学中，我们所使用的就是一类特定的有限域： $\mathbb{F}_p$ ，即整数模p域，p是一个素数。

所谓整数模p域，其实很好理解，就是只考虑从0到p-1这p个整数所构成的域。对于椭圆曲线而言，就是将其做模运算：

$y^2 \mod p = x^3 + a x + b \mod p$

我们一般可以将左侧的(mod p)省略。

我们可以先考虑实数模p域，此时椭圆曲线其实等价于这么一组：

$y^2 = x^3 + a x + b + n p \ \ \ \ n \in \mathbb{Z}, \ \ x \in [0, p), \ \ y \in [0, p)$

我们可以来看一个简单的例子：

y^2 = x^3 - 7 x + 10 (mod 3)

当然，对我们实际使用来说最有意义的是所谓的“整点”（即xy坐标都是整数的点）的分布，所以我们下面来看同一条椭圆曲线在不同模下的整点分布情况：

y^2 = x^3 - 7 x + 10 (mod p), p = 19, 97, 127, 487

同样的，现在连接曲线上两点A和B的直线其实可以视为一组直线而不是一条：

$y \mod p = k x + m \mod p \Rightarrow\\ y = k x + m + n' p \ \ \ \ n' \in \mathbb{Z}, \ \ x \in [0, p), \ \ y \in [0, p)$

接着，我们依然使用和实数域上椭圆曲线相同的方式来定义 $\mathbb{F}_p$ 上的椭圆曲线的加法，从而会发现其实结果在形式上是一样的，只需要加上mod p即可：

$\begin{cases} x_C = k^2 - \left( x_A + x_B \right) \mod p\\ y_C = k \left( x_A - x_C \right) - y_A \mod p \end{cases}\phantom{wwwwwww}\\ k = \begin{cases} \frac{y_A - y_B}{x_A - x_B} \mod p \phantom{www} x_A \neq x_B\\ \infty \phantom{wwwwwwwwaaa} x_A = x_B \land y_A \neq y_B\\ \frac{3 x_A^2 + a}{2 y_A} \mod p \phantom{wwai} x_A = x_B \land y_A = y_B \end{cases}$

这里需要注意的是除法。在实数模p域中，其结果是非唯一的， $\frac{1}{x}$ 、 $\frac{1 + p}{x}$ 、 $\frac{1 + n p}{x}$ 都可以是x的逆。在整数模p域中，x的逆定义为 $x \times y = 1 \mod p$ 。因此上面计算斜率时，实际上是我们先求出 $x_A - x_B$ 或 $2 y_A$ 的逆，然后再做其余的运算。

下面是一个简单的例子：

y^2 = x^3 - x + 3 (mod 127) 上整点的加法

当然还有更复杂的情况，比如：

y^2 = x^3 + 2 x + 3 (mod 97) 上整点的加法

这个是不是看上去很“过分”？

整数模p域中椭圆曲线有一个很有趣的性质，那就是对每个点P，都存在一个自然数n，使得 $nP=0$ ，我们将这个n称为点P的阶（满足这个条件的自然数n可以无限多，我们取最小的那个）。另一方面，现在这条椭圆曲线上总共有多少点N，被称为这条椭圆曲线的阶。根据Lagrange定理有： $N = \prod_P n(P)$ 。

下面才到最有趣的部分：假定我们知道了 $G = n P$ 中的P和G，是否可以反推出自然数n？

推当然是可以推的，但这个计算几乎没有任何捷径可走，只能不断暴力求解（当然，诸如“Baby step, Big step”和“Pollard rho”算法可以将求解次数做一个降低，但本质上也算是暴力求解了）。

这就是著名的“离散对数难题”。

之所以说是离散“对数”而不是离散“除数”，是因为它形式上与循环群上的ElGamal算法中的对数很像，所以习惯上沿用了ElGamal算法中的“离散对数”的称呼。

ElGamal算法中，我们从q阶循环圈Q中选择一个群元P，然后再从1到q-1中选择一个自然数n，计算 $G = P^n$ 。现在如果你知道了P和G，要反推n，那将非常困难。

利用有限域上椭圆曲线加法群的加密算法

假定，端点星要将一个数据M传递给索拉里星，但川陀会进行拦截，那它应该怎么办？

如果使用RSA加密算法，一个简单流程是这样的：

索拉里星找到两个大素数p和q，并计算 $N=pq$ 及 $r=(p-1)(q-1)$
选小于r且与r互质的自然数e，及e的模r逆d： $ed=1 \mod r$
$(N,e)$ 是公钥公开广播给全宇宙，而 $(N,d)$ 是私钥，只有索拉里星人自己知道
端点星人计算 $C=M^e \mod N$ ，并全宇宙广播
索拉里星人计算 $M=C^d \mod N$

整个过程中，川陀人如果想要破译，就必须从N求解p和q，但这是非常困难的一件事。这个求解被称为“素数分解问题”。

如果使用ElGamal算法，那过程是这样的：

索拉里星人选择一个q阶循环群Q，Q的一个元素P，1到q-1的一个自然数n，并计算 $G=P^n$ ，将 $(Q,P,G)$ 作为公钥全宇宙广播
端点星人在1到q-1中随机选择一个自然数m，并计算 $C_1=P^m$ 和 $C_2=M G^m$ ，这里M已经被编码为Q中元素，编码方式公开透明，接着端点星人广播 $(C_1,C_2)$
索拉里星人计算 $M=C_2 \left( C_1^n \right)^{-1}$

整个过程中，川陀人如果想要破译，就必须求解 $G=P^n$ ，这个“循环群上的离散对数问题”一样非常困难。

最后，如果使用椭圆曲线加密算法，那过程和ElGamal算法的过程非常类似：

索拉里星人选择一条椭圆曲线 $(a,b)$ 与有限域的模参数q，并寻找曲线上的一个整点P，确保P的阶l足够大，选择不大于l的自然数n，计算 $G=nP$ ，将 $(a,b,q,P,G)$ 作为公钥全宇宙广播
端点星人随机选择不大于l的自然数m，计算 $C_1=mP$ 和 $C_2=M+mG$ ，这里M已经被编码为椭圆曲线上整点，编码方式公开透明，接着端点星人广播 $(C_1,C_2)$
索拉里星人计算 $M=C_2-nC_1$

是不是发现椭圆曲线加密算法和ElGamal算法几乎一样？事实上由于整数模p域上整点的阶有限，所以它实际上也构成了一个循环群，因此和ElGamal算法一样都是循环群上的离散对数问题，只不过椭圆曲线上的加法比ElGamal算法选用的循环乘法计算起来更复杂一点而已。

事实上，密码学家早就发现ElGamal算法与RSA算法具有相似的数学结构，都可以用量子计算机上的经典Shor算法予以破解。而椭圆曲线加密算法（ECC）在2015年时被Kirsch和Chow指出一样可以用修改后的Shor算法来破解，而且由于ECDSA的密钥空间相比RSA更小，所以破解起来很可能更快更方便。这点甚至早在2003年的时候就被Proos和Zalka证明过[^proof]：160比特的ECC可以用1000量子位的量子计算机来破解，而一般认为安全等级相同的1024位的RSA却需要使用2000量子位的量子计算机才能破解。

[proof]: J. Proos and C. Zalka, “Shor’s Discrete Logarithm Quantum Algorithm for Elliptic Curves,” Quantum Info. Comput., vol. 3, no. 4, pp. 317–344, 2003.

PS：Proos和Zalka也给出了一些如何用Shor算法破解ECC的思路，但Kirsch和Chow给出了具体的算法，所以两者工作虽然看上去很接近，但到底还是不一样的。

换一个玩法

上面我们介绍了传统有限域上椭圆曲线上加法群即用于加密的一些情况，但这不是我们这篇文章的重点。

我们希望讨论这么一个问题：如果换一种曲线，会怎么样？

而且，实际上我们最后在ECC中所用到的性质，实际上总结下来就一句：整点P在特定加法定义下可以构成循环群。

事实上，由于要做加法的话需要三个点，所以是不是只要一组曲线与一条直线有三个交点，就可以构造这样的加法操作呢？而且三条直线的并本身就是一种退化了的椭圆曲线嘛，它显然可以构造这种与一条直线有三个交点的情况。

10曲线上的加法群

我们将一根直线并上一个椭圆的形式，称为“10曲线”。

我们先从最简单的正圆开始：

$\left( y^2 + x^2 - R^2 \right) (x - L) = 0$

这样的三次曲线当然可以通过恰当的“坐标变换”变成一条椭圆曲线：
$\begin{cases} z = y \sqrt{x - L}\\ w = x - \frac{1}{3} L \end{cases}\Rightarrow\\ z^2 + w^3 - \left( \frac{1}{3} L^2 + R^2 \right) w + \frac{2}{27} \left( 9 R^2 - L^2 \right) L = 0\\$
但这样的坐标变换存在一个问题，那就是当 $x<L$ 时，z其实已经是虚数了，因此在实空间它无法正确表达直线左侧的圆部分的情况。而直线部分在坐标变换后完全退化到了 $\left( \frac{2L}{3}, 0 \right)$ 这一个点上，显然也不是什么好性质。因此，10曲线这样的三次曲线被称为是一种退化椭圆曲线，而10曲线上也会有一些正常椭圆曲线上所没有的性质。

下面，我们确保 $L^2 > R^2$ ，这样的曲线就不存在自相交点。接着，我们采取和椭圆曲线上加法一样的操作方式，过这条10曲线上两点做直线，该直线必与这条10曲线相交于第三点：如果前两点都在圆上，除非垂直于x轴，否则必与一旁的直线有交点；而如果垂直于x轴，那可以认为与直线相交于无穷远点O；如果一点在圆上一点在直线上，那要么圆上点正好是切点，要么必与圆有第二个交点。比较麻烦的是直线上两点，这个我们暂不考虑。

从而，这样的直线与10曲线的三个交点A、B、C就满足加法关系 $A+B+C=0$ 。

我们来计算两个情况下的加法结果。

第一种情况， $A=\{ R \cos \theta, R \sin \theta \}$ 而 $B = \{ R \cos \phi, R \sin \phi \}$ ，且A和B的x坐标不相等，这样C的y坐标值就是：

$y_C = \frac{ ( x_B y_A - x_A y_B ) - L ( y_A - y_B ) }{x_A - x_B}$

如果A和B垂直于x轴，那不用算了，结果就是无穷远点O。如果A和B重合，那此时结果变为：

$y_C = \frac{ L x_A - R^2 }{ y_A }\\$

而如果点B在直线上而点A在圆上，情况则变为：

$\begin{cases} x_C = 2 \frac{(x_A y_B - L y_A) (y_B - y_A)}{(y_B - y_A)^2 + (L - x_A)^2} - x_A\\ y_C = 2 \frac{(x_A y_B - L y_A) (L - x_A)}{(y_B - y_A)^2 + (L - x_A)^2} + y_A \end{cases}$

我们来看一个示意图：

L=10, R=5

那么，如果两个点都落在直线部分，加法要怎么做呢？

我们可以去直线上点X为圆上辅助点A和B的合，而另一个直线上点Y是圆上点A和C的合，然后计算B+C（显然落在直线上），再计算A+B+C（落在圆）上，最后计算2A+B+C（落在直线）上：

$y_C = \frac{y_A y_B + R^2 - L^2}{y_A + y_B}$

通过复杂的计算可以发现，直线上两点通过这种方式定义的和并不依赖于圆上辅助点A的选择（这里一开始程序出了个小错误，居然还得出了依赖圆上辅助点A的结论，汗……）。至此，我们终于合理定义出了整个10曲线上的加法，而且由于10曲线是退化了的椭圆曲线，所以由Cayley-Bacharach定理可知这个加法在10曲线上的确构成加法群。

对于椭圆也会有类似的结果，事实上对于任意椭圆，我们总可以通过缩放与旋转将其变换为10曲线，所以不会有什么特别的新结果出来。而且，这里的两个参数：圆半径R和直线到圆距离L，也并不是都自由，我们可以将L固定为1，而R是一个0到1之间的值。

因此10曲线的实际特征自由度，只有1个（即便使用椭圆也是如此）。

10曲线虽然在很大程度上和普通椭圆曲线很是相近，但也有一些不同。

比如，如果我们将L与R取为无理数，那整条10曲线上将没有一个有理点，更不用说整点了。而另一方面，如果L取为整数，那10曲线上的整点数显然为无穷多。这两个都是传统椭圆曲线所没有的特性。

我们下面再主要看一下直线上的点和圆上点P的和，特别是同一个点P的 $2n+1$ 次自加的情况。

我们假定直线上的点的y值为Y，而圆上点则是x轴正向旋转 $\theta_0$ 后得到的，这样两者的和到x轴正向的角度为 $\theta_1$ ，其值为：

$\theta_1 = \pi + \theta_0 - 2 \arctan \left( \frac{Y - R \sin \theta_0}{L - R \cos \theta_0} \right)$

这里岔开一下。
事实上，利用上面的结论，我们可以计算直线上两点利用辅助点来做加法的结果，实际上并不依赖辅助点的选择，这一结论。当然，证明过程会比较繁琐，你可以考虑使用Mathematica。

另一方面，我们可以用将x和y坐标换用下面这种形式来表达：

$x = R \frac{2 t}{1 + t^2};\ \ \ \ y = R \frac{1 - t^2}{1 + t^2}$

因此就有如下关系：

$\arctan t_1 = \frac{\pi}{2} + \arctan t_0 - \arctan \left( \frac{Y (1 + t_0^2) - 2 R t_0}{L (1 + t_0^2) - R (1 - t_0^2)} \right)$

也即：

$t_1 = \frac{L - R + Y t_0}{Y - (L + R) t_0}$

这个结果可以推广到如下形式：

$t_{n + 1} = \frac{L - R + Y t_n}{Y - (L + R) t_n}$

而这里Y就是2P的y值： $Y = \frac{L - R - (L + R) t_0^2}{2 t_0}$ 。

因此，如果存在某个n使 $\left| t_n \right| = \left| t \right|$ ，那此时这两个点要么相等，要么相加0，而如果是后者的话再和直上的点相加一次就可让新点和原来的点相等。

对于直线上的点也有类似的结论。

我们取直线上点P为 $\{L, Y\}$ ，则它的n倍点的y坐标为：

$Y_n = \frac{\sum_{i=0}^{n} (-1)^i C_n^{2i} Y^{n - 2i} (L^2 - R^2)^{i}}{\sum_{i=0}^{n-1} (-1)^i C_n^{2i+1} Y^{n-1-2i} (L^2 - R^2)^{i}}$

令 $Y_n = \frac{F_n}{H_n}$ ，则有： $F_n + i \sqrt{L^2 - R^2} H_n = \left( Y + i \sqrt{L^2 - R^2} \right)^n$ ，从而可以看出 $Y_n$ 实际上就是复空间矢量 $Y + i \sqrt{L^2 - R^2}$ 的幅角的余切乘上一个系数 $\sqrt{L^2 - R^2}$ 。

如果该矢量的幅角可以表达为圆周的有理数倍，那显然点P的若干次自加后会回到自身，否则P的自加只会不断填满整条直线而不循环。

同样的，由于任何直线外点P都可以表达为直线上一点Q和直线外一点C的和，我们取C为 $\{-R,0\}$ ，其特点为 $2C=0$ （之所以选择这个点的另一个原因，是将它写为参数形式时，它对应的参数为正负无穷，即无穷远点，从而可以和直线上的无穷远点对应），因此P的偶数次自加就等于Q的同样次数的自加，P的奇数次自加则等于Q的n-1次自加再加C，因此如果Q对应的复数的幅角不是圆周的有理数倍，那P就无法在有限次自加后回到自身，而只能不断填充以“布满”整个圆周部分。

这样的映射关系并不是10曲线所独有的，在椭圆曲线上也有。
比如，可以分解为一个闭合圆环加上一根无限长曲线的椭圆曲线，这样的映射关系的存在是显而易见的。而即便是没有独立闭合圆环的椭圆曲线，我们也总可以选择那唯一一个自己是自己相反点的、椭圆曲线与x轴的交点，然后它和椭圆曲线自身有两个切点，这两个切点将椭圆曲线分割为三部分，其中中间的部分可以通过完全一样的映射，映射到上下两部分，从而构成完全一样的一一映射。

所以说，10曲线上有可数无穷个点在自加有限次后会循环，但剩余不可数无穷个点则无法通过自加来回到自身，不断自加只能使其不断“填充”并“布满”整条10曲线，这个结论和Mordell-Weil定理也有所差异。

比如，当我们取 $L=10$ 、 $R=5$ ，初始点P为 $(4, 3)$ 时，自加6次（直线上会有三点）后循环。而如果取初始点P为 $(-4, 3)$ ，自加10000次后的结果（没有循环）如下图：

有趣的是我们可以看一下参数t的分布曲线（y值为自加次数）：

显然，存在一些有趣的周期性，我们将其转成次数-角度图来看会更明显：

我们可以取R为无限小，那么此时角度的递归关系将变为：

$\theta_1 = \theta_0 + \pi - 2 \arctan \left( \frac{Y}{L} \right)$

这就可以解释上面我们所看到的周期性：每一次自加（其实是加2P）都近似等价于在当前转角上加了 $\pi - 2 \arctan \left( \frac{Y}{L} \right)$ ，所以最后整体效果就等于是在不断旋转该点，从而可以呈现出周期性。但在R不是无穷小的实际情况中，每次的转角并不固定，所以会出现并不是完全一样的周期性——我们能看到一些短周期和一些长周期，比如下图（取前100次自加）：

可见，10曲线虽然是退化了的椭圆曲线，但两者的性质并不完全一样，10曲线有很多好玩的东西。

有限域上的10曲线

虽然我们前面说过决定10曲线特性的参数只有一个（即 $\frac{R}{L}$ ），但当我们考虑有限域的时候情况则可以有所不同。

比如我们可以如下形式的10曲线（还没有穷尽所有可能的10曲线形式）：

$Q (x, y) = \left[ \left( P_x x \right)^2 + \left( P_y y \right)^2 - \left( P_x R \right)^2 \right] \left( x - L \right)$

在实数域上我们总可以通过坐标旋转、平移、缩放来将其转换为标准形式，但在在 $\mathbb{F}_p$ 上情况则可能很不一样。

现在，10曲线的形式为：

$\left[ \left( P_x x \right)^2 + \left( P_y y \right)^2 - \left( P_x R \right)^2 \right] \left( x - L \right) = 0 \mod p$

我们可以看一些参数下现在的整点分布：

R=5,L=10,P_x=P_y=1,p=103

R=1,L=2,P_x=P_y=1,p=103

R=10,L=20,P_x=P_y=1,p=103

R=5,L=10,P_x=P_y=1,p=17

R=5,L=10,P_x=P_y=1,p=1009

R=5,L=10,P_x=1,P_y=10,p=103

可以发现，虽然在完整的实数域上它们是同一条10曲线，但在整数模p域 $\mathbb{F}_p$ 上却可以很不一样。

让我们回到非病态的正常的10曲线Z。

很显然现在10曲线可以拆分为直线部分 $x - L = 0\ (\mathrm{mod}\ p)$ 与直线外部分 $\left( P_x x \right)^2 + \left( P_y y \right)^2 = \left( P_x R \right)^2\ (\mathrm{mod}\ p)$ 。10曲线的阶，也即其上所有的点的总数，其实很容易计算： $N(Z) = 2 p + 2$ ，其中一个是无穷远点，p个点在直线上，p+1个点在直线外，且这p+1个点中一个点为 $(p - R,0)$ ，另外p个点可用下式来表示：

$\begin{cases} x = R \frac{1 - t^2}{1 + t^2}\mod p\\ y = R P_x P_y^{-1} \frac{2 t}{1 + t^2}\mod p \end{cases}$

之所以 $(p - R,0)$ 无法用上市表达，是因为在 $\mathbb{F}_p$ 上无法表达无穷大。

当然，必须要强调的是：并不是所有参数组合都能在 $\mathbb{F}_p$ 上构成合适的10曲线。

在实数域，10曲线的直线部分与圆圈部分只要 $L>R$ 就是彼此独立的、从而也就是合理的。但在 $\mathbb{F}_p$ 上情况将变得不同，现在直线部分依然是一条直线（准确地说是 $x=L$ 而y为0到p-1的整数的p个点），但直线外部分并不是一个简单的圆，从上式可以发现其实现在是一系列分布在“同心圆”上的整点，从而会从原来的正圆位置向内外“扩散”出去。

因此，就会存在一个很极端的情况：扩散出去的圆上整点，同时恰好落在了直线上。

当发生这种情况的时候，我们就认为所选的参数组合是“病态”的，它会使得现在10曲线上的加法的定义遇到障碍。

病态的10曲线还有很多。比如某些参数组合下（比如取L=13、R=5、P_x=1、P_y=3、p=103）可能会出现两个直线外点的连线与其中至少一个点相切这么一种诡异的情况（此时等于一根直线与10曲线相交于4点），这样的10曲线显然也是病态的。

所以，我们必须考虑选择恰当的参数，使得10曲线的行为不病态。

$\mathbb{F}_p$ 中10曲线上的加法的定义，形式上与实数域上的情况完全相同，只不过要注意除法需要用取模来做。此时直线外两点的和必然落在直线上，而直线外一点与直线上一点的和必然在直线外，直线上两点可以通过直线外的辅助点来构造且结果不依赖于辅助点的选择，这些结论都和实数域上10曲线的加法相同，且一样可以构成加法群。

但当参数选择是“病态”的时候，我们在那些导致病态的点上将无法定义合适的加法，这也是我们不选用病态10曲线的重要原因。

我们可以仿造 $\mathbb{F}_p$ 上椭圆曲线的做法来定义10曲线上每个点P的“阶” $l(P)$ 为能使 $n P = 0$ 成立的最小自然数n。记 $C(P)=\left\{ nP | n \in [1, l(P)) \right\}$ ，因此如果 $C(P_2) \subseteq C(P_1)$ ，那我们就说 $P_2$ 可由 $P_1$ 生成。通过这种方式我们可以将10曲线的所有点都划分为若干组，每一组都可以由一个元素通过有限次自加来遍历。我们将能生成组中所有元素的数称为“生成元”。

换一个角度来看，我们可以称无穷远点为零点，因为这是定义。然后，将两倍为零的点称为“半零点”，这样的点有三个： $\{R, 0\}$ 、 $\{p - R, 0\}$ 、 $\{L, 0\}$ 。

接着，如果一个点P可以表达为点Q的自加，即 $P = 2 Q$ ，则称Q是P的半点而P是Q的倍点。那，由于半零点有三个，我们很容易就可以得到结论：P的半点数是4的倍数，且一半在直线上，一半在直线外，且它们四个一组可以通过半零点相互转换。

当然，另一个更加直接的结论是：直线外点没有半点，而直线上点有的有半点有的没有。

n倍点的问题其实可以在上述由生成元生成的循环组中来考虑。

假定点P属于组 $C(Q)$ ，生成元为Q，从而有 $P = n Q$ ，那么P的x倍就是 $\mathrm{mod}(n x, l(Q)) P$ 。所以一个点是否有x分之一点就取决于是否存在整数m使下式成立：

$m x = n \mod l(Q)$

这样我们不用做具体的计算就能判断一个点是否存在n分之一点，以及有几个n分之一点。

直线上的n倍点，利用实数域上的结论可以写为：

$Y_n = \frac{\sum_{i=0}^{n} (-1)^i C_n^{2i} Y^{n - 2i} (L^2 - R^2)^{i}}{\sum_{i=0}^{n-1} (-1)^i C_n^{2i+1} Y^{n-1-2i} (L^2 - R^2)^{i}}\mod p$

由于当 $n \ge p$ 时， $C_n^m$ 除了m=0和m=n外别的值模p后都为0，因此不难发现 $Y_{p+1}=\infty$ ，即 $(p+1)P=0$ 。也因此，如果 $nP=0$ ，那么n必然是p+1的因子。

我们总可以取直线上一个特定的生成元 $E_0$ ，它可以通过p次自加来遍历直线上所有点，这个点就变得非常重要了。

另一方面，直线外一点总可以表达为 $\{-R,0\}$ 加上直线上某一点的形式，我们将 $\{-R,0\}$ 记为 $E_1$ ，则任何一个点都可以表达为 $n E_0 + d E_1$ 的形式，其中 $n \in [0, p)$ 而 $d \in \{0,1\}$ 。

形式上说，我们可以由此来定义 $\mathbb{F}_p$ 上10曲线的乘法：

$P_1 = n_1 E_0 + d_1 E_1;\ \ E_2 = n_2 E_0 + d_2 E_1\ \Rightarrow\\ P_3 = P_1 \times P_2 = \mathrm{mod}(n_1 n_2, p) E_0 + d_1 d_2 E_1$

这里第二部分不用写取模的理由倒也是很简单：它的结果要么是0要么是1，没有取模的必要。

这种定义的好处，便是它天然具备乘法环的所有要素，但缺点就是我们如果要做计算，那首先要解决如何用生成元的倍点来表达指定点这一离散对数问题，难度颇高。当然，从形式上说这样的定义一点问题都没有。

同样的，这个定义也可以用在 $\mathbb{F}_p$ 的至少部分椭圆曲线上，因为前面已经提过，只要椭圆曲线包含一个y值为0的点，那么我们总可以通过椭圆曲线加法将整条椭圆曲线分割为彼此一一对应的两部分（如果椭圆曲线可以分解为一个闭环加一条曲线，则这种分割很显然；如果是一条完整的曲线，前面也介绍过，可以分解为两个切点之间的部分与两个切点之外的部分），从而可以写为 $n E_0 + d E_1$ 的形式。

容易证明，这样定义的乘法结合之前定义的加法，可以在 $\mathbb{F}_p$ 上的10曲线和椭圆曲线上构成一个交换除环，即一个域。且这个域有一个子域，它是10曲线的直线部分，也是椭圆曲线的非闭合曲线或非中段曲线部分，因此整个10曲线与椭圆曲线作为一个域，是直线域（椭圆曲线就是非闭合曲线域或非中段曲线域）的单扩张域， $\{-R,0\}$ （椭圆曲线就是前面提到的那个与x轴的交点）就是该扩张的本原元。

和椭圆曲线可以用倍点分解很困难这个特性来构造ECC一样，10曲线也可以利用倍点分解很困难这个特性来构造加密算法，我们可以将之称为OZCC。OZCC和ECC其实都用到了域上的乘法，但其保密安全性来源于倍点分解而不是乘积分解的难度。因此ECC和OZCC本质上和ElGamal算法是相同的，都是模幂难题，只不过用加法来自然构造出了完整的循环群而已。

如果要进一步拓展10曲线，我们可以将 $R^2$ 用一个整数 $R$ 来取代，这样 $\mathbb{F}_p$ 上的点分布还能有更多的变化（比如此时直线外部分很可能没有y值为0的点，从而上面那种直线内外一一对应的做法将不再适用），也可以用双曲线提到圆而将直线放在y轴上从而构造“川”形曲线，也能得到很多相近但又不完全相同的性质，也可以构建域。

我们可以发现，10曲线虽然是退化的三次曲线，很多性质相对椭圆曲线有了不少的简化，但在其上构建加法群甚至一个域的方法和椭圆曲线是相同的，我们也可以拿来做很多有趣的事。

至少，用来造一个循环群然后仿ElGamal或ECC的方法来构造一个加密算法，问题不是很大。

一类退化三次曲线及其在离散域的应用

模p整数域中椭圆曲线上的加法群

椭圆曲线及其上的加法

实数域子域上的椭圆曲线

利用有限域上椭圆曲线加法群的加密算法

换一个玩法

10曲线上的加法群

有限域上的10曲线

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

理科生的果壳

有意思的文章