一類退化三次曲線及其在離散域的應(yīng)用

模p整數(shù)域中橢圓曲線上的加法群

我們通常使用的橢圓曲線加密算法疲恢，都是建立在模p整數(shù)域 $\mathrm{F}_p$ 中橢圓曲線上的加法群上的，其主要使用的特點辆亏，是這個加法群中計算 $P = n G, G \in \mathrm{F}_p \land n \in N$ 是相對很簡單的蛾狗，但如果知道P和G要反過來求n則非常困難。它是循環(huán)群上離散對數(shù)問題（應(yīng)用它的加密算法是ElGamal加密算法）在橢圓曲線加法群上的推廣座菠。

我們這里就來簡要介紹一下這個群是什么樣的狸眼。

橢圓曲線及其上的加法

橢圓曲線是形如下式的曲線：

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

其中為了避免奇點，我們要求 $4 a^3 + 27 b^2 \neq 0$ 浴滴。

下面就是一個橢圓曲線的示例：

橢圓曲線

接下來拓萌，我們過曲線上兩點來做一條直線，顯然由于橢圓曲線是三次曲線而直線是一次升略，最后交點方程是一個三次方程微王，它有三個解屡限，其中兩個是我們已知的兩點，而第三個解就是直線與橢圓曲線相交的第三點炕倘。也即钧大，任意一條直線最多與橢圓曲線相交與三點，我們將其記為A激才、B拓型、C。

接著瘸恼，我們定義上述三個交點滿足橢圓曲線上的加法： $A + B + C = 0$ 劣挫。

注意，這里的加法并不是通常意義上我們在實數(shù)域上所定義的加法东帅，而是橢圓曲線上的加法压固，只不過依然用“+”這個符號來表示而已。

由于直線與橢圓曲線相交最多只有三個交點靠闭，最少可以沒有交點帐我，所以我們?yōu)闄E圓曲線補上無窮遠點，這樣如果發(fā)現(xiàn)在通常的無限大平面上直線與橢圓曲線的交點不足三個愧膀，那我們可以說還有一到三個交點在無窮遠處拦键，即都是無窮遠點。

這樣的橢圓曲線稱為“射影橢圓曲線”檩淋，但我們一般直接稱它為橢圓曲線就足夠了芬为，只是大家要記住這里要補上了一個無窮遠點师坎。

因此飒泻，我們現(xiàn)在可以說：任何一條直線與橢圓曲線的交點都有三個。

實際上我們可以說必然有四個侯嘀，因為等式右邊的0也可以視為無窮遠點日戈，而實際上無窮遠點并不是真的只是一個點询张，直線的兩端都會在無窮遠點上和橢圓曲線“相交”。

而加法運算也就可以通過直線與橢圓曲線的交點來給出浙炼。

比如份氧，如果我們已知橢圓曲線上兩點A和B，過它們的直線與橢圓曲線還會有第三個交點C'鼓拧，那么C'關(guān)于x軸的對稱點C就是A和B在橢圓曲線加法操作下的結(jié)果半火，如下圖：

image

我們下面來手算一下這樣定義的加法的結(jié)果：

$\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}$

上述結(jié)果是在A和B的x坐標不相等時成立的，因此我們還需要補充考慮兩個例外情況季俩。

首先，如果A和B關(guān)于x軸對稱梅掠，那結(jié)果直線與y軸平行酌住，結(jié)果是第三交點為無窮遠點店归，答案就是0（體現(xiàn)在x坐標上就是無窮大）。

而如果A和B是同一個點酪我，那此時直線與橢圓曲線相切消痛，結(jié)果便調(diào)整為：

$\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òu)成群秩伞。

群是滿足如下四條定義的帶二元運算“+”的集合G：

封閉性：如果a和b都是G的元素，那a+b也必須是G的元素欺矫；
單位元：存在單位元e纱新，使 $a+e=e+a=a$ ；
可逆性：必然存在唯一的元素b使 $a+b=b+a=e$ 穆趴；
結(jié)合律： $(a+b)+c=a+(b+c)$

如果還滿足交換律 $a+b=b+a$ 脸爱，那這樣的群就被稱為阿貝爾群。

我們前面在橢圓曲線上定義的加法運算未妹，封閉性簿废、單位元和可逆性是顯然滿足的，甚至交換律也是顯然滿足的络它，關(guān)鍵就是是否滿足結(jié)合律族檬。所以我們下面用一個“巧妙”的方式來證明這點。

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

Cayley-Bacharach定理：射影平面內(nèi)化戳，任意兩條不同的平面三次曲線會相交于9點（相切算兩點）单料，那么如果第三條不同的平面三次曲線經(jīng)過了其中任意8點，則它必然經(jīng)過第九點迂烁。

接著看尼，我們用 $A \circ B$ 表示通過A和B的直線與給定橢圓曲線E相交的第三點，因此就有 $A + B = O \circ (A \circ B)$ 盟步，這里O為無窮遠點藏斩，它還能給出一個很有用的性質(zhì)： $O \circ (O \circ A) = A$ 。

于是却盘，我們可以構(gòu)造這么三條直線：

$\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}$

用這三條直線可以構(gòu)造一個很“奇特”的三次曲線狰域，一條退化三次曲線：

$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$ 线梗。

接下來，我們再構(gòu)造三條直線：

$\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}$

它們一樣可以構(gòu)成一條退化三次曲線 $C_2$ 怠益，它和 $E$ 一樣相較于九個點 $\left< C_2, E \right>$ 仪搔，和 $\left< C_1, E \right>$ 可知有8個點是相同的，差別在于第九個點蜻牢，之前是 $C \circ (A + B)$ 而現(xiàn)在是 $A \circ (C + B)$ 烤咧。

根據(jù)上面提到的Cayley-Bacharach定理，我們可以斷定 $C \circ (A + B) = A \circ (C + B)$ 抢呆。再結(jié)合 $A + B = O \circ (A \circ B)$ 與 $O \circ (O \circ A) = A$ 煮嫌，就可以得到我們所要的結(jié)合律（別忘了橢圓曲線上的加分滿足交換律）： $(A + B) + C = A + (B + C)$ 。

那如果A镀娶、B立膛、C中有點相同怎么辦？別忘了Cayley-Bacharach定理中切點算兩個點梯码，所以一樣可以用宝泵。

至此，我們就證明了上面所定義的橢圓曲線上的加分可以構(gòu)成群轩娶。

附帶一提儿奶，除了很少的幾個例外，幾乎所有平面三次曲線都可以通過坐標變換變成橢圓曲線鳄抒。其中有幾類很有趣的特例：三條直線（一次曲線）的并（也就是我們上面構(gòu)造的兩條退化曲線）闯捎，以及，一條圓錐曲線與一條直線的并许溅，都被歸類為“退化橢圓曲線”瓤鼻。

實數(shù)域子域上的橢圓曲線

從前面關(guān)于橢圓曲線的定義可以看出，雖然我們將其定義在實數(shù)域的射影平面上贤重，但實際上可以定義在各類域上茬祷，比如最常見的復數(shù)域。

我們可以先看有理數(shù)域上的橢圓曲線并蝗，即只考慮一條橢圓曲線上的所有有理點（x和y都是有理數(shù)）祭犯，按照之前得到的結(jié)果，其加法結(jié)果為：

$\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的參數(shù)a和b也都是有理數(shù)，那A+B也必然是有理點键畴。

Mordell-Weil定理告訴我們：有理數(shù)域上的任意（非退化）橢圓曲線加法群都是有限生成阿貝爾群： $E(\mathbb{Q}) = \mathbb{Z}^r \oplus T$ 最盅，r被稱為E的秩，T是E的撓點集。

也就是說檩禾，我們只需要有限個有理點挂签，然后通過橢圓曲線加法就可以找出它的所有有理點——當然疤祭，要找到所有這些基點（用來生成其它有理點的初始有理點）本身是非常困難的盼产，但我們至少知道它數(shù)量有限。

我們可以將數(shù)域做進一步限制：如果是整數(shù)域呢勺馆？

Siegel定理告訴我們：任意（非退化）橢圓曲線的整點戏售，或者x與y之一為整數(shù)的點，只有有限多個草穆。

如果我們再將數(shù)域進一步壓縮灌灾，壓縮到有限域，那就有另一個定理了——

Hasse定理：有q個元素的有限域上任意（非退化）橢圓曲線的點的數(shù)量N滿足 $|N - (q + 1)| \leq 2 \sqrt{q}$ 悲柱。

在橢圓曲線密碼學中锋喜，我們所使用的就是一類特定的有限域： $\mathbb{F}_p$ ，即整數(shù)模p域豌鸡，p是一個素數(shù)嘿般。

所謂整數(shù)模p域，其實很好理解涯冠，就是只考慮從0到p-1這p個整數(shù)所構(gòu)成的域炉奴。對于橢圓曲線而言，就是將其做模運算：

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

我們一般可以將左側(cè)的(mod p)省略蛇更。

我們可以先考慮實數(shù)模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坐標都是整數(shù)的點）的分布派任，所以我們下面來看同一條橢圓曲線在不同模下的整點分布情況：

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

同樣的砸逊，現(xiàn)在連接曲線上兩點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)$

接著，我們依然使用和實數(shù)域上橢圓曲線相同的方式來定義 $\mathbb{F}_p$ 上的橢圓曲線的加法掌逛，從而會發(fā)現(xiàn)其實結(jié)果在形式上是一樣的师逸，只需要加上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}$

這里需要注意的是除法。在實數(shù)模p域中颤诀，其結(jié)果是非唯一的字旭， $\frac{1}{x}$ 、 $\frac{1 + p}{x}$ 崖叫、 $\frac{1 + n p}{x}$ 都可以是x的逆遗淳。在整數(shù)模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) 上整點的加法

這個是不是看上去很“過分”种呐？

整數(shù)模p域中橢圓曲線有一個很有趣的性質(zhì)，那就是對每個點P弃甥，都存在一個自然數(shù)n爽室，使得 $nP=0$ ，我們將這個n稱為點P的階（滿足這個條件的自然數(shù)n可以無限多淆攻，我們?nèi)∽钚〉哪莻€）阔墩。另一方面，現(xiàn)在這條橢圓曲線上總共有多少點N瓶珊，被稱為這條橢圓曲線的階啸箫。根據(jù)Lagrange定理有： $N = \prod_P n(P)$ 。

下面才到最有趣的部分：假定我們知道了 $G = n P$ 中的P和G伞芹，是否可以反推出自然數(shù)n忘苛？

推當然是可以推的，但這個計算幾乎沒有任何捷徑可走唱较，只能不斷暴力求解（當然扎唾，諸如“Baby step, Big step”和“Pollard rho”算法可以將求解次數(shù)做一個降低，但本質(zhì)上也算是暴力求解了）绊汹。

這就是著名的“離散對數(shù)難題”稽屏。

之所以說是離散“對數(shù)”而不是離散“除數(shù)”，是因為它形式上與循環(huán)群上的ElGamal算法中的對數(shù)很像西乖，所以習慣上沿用了ElGamal算法中的“離散對數(shù)”的稱呼狐榔。

ElGamal算法中，我們從q階循環(huán)圈Q中選擇一個群元P获雕，然后再從1到q-1中選擇一個自然數(shù)n薄腻，計算 $G = P^n$ 。現(xiàn)在如果你知道了P和G届案，要反推n庵楷，那將非常困難。

利用有限域上橢圓曲線加法群的加密算法

假定楣颠，端點星要將一個數(shù)據(jù)M傳遞給索拉里星尽纽，但川陀會進行攔截，那它應(yīng)該怎么辦童漩？

如果使用RSA加密算法弄贿，一個簡單流程是這樣的：

索拉里星找到兩個大素數(shù)p和q，并計算 $N=pq$ 及 $r=(p-1)(q-1)$
選小于r且與r互質(zhì)的自然數(shù)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，但這是非常困難的一件事谊娇。這個求解被稱為“素數(shù)分解問題”肺孤。

如果使用ElGamal算法，那過程是這樣的：

索拉里星人選擇一個q階循環(huán)群Q邮绿，Q的一個元素P渠旁，1到q-1的一個自然數(shù)n，并計算 $G=P^n$ 船逮，將 $(Q,P,G)$ 作為公鑰全宇宙廣播
端點星人在1到q-1中隨機選擇一個自然數(shù)m，并計算 $C_1=P^m$ 和 $C_2=M G^m$ 粤铭，這里M已經(jīng)被編碼為Q中元素挖胃，編碼方式公開透明，接著端點星人廣播 $(C_1,C_2)$
索拉里星人計算 $M=C_2 \left( C_1^n \right)^{-1}$

整個過程中梆惯，川陀人如果想要破譯酱鸭，就必須求解 $G=P^n$ ，這個“循環(huán)群上的離散對數(shù)問題”一樣非常困難垛吗。

最后凹髓，如果使用橢圓曲線加密算法，那過程和ElGamal算法的過程非常類似：

索拉里星人選擇一條橢圓曲線 $(a,b)$ 與有限域的模參數(shù)q怯屉，并尋找曲線上的一個整點P蔚舀，確保P的階l足夠大，選擇不大于l的自然數(shù)n锨络，計算 $G=nP$ 赌躺，將 $(a,b,q,P,G)$ 作為公鑰全宇宙廣播
端點星人隨機選擇不大于l的自然數(shù)m，計算 $C_1=mP$ 和 $C_2=M+mG$ 羡儿，這里M已經(jīng)被編碼為橢圓曲線上整點礼患，編碼方式公開透明，接著端點星人廣播 $(C_1,C_2)$
索拉里星人計算 $M=C_2-nC_1$

是不是發(fā)現(xiàn)橢圓曲線加密算法和ElGamal算法幾乎一樣掠归？事實上由于整數(shù)模p域上整點的階有限缅叠，所以它實際上也構(gòu)成了一個循環(huán)群，因此和ElGamal算法一樣都是循環(huán)群上的離散對數(shù)問題虏冻，只不過橢圓曲線上的加法比ElGamal算法選用的循環(huán)乘法計算起來更復雜一點而已肤粱。

事實上，密碼學家早就發(fā)現(xiàn)ElGamal算法與RSA算法具有相似的數(shù)學結(jié)構(gòu)兄旬，都可以用量子計算機上的經(jīng)典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給出了具體的算法祝蝠，所以兩者工作雖然看上去很接近，但到底還是不一樣的幻碱。

換一個玩法

上面我們介紹了傳統(tǒng)有限域上橢圓曲線上加法群即用于加密的一些情況绎狭，但這不是我們這篇文章的重點。

我們希望討論這么一個問題：如果換一種曲線褥傍，會怎么樣儡嘶？

而且，實際上我們最后在ECC中所用到的性質(zhì)恍风，實際上總結(jié)下來就一句：整點P在特定加法定義下可以構(gòu)成循環(huán)群蹦狂。

事實上，由于要做加法的話需要三個點朋贬，所以是不是只要一組曲線與一條直線有三個交點凯楔，就可以構(gòu)造這樣的加法操作呢？而且三條直線的并本身就是一種退化了的橢圓曲線嘛锦募，它顯然可以構(gòu)造這種與一條直線有三個交點的情況摆屯。

10曲線上的加法群

我們將一根直線并上一個橢圓的形式，稱為“10曲線”糠亩。

我們先從最簡單的正圓開始：

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

這樣的三次曲線當然可以通過恰當?shù)摹白鴺俗儞Q”變成一條橢圓曲線：
$\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其實已經(jīng)是虛數(shù)了削解，因此在實空間它無法正確表達直線左側(cè)的圓部分的情況。而直線部分在坐標變換后完全退化到了 $\left( \frac{2L}{3}, 0 \right)$ 這一個點上氛驮，顯然也不是什么好性質(zhì)矫废。因此，10曲線這樣的三次曲線被稱為是一種退化橢圓曲線唉铜，而10曲線上也會有一些正常橢圓曲線上所沒有的性質(zhì)桃序。

下面滔金，我們確保 $L^2 > R^2$ ，這樣的曲線就不存在自相交點节仿。接著确封，我們采取和橢圓曲線上加法一樣的操作方式键袱，過這條10曲線上兩點做直線讼撒，該直線必與這條10曲線相交于第三點：如果前兩點都在圓上浑厚，除非垂直于x軸，否則必與一旁的直線有交點根盒；而如果垂直于x軸钳幅，那可以認為與直線相交于無窮遠點O；如果一點在圓上一點在直線上炎滞，那要么圓上點正好是切點敢艰，要么必與圓有第二個交點。比較麻煩的是直線上兩點厂榛，這個我們暫不考慮盖矫。

從而，這樣的直線與10曲線的三個交點A击奶、B、C就滿足加法關(guān)系 $A+B+C=0$ 责掏。

我們來計算兩個情況下的加法結(jié)果。

第一種情況， $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軸，那不用算了朋魔，結(jié)果就是無窮遠點O。如果A和B重合拓售，那此時結(jié)果變?yōu)椋?/p>

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

而如果點B在直線上而點A在圓上，情況則變?yōu)椋?/p>

$\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}$

通過復雜的計算可以發(fā)現(xiàn)案训，直線上兩點通過這種方式定義的和并不依賴于圓上輔助點A的選擇（這里一開始程序出了個小錯誤，居然還得出了依賴圓上輔助點A的結(jié)論轩触，汗……）。至此榨为，我們終于合理定義出了整個10曲線上的加法蔓腐，而且由于10曲線是退化了的橢圓曲線散罕，所以由Cayley-Bacharach定理可知這個加法在10曲線上的確構(gòu)成加法群。

對于橢圓也會有類似的結(jié)果，事實上對于任意橢圓，我們總可以通過縮放與旋轉(zhuǎn)將其變換為10曲線，所以不會有什么特別的新結(jié)果出來浩蓉。而且，這里的兩個參數(shù)：圓半徑R和直線到圓距離L认轨，也并不是都自由，我們可以將L固定為1衷恭，而R是一個0到1之間的值。

因此10曲線的實際特征自由度，只有1個（即便使用橢圓也是如此）烤芦。

10曲線雖然在很大程度上和普通橢圓曲線很是相近，但也有一些不同遂唧。

比如页滚，如果我們將L與R取為無理數(shù)隧熙，那整條10曲線上將沒有一個有理點沪饺，更不用說整點了件余。而另一方面，如果L取為整數(shù)坟漱，那10曲線上的整點數(shù)顯然為無窮多。這兩個都是傳統(tǒng)橢圓曲線所沒有的特性。

我們下面再主要看一下直線上的點和圓上點P的和栅炒，特別是同一個點P的 $2n+1$ 次自加的情況。

我們假定直線上的點的y值為Y释移，而圓上點則是x軸正向旋轉(zhuǎn) $\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)$

這里岔開一下豆巨。
事實上熊户，利用上面的結(jié)論，我們可以計算直線上兩點利用輔助點來做加法的結(jié)果串塑，實際上并不依賴輔助點的選擇，這一結(jié)論傻昙。當然，證明過程會比較繁瑣贾惦，你可以考慮使用Mathematica绞惦。

另一方面杰刽，我們可以用將x和y坐標換用下面這種形式來表達：

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

因此就有如下關(guān)系：

$\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}$

這個結(jié)果可以推廣到如下形式：

$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勺卢，而如果是后者的話再和直上的點相加一次就可讓新點和原來的點相等。

對于直線上的點也有類似的結(jié)論。

我們?nèi)≈本€上點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}$ 的幅角的余切乘上一個系數(shù) $\sqrt{L^2 - R^2}$ 。

如果該矢量的幅角可以表達為圓周的有理數(shù)倍，那顯然點P的若干次自加后會回到自身，否則P的自加只會不斷填滿整條直線而不循環(huán)烁巫。

同樣的，由于任何直線外點P都可以表達為直線上一點Q和直線外一點C的和亦歉，我們?nèi)為 $\{-R,0\}$ 水由，其特點為 $2C=0$ （之所以選擇這個點的另一個原因呵恢，是將它寫為參數(shù)形式時渗钉，它對應(yīng)的參數(shù)為正負無窮彤恶，即無窮遠點，從而可以和直線上的無窮遠點對應(yīng)）鳄橘，因此P的偶數(shù)次自加就等于Q的同樣次數(shù)的自加声离，P的奇數(shù)次自加則等于Q的n-1次自加再加C，因此如果Q對應(yīng)的復數(shù)的幅角不是圓周的有理數(shù)倍瘫怜，那P就無法在有限次自加后回到自身唤锉，而只能不斷填充以“布滿”整個圓周部分听系。

這樣的映射關(guān)系并不是10曲線所獨有的，在橢圓曲線上也有省艳。
比如棉圈，可以分解為一個閉合圓環(huán)加上一根無限長曲線的橢圓曲線，這樣的映射關(guān)系的存在是顯而易見的呆瞻。而即便是沒有獨立閉合圓環(huán)的橢圓曲線始绍，我們也總可以選擇那唯一一個自己是自己相反點的痒蓬、橢圓曲線與x軸的交點，然后它和橢圓曲線自身有兩個切點，這兩個切點將橢圓曲線分割為三部分，其中中間的部分可以通過完全一樣的映射峭沦，映射到上下兩部分织阳，從而構(gòu)成完全一樣的一一映射。

所以說，10曲線上有可數(shù)無窮個點在自加有限次后會循環(huán)熊咽，但剩余不可數(shù)無窮個點則無法通過自加來回到自身等浊，不斷自加只能使其不斷“填充”并“布滿”整條10曲線纬霞，這個結(jié)論和Mordell-Weil定理也有所差異蜕窿。

比如，當我們?nèi)?img class="math-inline" src="https://math.jianshu.com/math?formula=L%3D10" alt="L=10" mathimg="1">犀呼、 $R=5$ 罪佳，初始點P為 $(4, 3)$ 時岗屏，自加6次（直線上會有三點）后循環(huán)。而如果取初始點P為 $(-4, 3)$ 暇屋，自加10000次后的結(jié)果（沒有循環(huán)）如下圖：

有趣的是我們可以看一下參數(shù)t的分布曲線（y值為自加次數(shù)）：

顯然似袁，存在一些有趣的周期性，我們將其轉(zhuǎn)成次數(shù)-角度圖來看會更明顯：

我們可以取R為無限小，那么此時角度的遞歸關(guān)系將變?yōu)椋?/p>

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

這就可以解釋上面我們所看到的周期性：每一次自加（其實是加2P）都近似等價于在當前轉(zhuǎn)角上加了 $\pi - 2 \arctan \left( \frac{Y}{L} \right)$ 昙衅，所以最后整體效果就等于是在不斷旋轉(zhuǎn)該點扬霜，從而可以呈現(xiàn)出周期性。但在R不是無窮小的實際情況中而涉，每次的轉(zhuǎn)角并不固定著瓶，所以會出現(xiàn)并不是完全一樣的周期性——我們能看到一些短周期和一些長周期，比如下圖（取前100次自加）：

可見婴谱，10曲線雖然是退化了的橢圓曲線蟹但，但兩者的性質(zhì)并不完全一樣，10曲線有很多好玩的東西谭羔。

有限域上的10曲線

雖然我們前面說過決定10曲線特性的參數(shù)只有一個（即 $\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)$

在實數(shù)域上我們總可以通過坐標旋轉(zhuǎn)瘟裸、平移客叉、縮放來將其轉(zhuǎn)換為標準形式，但在在 $\mathbb{F}_p$ 上情況則可能很不一樣话告。

現(xiàn)在兼搏，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$

我們可以看一些參數(shù)下現(xiàn)在的整點分布：

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

可以發(fā)現(xiàn)，雖然在完整的實數(shù)域上它們是同一條10曲線沙郭，但在整數(shù)模p域 $\mathbb{F}_p$ 上卻可以很不一樣佛呻。

讓我們回到非病態(tài)的正常的10曲線Z。

很顯然現(xiàn)在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曲線的階吓著，也即其上所有的點的總數(shù)，其實很容易計算： $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$ 上無法表達無窮大司澎。

當然欺缘，必須要強調(diào)的是：并不是所有參數(shù)組合都能在 $\mathbb{F}_p$ 上構(gòu)成合適的10曲線。

在實數(shù)域挤安，10曲線的直線部分與圓圈部分只要 $L>R$ 就是彼此獨立的浪南、從而也就是合理的。但在 $\mathbb{F}_p$ 上情況將變得不同漱受，現(xiàn)在直線部分依然是一條直線（準確地說是 $x=L$ 而y為0到p-1的整數(shù)的p個點）络凿，但直線外部分并不是一個簡單的圓骡送，從上式可以發(fā)現(xiàn)其實現(xiàn)在是一系列分布在“同心圓”上的整點，從而會從原來的正圓位置向內(nèi)外“擴散”出去絮记。

因此摔踱，就會存在一個很極端的情況：擴散出去的圓上整點，同時恰好落在了直線上怨愤。

當發(fā)生這種情況的時候派敷，我們就認為所選的參數(shù)組合是“病態(tài)”的，它會使得現(xiàn)在10曲線上的加法的定義遇到障礙撰洗。

病態(tài)的10曲線還有很多篮愉。比如某些參數(shù)組合下（比如取L=13、R=5差导、P_x=1试躏、P_y=3、p=103）可能會出現(xiàn)兩個直線外點的連線與其中至少一個點相切這么一種詭異的情況（此時等于一根直線與10曲線相交于4點）设褐，這樣的10曲線顯然也是病態(tài)的颠蕴。

所以，我們必須考慮選擇恰當?shù)膮?shù)助析，使得10曲線的行為不病態(tài)犀被。

$\mathbb{F}_p$ 中10曲線上的加法的定義，形式上與實數(shù)域上的情況完全相同外冀，只不過要注意除法需要用取模來做寡键。此時直線外兩點的和必然落在直線上，而直線外一點與直線上一點的和必然在直線外雪隧，直線上兩點可以通過直線外的輔助點來構(gòu)造且結(jié)果不依賴于輔助點的選擇西轩，這些結(jié)論都和實數(shù)域上10曲線的加法相同，且一樣可以構(gòu)成加法群膀跌。

但當參數(shù)選擇是“病態(tài)”的時候，我們在那些導致病態(tài)的點上將無法定義合適的加法固灵，這也是我們不選用病態(tài)10曲線的重要原因捅伤。

我們可以仿造 $\mathbb{F}_p$ 上橢圓曲線的做法來定義10曲線上每個點P的“階” $l(P)$ 為能使 $n P = 0$ 成立的最小自然數(shù)n。記 $C(P)=\left\{ nP | n \in [1, l(P)) \right\}$ 巫玻，因此如果 $C(P_2) \subseteq C(P_1)$ 丛忆，那我們就說 $P_2$ 可由 $P_1$ 生成。通過這種方式我們可以將10曲線的所有點都劃分為若干組仍秤，每一組都可以由一個元素通過有限次自加來遍歷熄诡。我們將能生成組中所有元素的數(shù)稱為“生成元”。

換一個角度來看诗力，我們可以稱無窮遠點為零點凰浮，因為這是定義。然后，將兩倍為零的點稱為“半零點”袜茧，這樣的點有三個： $\{R, 0\}$ 菜拓、 $\{p - R, 0\}$ 、 $\{L, 0\}$ 笛厦。

接著纳鼎，如果一個點P可以表達為點Q的自加，即 $P = 2 Q$ 裳凸，則稱Q是P的半點而P是Q的倍點贱鄙。那，由于半零點有三個姨谷，我們很容易就可以得到結(jié)論：P的半點數(shù)是4的倍數(shù)逗宁，且一半在直線上，一半在直線外菠秒，且它們四個一組可以通過半零點相互轉(zhuǎn)換疙剑。

當然，另一個更加直接的結(jié)論是：直線外點沒有半點践叠，而直線上點有的有半點有的沒有言缤。

n倍點的問題其實可以在上述由生成元生成的循環(huán)組中來考慮。

假定點P屬于組 $C(Q)$ 禁灼，生成元為Q管挟，從而有 $P = n Q$ ，那么P的x倍就是 $\mathrm{mod}(n x, l(Q)) P$ 弄捕。所以一個點是否有x分之一點就取決于是否存在整數(shù)m使下式成立：

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

這樣我們不用做具體的計算就能判斷一個點是否存在n分之一點僻孝，以及有幾個n分之一點。

直線上的n倍點守谓，利用實數(shù)域上的結(jié)論可以寫為：

$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，因此不難發(fā)現(xiàn) $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$

這里第二部分不用寫取模的理由倒也是很簡單：它的結(jié)果要么是0要么是1送矩，沒有取模的必要。

這種定義的好處哪替，便是它天然具備乘法環(huán)的所有要素栋荸，但缺點就是我們?nèi)绻鲇嬎悖鞘紫纫鉀Q如何用生成元的倍點來表達指定點這一離散對數(shù)問題凭舶，難度頗高晌块。當然，從形式上說這樣的定義一點問題都沒有帅霜。

同樣的匆背，這個定義也可以用在 $\mathbb{F}_p$ 的至少部分橢圓曲線上，因為前面已經(jīng)提過身冀，只要橢圓曲線包含一個y值為0的點钝尸，那么我們總可以通過橢圓曲線加法將整條橢圓曲線分割為彼此一一對應(yīng)的兩部分（如果橢圓曲線可以分解為一個閉環(huán)加一條曲線，則這種分割很顯然搂根；如果是一條完整的曲線珍促，前面也介紹過，可以分解為兩個切點之間的部分與兩個切點之外的部分）剩愧，從而可以寫為 $n E_0 + d E_1$ 的形式猪叙。

容易證明，這樣定義的乘法結(jié)合之前定義的加法仁卷，可以在 $\mathbb{F}_p$ 上的10曲線和橢圓曲線上構(gòu)成一個交換除環(huán)穴翩，即一個域。且這個域有一個子域锦积，它是10曲線的直線部分芒帕，也是橢圓曲線的非閉合曲線或非中段曲線部分，因此整個10曲線與橢圓曲線作為一個域丰介，是直線域（橢圓曲線就是非閉合曲線域或非中段曲線域）的單擴張域背蟆， $\{-R,0\}$ （橢圓曲線就是前面提到的那個與x軸的交點）就是該擴張的本原元。

和橢圓曲線可以用倍點分解很困難這個特性來構(gòu)造ECC一樣基矮，10曲線也可以利用倍點分解很困難這個特性來構(gòu)造加密算法淆储，我們可以將之稱為OZCC冠场。OZCC和ECC其實都用到了域上的乘法家浇，但其保密安全性來源于倍點分解而不是乘積分解的難度。因此ECC和OZCC本質(zhì)上和ElGamal算法是相同的碴裙，都是模冪難題钢悲，只不過用加法來自然構(gòu)造出了完整的循環(huán)群而已点额。

如果要進一步拓展10曲線，我們可以將 $R^2$ 用一個整數(shù) $R$ 來取代莺琳，這樣 $\mathbb{F}_p$ 上的點分布還能有更多的變化（比如此時直線外部分很可能沒有y值為0的點还棱，從而上面那種直線內(nèi)外一一對應(yīng)的做法將不再適用），也可以用雙曲線提到圓而將直線放在y軸上從而構(gòu)造“川”形曲線惭等，也能得到很多相近但又不完全相同的性質(zhì)珍手，也可以構(gòu)建域。

我們可以發(fā)現(xiàn)辞做，10曲線雖然是退化的三次曲線琳要，很多性質(zhì)相對橢圓曲線有了不少的簡化，但在其上構(gòu)建加法群甚至一個域的方法和橢圓曲線是相同的忽刽，我們也可以拿來做很多有趣的事介却。

至少蛇耀，用來造一個循環(huán)群然后仿ElGamal或ECC的方法來構(gòu)造一個加密算法，問題不是很大课幕。

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者

人面猴
序言：七十年代末，一起剝皮案震驚了整個濱河市五垮，隨后出現(xiàn)的幾起案子乍惊，更是在濱河造成了極大的恐慌，老刑警劉巖拼余，帶你破解...
沈念sama閱讀 218,682評論 6贊 507
死咒
序言：濱河連續(xù)發(fā)生了三起死亡事件污桦，死亡現(xiàn)場離奇詭異，居然都是意外死亡匙监，警方通過查閱死者的電腦和手機凡橱，發(fā)現(xiàn)死者居然都...
沈念sama閱讀 93,277評論 3贊 395
救了他兩次的神仙讓他今天三更去死
文/潘曉璐我一進店門，熙熙樓的掌柜王于貴愁眉苦臉地迎上來亭姥，“玉大人稼钩，你說我怎么就攤上這事〈锫蓿” “怎么了坝撑？”我有些...
開封第一講書人閱讀 165,083評論 0贊 355
道士緝兇錄：失蹤的賣姜人
文/不壞的土叔我叫張陵，是天一觀的道長粮揉。經(jīng)常有香客問我巡李，道長，這世上最難降的妖魔是什么扶认？我笑而不...
開封第一講書人閱讀 58,763評論 1贊 295
?港島之戀（遺憾婚禮）
正文為了忘掉前任侨拦，我火速辦了婚禮，結(jié)果婚禮上辐宾，老公的妹妹穿的比我還像新娘狱从。我一直安慰自己膨蛮，他們只是感情好，可當我...
茶點故事閱讀 67,785評論 6贊 392
惡毒庶女頂嫁案：這布局不是一般人想出來的
文/花漫我一把揭開白布季研。她就那樣靜靜地躺著敞葛，像睡著了一般。火紅的嫁衣襯著肌膚如雪与涡。梳的紋絲不亂的頭發(fā)上惹谐，一...
開封第一講書人閱讀 51,624評論 1贊 305
城市分裂傳說
那天，我揣著相機與錄音驼卖，去河邊找鬼豺鼻。笑死，一個胖子當著我的面吹牛款慨，可吹牛的內(nèi)容都是我干的儒飒。我是一名探鬼主播，決...
沈念sama閱讀 40,358評論 3贊 418
雙鴛鴦連環(huán)套：你想象不到人心有多黑
文/蒼蘭香墨我猛地睜開眼檩奠，長吁一口氣：“原來是場噩夢啊……” “哼桩了！你這毒婦竟也來了？” 一聲冷哼從身側(cè)響起埠戳，我...
開封第一講書人閱讀 39,261評論 0贊 276
萬榮殺人案實錄
序言：老撾萬榮一對情侶失蹤井誉，失蹤者是張志新（化名）和其女友劉穎，沒想到半個月后整胃，有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體颗圣，經(jīng)...
沈念sama閱讀 45,722評論 1贊 315
?護林員之死
正文獨居荒郊野嶺守林人離奇死亡，尸身上長有42處帶血的膿包…… 初始之章·張勛以下內(nèi)容為張勛視角年9月15日...
茶點故事閱讀 37,900評論 3贊 336
?白月光啟示錄
正文我和宋清朗相戀三年屁使，在試婚紗的時候發(fā)現(xiàn)自己被綠了在岂。大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
茶點故事閱讀 40,030評論 1贊 350
活死人
序言：一個原本活蹦亂跳的男人離奇死亡蛮寂，死狀恐怖蔽午，靈堂內(nèi)的尸體忽然破棺而出，到底是詐尸還是另有隱情酬蹋，我是刑警寧澤及老，帶...
沈念sama閱讀 35,737評論 5贊 346
?日本核電站爆炸內(nèi)幕
正文年R本政府宣布，位于F島的核電站范抓，受9級特大地震影響骄恶，放射性物質(zhì)發(fā)生泄漏。R本人自食惡果不足惜匕垫，卻給世界環(huán)境...
茶點故事閱讀 41,360評論 3贊 330
男人毒藥：我在死后第九天來索命
文/蒙蒙一僧鲁、第九天我趴在偏房一處隱蔽的房頂上張望。院中可真熱鬧，春花似錦悔捶、人聲如沸。這莊子的主人今日做“春日...
開封第一講書人閱讀 31,941評論 0贊 22
一樁弒父案蜕该，背后竟有這般陰謀
文/蒼蘭香墨我抬頭看了看天上的太陽。三九已至洲鸠，卻和暖如春堂淡，著一層夾襖步出監(jiān)牢的瞬間，已是汗流浹背扒腕。一陣腳步聲響...
開封第一講書人閱讀 33,057評論 1贊 270
情欲美人皮
我被黑心中介騙來泰國打工绢淀，沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留，地道東北人瘾腰。一個月前我還...
沈念sama閱讀 48,237評論 3贊 371
代替公主和親
正文我出身青樓皆的，卻偏偏與公主長得像，于是被迫代替她去往敵國和親蹋盆。傳聞我的和親對象是個殘疾皇子费薄，可洞房花燭夜當晚...
茶點故事閱讀 44,976評論 2贊 355