ECC Megamix



目录：



  1. 前言

本文旨在以笔者的角度，对椭圆曲线的相关内容进行一些基本的总结。

本文会省略一些内容，默认是显然的并时常以“众所周知”一笔带过以节省篇幅。比如本文不会探讨同源映射的可分性、度与对偶，本文也不会探讨二次域理想类群与二次型的关系。

本文的章节之间不一定存在严格的逻辑顺序。

本文会先做一堆铺垫，然后给出下面这个东西的解。


含4p-1型质因子的大整数分解问题（简称“4p-1问题”）[1][2]：已知整数\(N\)由两个pbits比特位的质因子\(p,q\)组成（\(N=pq\)），其中

\[ \require{HTML} \newcommand{\rotateninety}[1]{\style{display: inline-block; transform: rotate(90deg)}{#1}} \newcommand{\ZZ}{\mathbb{Z}} \newcommand{\RR}{\mathbb{R}} \newcommand{\CC}{\mathbb{C}} \newcommand{\HH}{\mathbb{H}} \newcommand{\QQ}{\mathbb{Q}} \newcommand{\abs}[1]{\left\vert #1 \right\vert} \newcommand{\End}{\text{End}} \newcommand{\tens}[1]{\otimes_{#1}} \newcommand{\SL}{\text{SL}} \newcommand{\GL}{\text{GL}} \newcommand{\iso}{\mathop{\longrightarrow}\limits^{\sim}} \newcommand{\Tr}{\operatorname{T}} \newcommand{\Nm}{\operatorname{N}} \newcommand{\deg}{\operatorname{deg}} \newcommand{\gcd}{\mathop{\text{gcd}}} \newcommand{\lcm}{\mathop{\text{lcm}}} \newcommand{\Aut}{\text{Aut}} \newcommand{\diag}{\text{diag}} \newcommand{\ker}{\operatorname{ker}} \newcommand{\coker}{\operatorname{coker}} \newcommand{\PGL}{\text{PGL}} \newcommand{\OO}{\mathcal{O}} \newcommand{\cl}{\text{cl}} \newcommand{\FF}{\mathbb{F}} \newcommand{\disc}{\operatorname{disc}} \newcommand{\Gal}{\text{Gal}} \newcommand{\Im}{\operatorname{Im}} \newcommand{\Re}{\operatorname{Re}} p = \frac{t^2-v^2D}{4},\quad D,v,t\in\ZZ,\quad D < 0,\quad D\equiv 5\pmod{8}, \quad t = 1 \]

求\(p,q\)。


在量子计算机发明出来之后这个问题就变得平凡了——它与一般的大整数分解问题在Shor算法下基本无异。而在此之前，如果能够相对高效地解决上述问题的话，我们的RSA就又多出了一类不安全的模数——虽然寻找某类特殊的大整数分解方法并非本文的出发点。


  1. Complex multiplication for babies

众所周知，作为一个复环面，格点\(\CC/\Lambda\)与椭圆曲线\(E/\CC\)的点群同构[Appendix A]，\(E/\CC\)上的自同态对应在\(\CC/\Lambda\)上是形如

\[ f(z+\Lambda)=\alpha z+\Lambda,\quad z\in \CC,\quad \alpha \in \HH=\{x+iy:x,y\in\RR,y>0\},\quad \alpha \Lambda\subseteq \Lambda \]

的全纯映射。一般来说，每个\(\alpha \in\ZZ\)都可以对应一个自同态，而如果存在满足\(\alpha \Lambda\subseteq\Lambda\)的\(\alpha \in\CC - \RR\)，那么称该\(\CC/\Lambda\)对应的\(E/\CC\)具有复数乘法（complex multiplication），这个\(\alpha\)则被称为复乘点（CM point）。

不妨设\(\Lambda = \ZZ + \ZZ\tau\)，那么\( \alpha,\alpha^2 \in \Lambda \)，\(\alpha^2\)可以表示为\(1,\alpha\)的有理系数线性组合，即\(\alpha\)是\(\ZZ\)上的二次代数数。

\(E/\CC\)的自同态代数与有理数域或者某个虚二次域\(K\)是同构的，\(E/\CC\)的自同态环与整数环或者某个虚二次域的某个序\(\mathcal{O}\)是同构的。

\[ \QQ \tens{\ZZ} \End(E) =: \End^0 (E) \cong \QQ \text{ or } K \] \[ \End(E) \cong \ZZ \text{ or } \mathcal{O} \]

事实上，我们有，

定理1-1：对于域\(k\)上的椭圆曲线\(E/k\)而言，\(\End^0 (E)\)与以下三者之一同构

  1. 有理数域 \( \QQ \)
  2. 虚二次域 \( \QQ(\alpha),\quad \alpha^2 < 0 \)
  3. 四元数代数 \( \QQ(\alpha,\beta),\quad \alpha^2,\beta^2 < 0, \quad \alpha\beta=-\beta\alpha \)

证明见附录C[Appendix C]。对于复数域上的\(E/\CC\)，由于\(E/\CC\)上的自同态一定交换，故定理1-1的第三种情况是不可能出现的。


对于有限域上的椭圆曲线\(E\)而言，自同态代数在代数闭域上表现为第三种情况当且仅当\(E\)超奇异（supersingular）（不证）。有如下两个典型的例子。


例1-1：\(p\equiv 3\pmod{4},\ p > 3\)，\(j(E/\FF_p)=1728\)。取\(E: y^2 = x^3 + x\)，那么\(\left(\frac{-1}{p}\right)=-1\)，于是下述的自同态不在\(\ZZ\)中。

\[ \phi: (x, y) \mapsto (-x, iy),\quad i^2 + 1 = 0,\ i\notin\FF_p \]

其满足\(\phi^2 + 1 = 0\)，算上\(E\)的Frobenius自同态\(\pi\)，\(\End^0(E)\)必然与某个四元数代数同构，于是\(E\)超奇异，\(\pi^2 + p = 0\)。由于\(i\notin \FF_p\)，故\(\pi\)不固定\(i\)（更精确地，\(i^p = -i\)），于是\(\pi\)与\(\phi\)不交换。

\[ \End^0(E) \cong \QQ(\phi, \pi),\quad \phi^2 = -1,\ \pi^2 = -p,\ \phi\pi = -\pi\phi \]

例1-2：\(p\equiv 2\pmod{3},\ p > 3\)，\(j(E/\FF_p)=0\)。取\(E: y^2 = x^3 + 1\)，那么\(\left(\frac{-3}{p}\right)=(-1)^{\frac{p-1}{2}\cdot \frac{3-1}{2}}\left(\frac{3}{p}\right)=\left(\frac{p}{3}\right)=\left(\frac{2}{3}\right)=-1\)，于是下述的自同态不在\(\ZZ\)中。

\[ \phi: (x, y) \mapsto (\rho x, y),\quad \rho^2 + \rho + 1 = 0,\ \rho\notin\FF_p \]

其满足\(\phi^2 + \phi + 1 = 0\)，算上\(E\)的Frobenius自同态\(\pi\)，\(\End^0(E)\)必然与某个四元数代数同构，于是\(E\)超奇异，\(\pi^2 + p = 0\)。由于\(\rho\notin \FF_p\)，故\(\pi\)不固定\(\rho\)（更精确地，\(\rho^p = -\rho - 1\)），于是\(\pi\)与\(\phi\)不交换。

\[ \End^0(E) \cong \QQ(\phi, \pi) \]
  1. j-function & its q-expansion

由\(\Lambda\)的Weierstrass方程

\[ (\wp')^2 = 4 \wp^3 - g_2 \wp - g_3, \qquad \Delta(\Lambda) = g_2^3 - 27g_3^2 \] \[ \wp = \wp(z;\Lambda) = \frac{1}{z^2} + \sum\limits_{\omega\in\Lambda-\{0\}} \left[ \frac{1}{(z-\omega)^2} - \frac{1}{\omega^2} \right] \]

我们可以得到一个零阶齐次的函数——j不变量

\[ j(\Lambda) = 12^3 J(\Lambda) = \frac{1728 g_2^3}{\Delta}, \qquad j(\tau) := j(\Lambda(\omega_1,\omega_2)), \quad \omega_1/\omega_2=\tau\in\HH \] \[ j(\gamma\tau) = j(\tau),\qquad \forall \tau\in\HH,\ \gamma\in\Gamma:=\SL_2(\ZZ) \]

类似地，与之相关联的椭圆曲线\(E:y^2=4x^3-g_2x-g_3\)（\(x=\wp(z),\ y=\wp'(z)\)）的j不变量为

\[ j_E = j(E) = \frac{1728 g_2^3}{\Delta} = \frac{1728 g_2^3}{g_2^3 - 27g_3^2} \]

根据[Appendix B]中的价公式，

\(G_4,G_6,\Delta\)在\(\HH\)中除了上述位置外的其余地方没有极点与零点。因此

\[ v_\rho(J) = 3,\ v_\infty(J) = -1,\ v_i(J-1) = 2 \]

\(J\)在\(\HH\)的其余地方没有极点与零点。进一步地，对于\(\forall c\in\CC-\{0,1\}\)，\(J(z),J(z)-c\)有一个一阶极点，因此\(J(z)-c\)一定有一个一阶零点\(z_c\)，显然每个\(z_c\)对于每个\(c\)而言是一一对应的。我们有双射

\[ j: \Gamma\backslash\HH \iso \CC \]

现在，对于两条椭圆曲线\(E/\CC,\ E'/\CC\)及其对应的\(\Lambda=[\omega_1,\omega_2],\ \Lambda'=[\omega_1',\omega_2']\)而言，

\[ j(E) = j(E') \iff j(\Lambda) = j(\Lambda') \iff \omega_1/\omega_2=\pm \omega_1'/\omega_2' \iff \exists c\in\CC^*,\ c\Lambda = \Lambda' \iff E \cong E' \]

此时，\(\exists c\in \CC^*\)，

\[ g_2(\Lambda')=g_2(c\Lambda)=c^{-4}g_2(\Lambda),\quad g_3(\Lambda')=g_3(c\Lambda)=c^{-6}g_3(\Lambda) \] \[ \wp(cz;\Lambda')=c^{-2}\wp(z;\Lambda),\ \wp'(cz;\Lambda')=c^{-3}\wp'(z;\Lambda) \implies (x,y)\mapsto(c^{-2}x,c^{-3}y) \]

对于有限域上的椭圆曲线而言，我们可以类似地定义j不变量，并且可以用代数的方法证明，在有限域的代数闭包中每个j不变量能够在同构的意义下唯一确定一条椭圆曲线。

例2-1：考虑域\(K\)上具有cusp型奇异点的椭圆曲线\(E: y^2 = x^3\)，此时若\(K\)为复数域，则\(\Lambda(E)=\{0\}\)。将\((0,0),\infty\ne P\in E/K\)参数化为\((t^2, t^3),\ t\in \overline{K}\)，则\(P\)的倍乘退化为

\[ k: (t^2, t^3) \mapsto \begin{cases} \left(\left(\frac{t}{k}\right)^2, \left(\frac{t}{k}\right)^3\right), & 0 < \operatorname{char}{K} \nmid k\quad\text{or}\quad 0 = \operatorname{char}{K} \ne k\\ \infty, &\text{otherwise}\\ \end{cases} \]

\(\langle P\rangle \cong \FF_{\operatorname{char}{K}}\text{ or }\ZZ\)，\(\langle P\rangle\)中的离散对数问题退化为整数环或有限域上的乘除法。


众所周知，全纯映射

\[ z\mapsto e^{2\pi i z} =: q_z \]

将开集\(\HH_{\tau} := \{z\in\CC: \Im{z} > \tau\}\)映射到去心开圆盘\(\mathring{B}(0; e^{-2\pi \tau}) := \{z\in\CC: \abs{z} < e^{-2\pi \tau},\ z\ne 0\}\)。而\(T\backslash\HH_{\tau}\)在上述映射下刚好卷绕这个去心开圆盘一次（随着x的变化），其中\(T=\begin{pmatrix}1&1\\0&1\\\end{pmatrix}\)。这表明\(z\mapsto q_z\)诱导出\(T\backslash\HH_{\tau}\)到\(\mathring{B}(0; e^{-2\pi \tau})\)的一个解析同构。

至此，\(\HH_{\tau}\)上周期为1的半纯函数\(f\)在\(\mathring{B}(0; e^{-2\pi \tau})\)上诱导出一个半纯函数\(f^*\)。我们始终可以在去心开圆盘的某个环带中将\(f^*\)展开为Laurent级数（根据\(f\)的半纯性）：

\[ f^*(q) = \sum\limits_{n = -\infty}^{\infty} c_n q^n,\quad f(z) = \sum\limits_{n = -\infty}^{\infty} c_n e^{2\pi i nz} \]

若\(f^*(q)\)在\(q=0\)处半纯，则

\[ f^*(q) = \sum\limits_{n = -N}^{\infty} c_n q^n,\quad f(z) = \sum\limits_{n = -N}^{\infty} c_n e^{2\pi i nz}, \quad N \in \ZZ \]

此时称\(f\)在\(\infty\)处半纯。

接下来我们尝试求解\(j\)函数的q-级数展开。

首先根据Weierstrass分解定理，将整函数\(\sin{\pi z}\)表示为

\[ \sin{\pi z} = \pi z \prod\limits_{n = 1}^{\infty} \left(1-\frac{z}{n}\right)\left(1+\frac{z}{n}\right) \]

两边取对数导数，另外根据Euler公式与幂级数展开得到，对于\(\tau\in\HH\)而言，

\[ \frac{1}{\tau} + \sum\limits_{n=1}^{\infty} \left(\frac{1}{\tau-n} + \frac{1}{\tau+n}\right) = \pi \frac{\cos{\pi\tau}}{\sin{\pi\tau}} = \pi i - 2\pi i\sum\limits_{\nu = 0}^{\infty} q_{\tau}^{\nu} \]

对左右两式反复求导，对比系数可得

\[ (-1)^{k-1} (k-1)! \sum\limits_{n = -\infty}^{\infty} \frac{1}{(\tau - n)^k} = -\sum\limits_{\nu = 1}^{\infty} (2\pi i)^k \nu^{k-1} q_{\tau}^{\nu} \]

据此变形Eisenstein级数：

\[ \begin{aligned} G_k(\tau) &= \sum\limits_{0\ne m,n\in\ZZ}\frac{1}{(m\tau + n)^{2k}}\\ &= 2\zeta(2k) + 2\sum\limits_{m=1}^{\infty} \sum\limits_{n=-\infty}^{\infty}\frac{1}{(m\tau + n)^{2k}}\\ &= 2\zeta(2k) + 2\sum\limits_{m = 1}^{\infty}\sum\limits_{\nu = 1}^{\infty} \frac{(2\pi i)^{2k}\nu^{2k-1}}{(2k-1)!}q_{\tau}^{m\nu}\\ &= 2\zeta(2k) + 2\frac{(2\pi i)^{2k}}{(2k-1)!}\sum\limits_{n=1}^{\infty} \sigma_{2k-1}(n) q_{\tau}^n \end{aligned} \]

其中

\[ \sigma_k(n) := \sum\limits_{0 < d|n} d^k \]

于是，代入我们小学二年级就知道的常数\(\zeta(4) = \frac{\pi^4}{90},\ \zeta(6) = \frac{2\pi ^6}{245}\)算得

\[ g_2 = 60G_2 = (2\pi)^4 \frac{1}{2^2 3}(1+240X) \] \[ g_3 = 140G_3 = (2\pi)^6 \frac{1}{2^3 3^3}(1-504Y) \] \[ \Delta = (2\pi)^{12}\frac{1}{2^6 3^3}[(1+240X)^3 - (1-504Y)^2] \]

其中

\[ X = \sum\limits_{n=1}^{\infty} \sigma_3(n) q_{\tau}^n,\quad Y = \sum\limits_{n=1}^{\infty} \sigma_5(n) q_{\tau}^n \]

注意到模4与模3的意义下\(d^3\equiv d^5,\ d\in\ZZ\)，故\(\sigma_3(n)\equiv\sigma_5(n)\)，故\((1+240X)^3 - (1-504Y)^2\equiv 2^4 3^2(5X+7Y)\equiv 0\pmod{2^6 3^3}\)，于是

\[ \Delta = (2\pi)^{12} \sum\limits_{n=1}^{\infty} d_n q_{\tau}^n,\quad d_n\in\ZZ,\ d_1 = \frac{1}{1728}(240\cdot 3 - (-504)\cdot 2) = 1 \]

最后，设

\[ \begin{aligned} j(\tau) &= 2^6 3^3 \frac{g_2^3}{\Delta}\\ &= \sum\limits_{n=-1}^{\infty} a_n q_{\tau}^{n} \end{aligned} \]

则

\[ \begin{aligned} \left(\sum\limits_{n=0}^{\infty} d_{n+1}q^n\right)\left(\sum\limits_{n=0}^{\infty} a_{n-1}q^n\right) &= \sum\limits_{n=0}^{\infty}\left(\sum\limits_{m=0}^n d_{m+1}a_{n-m-1}\right) q_{\tau}^n\\ &= \left(1+240\sum\limits_{n=1}^{\infty} \sigma_3(n) q_{\tau}^n\right)^3\\ &=: \sum\limits_{n=0}^{\infty} b_n q_{\tau}^n,\quad b_n\in\ZZ \end{aligned} \]

于是

\[ d_{1} a_{-1} = b_0 \implies a_{-1} = 1 \] \[ d_{1} a_{n-1} + d_{2}a_{n-2} + \cdots + d_{n+1}a_{-1} = b_n\implies a_{n-1}\in \ZZ,\quad \forall n\in\ZZ_{+} \]

显式地写出\(j\)函数的q-级数开头几项，

\[ \begin{aligned} j^*(q) &= \frac{1}{q} + 744 + 196884q + 21493760q^2 +\\ &864299970q^3 + 20245856256q^4 + 333202640600q^5 +\\ &4252023300096q^6 + 44656994071935q^7 + 401490886656000q^8 +\\ &3176440229784420q^9 + 22567393309593600q^{10} + 146211911499519294q^{11} +\\ &874313719685775360q^{12} + 4872010111798142520q^{13} +\\ &25497827389410525184q^{14} + \cdots \end{aligned} \]
  1. The modular polynomial

记

\[ \GL_n^+(R)=\{M\in\GL_n(R): \det(M)>0\},\quad \Delta_n=\{M\in\GL_2(\ZZ): \det(M)=n\} \] \[ \Delta_n^*=\left\{\begin{pmatrix}a&b\\c&d\end{pmatrix}\in\Delta_n: \gcd(a,b,c,d)=1\right\}=\left\{M\in\PGL_2(\ZZ):\det(M)=n\right\} \]

设\(j\)为前文所述，则\(j\circ \gamma\alpha=j\circ\alpha,\ \forall\gamma\in\Gamma\)。取\(\Gamma\backslash\Delta_n^*\)中一组形如下式的代表元

\[ \begin{pmatrix}a&b\\0&d\end{pmatrix},\quad ad=n,\quad 0 < a,\ 0\le b < d,\quad \gcd(a,b,d) = 1 \]

令\(\psi(n)=\abs{\Gamma\backslash\Delta_n^*}\)，不难算出[4]

\[ \psi(n) = n\prod\limits_{p\mid n}\left(1+\frac{1}{p}\right) \]

我们希望找到在\(\Gamma\backslash\Delta_n^*\)的置换的意义下\(j(n\tau)\)在\(\ZZ[j(\tau)]\)中的极小多项式，故令

\[ \Phi_n(X)=\prod\limits_{i=1}^{\psi(n)}(X-j\circ \alpha_i), \quad \alpha_i\in \Gamma\backslash\Delta_n^* \]

它满足

定理3-1：

  1. \(\Phi_n(X)\in\ZZ[X,j]\)。
  2. \(\Phi_n(X)\)是\(\CC(j)\)上不可约的\(\psi(n)\)阶多项式。
  3. \(\Phi_n(X,j)=\Phi_n(j,X)\)。
  4. 若\(n\)不为平方数，则\(\Phi_n(j,j)\)次数大于1，且首项系数为\(\pm 1\)。

证明参见附录D[Appendix D]。我们称\(\Phi_n(X)\)为n阶模多项式（modular polynomial of order n）。


我们可以得到一个有用的推论：

推论3-1：若\(\tau\in\HH\)是虚二次代数数，则\(j(\tau)\)是\(\ZZ\)上的代数整数。

证明：令\(K=\QQ(\tau)\)，

\[ \lambda = \begin{cases} 1+i, &K = \QQ(i)\\ \sqrt{-m}, &K = \QQ(\sqrt{-m}),\ m>1\text{ square free} \end{cases} \]

设\(\OO_K=[z,1]\)，则

\[ \lambda\begin{pmatrix} z\\1 \end{pmatrix} = \underbrace{\begin{pmatrix} a & b\\ c & d\\ \end{pmatrix}}_{\alpha} \begin{pmatrix} z\\1 \end{pmatrix} \]

且\(0 < \Nm_{K/\QQ}(\lambda) = \det{\alpha} =: n\)，\(z = \alpha z\)。根据\(\lambda\)的构造这表明\(\alpha\in\Delta_{n}^*\)，且\(n\)没有平方因子，定理3-1的第四条告诉我们\(j(z)\)是代数整数。

\(K = \QQ(\tau)=\QQ(z)\)说明\(\tau = uz + v,\ u,v\in\QQ\)，不妨设\(\tau = \beta z,\ \beta\in\Delta_{n'}^*,\ n'=\det{\beta}\)，根据定理3-1的第一条\(j(\tau) = j(\beta z)\)是\(\ZZ[j(z)]\)上的代数整数，从而根据代数整数的特性知\(j(\tau)\)是\(\ZZ\)上的代数整数。

Q.E.D.


考虑如下的交换图：

\[ \require{AMScd} \begin{CD} \CC/M @>{\lambda}>> \CC/L\\ @VV{\rotateninety{\sim}}V @VV{\rotateninety{\sim}}V \\ B/\CC @>>{\phi}> A/\CC \end{CD} \]

其中\(M\subseteq L\)。设\(L=[\omega_1,\omega_2]\)，那么，

\[ M=[a\omega_1+b\omega_2,c\omega_1+d\omega_2],\quad \alpha=\begin{pmatrix}a&b\\c&d\end{pmatrix}\in \GL_2^+(\ZZ) \]

将\(\alpha\)写成Smith标准形，

\[ \diag\{\lambda_1,\lambda_2\} = \alpha' = \gamma\alpha\gamma',\quad \gamma,\gamma'\in\Gamma,\quad \lambda_1\mid\lambda_2 \] \[ M=[\lambda_1\omega_1,\lambda_2\omega_2] \]

故\(L/M\)是循环加法群当且仅当\(\lambda_1=1\)，也即\(\gcd(a,b,c,d)=1\)。

同态\(\lambda:\CC/M\to\CC/L,\ z+M\mapsto z+L\)的核为\(\ker{\lambda}=L/M\)。据此立即得到，

定理3-2：从\(B/\CC\)到\(A/\CC\)的同源\(\phi\)满足\(\ker{\phi}\)为\(n\)阶循环群当且仅当\(\Phi_n(j_A,j_B)=0\)。

对于非代数闭域上也有类似的结论，不过陪域\(A\)有时需替换为\(A\)的某条孪生曲线。


我们尝试计算\(\Phi_2(X, j)\)的表达式，首先显式地写出

\[ \Phi_2(X, j(\tau)) = \left(X - j\left(2\tau\right)\right)\left(X - j\left(\frac{\tau}{2}\right)\right)\left(X - j\left(\frac{\tau+1}{2}\right)\right) \]

根据j函数的q-级数展开式与附录D[Appendix D]的引理D-1，我们计算出

\[ \begin{aligned} &j\left(2\tau\right)j\left(\frac{\tau}{2}\right)j\left(\frac{\tau+1}{2}\right)\\ =\ &\left(q^{-2}+744+196884q^2+\OO(q^4)\right)\cdot\\ &\left(q^{-1/2}+744+196884q^{1/2}+21493760q+864299970q^{3/2}+20245856256q^2+333202640600q^{5/2}+\OO(q^3)\right)\cdot\\ &\left(-q^{-1/2}+744-196884q^{1/2}+21493760q-864299970q^{3/2}+20245856256q^2-333202640600q^{5/2}+\OO(q^3)\right)\\ =\ &\left(q^{-2}+744+196884q^2+\OO(q^4)\right)\left(-q^{-1}+159768-8509194516q+151107477178368q^2+\OO(q^{3})\right)\\ =\ &\left(-q^{-3}+159768q^{-2}-8509195260q^{-1}+151107596045760+\OO(q)\right)\\ =\ &-j^3 + 162000j^2 - 8748000000j + 157464000000000 \end{aligned} \]

类似地，

\[ \begin{aligned} &j\left(2\tau\right)j\left(\frac{\tau}{2}\right) + j\left(\frac{\tau}{2}\right)j\left(\frac{\tau+1}{2}\right) + j\left(\frac{\tau+1}{2}\right)j\left(2\tau\right)\\ =\ &1488j^2 + 40773375j + 8748000000 \end{aligned} \] \[ \begin{aligned} &j\left(2\tau\right) + j\left(\frac{\tau}{2}\right) + j\left(\frac{\tau+1}{2}\right)\\ =\ &j^2 - 1488j + 162000 \end{aligned} \]

结合上述结果与Vieta定理得到，

\[ \begin{aligned} \Phi_2(X, j) = &-X^2j^2 + X^3 + 1488X^2j + 1488Xj^2 + j^3 - 162000X^2 + 40773375Xj\\ & - 162000j^2 + 8748000000X + 8748000000j - 157464000000000 \end{aligned} \]

为了验证上述结果是否正确，不妨考虑\(p = 14007008404447413697\)，\(\FF_p\)上的椭圆曲线\(E:y^2 = x^3 + Ax + B,\ A = 14007008365700685685,\ B = 14004095012137039409\)，它满足\(j(E)=114514\)。取\(R=(2059498320637642707, 0)\in E[2]\)，我们利用Vélu公式[5]计算以\(\langle R\rangle\)为核的同源\(\phi\)：

\[ \phi:E\to E',\quad \langle R\rangle \not\ni P = (x_P, y_P) \mapsto \left(x_P + \sum\limits_{Q\in \langle R\rangle-\{\infty\}}(x_{P+Q}-x_Q), y_P + \sum\limits_{Q\in \langle R\rangle-\{\infty\}}(y_{P+Q}-y_Q)\right) \]

进一步地，由于\(\#\langle R\rangle = 2\)，

\[ \phi(P) = \left(\frac{x_P^2-x_Px_R+t}{x_P-x_R}, \frac{(x_P-x_R)^2-t}{(x_P-x_R)^2}y_P\right),\quad P\notin\langle R\rangle \] \[ t=3x_R^2+A=7341004350464452570,\ w=x_Rt=2554626905828350750 \] \[ E':y^2=x^3+A'x+B',\quad A' = A-5t = 5316003422273250229,\ B' = B-7w = 10128715075785997856 \]

于是\(j(E') = 1728\cdot \frac{4A'^3}{4A'^3+27B'^2} = 911665652129516608\)，不难验证\(\Phi_2(j(E'), j(E)) \equiv 0 \pmod{p}\)。


  1. Class group action

数域\(K\)上的格\(\Lambda\)定义为\(K\)中的某个\([K:\QQ]\)维自由\(\ZZ\)-模，\(K\)上的序\(\OO\)定义为\(\OO_K\)中的某个\(\ZZ\)-维度为\([K:\QQ]\)的子环。对于每个\(\Lambda\)而言可以分配一个序\(\OO(\Lambda)\)，使得

\[ \OO(\Lambda) = \left\{\lambda \in K: \lambda \Lambda \subseteq \Lambda \right\} \]

若对于某个序\(\OO\)而言

\[ \OO(\Lambda) = \OO \]

则称\(\Lambda\)是一个恰当的\(\OO\)-格。将\(\OO\)-理想\(\mathfrak{a}\)看作是一个\(\OO\)-格，若\(\OO(\mathfrak{a})=\OO\)，则称\(\mathfrak{a}\)是一个恰当的\(\OO\)-理想。

我们定义理想类群（ideal class group）\(\text{cl}(\OO)=J(\OO)/P(\OO)\)，\(J(\OO)\)是\(\OO\)在\(K\)中（\(K=\operatorname{Frac}{\OO}\)）的所有可逆分式理想，\(P(\OO)\le J(\OO)\)是其中的所有主理想。注意到\(\OO(\Lambda)\)在与\(\Lambda\)位似的意义下唯一，故理想类群的元素为恰当\(\OO\)-理想的等价类。

理想类群的等价类可以与二元二次型（binary quadratic form）的等价类一一对应，Gauss证明了后者构成一个有限Abel群。\(\cl(\OO)\)有限[7, Thm 7.7]，（作为特例）\(\cl(\OO_K)\)有限[6, Thm 6.3]。记\(h(\OO):=\#\cl(\OO),\ d_K := \disc{\OO_K}\)，\(\OO = \ZZ + f\OO_K\)，我们还有[7, Thm 7.24]

\[ h(\OO) = \frac{h(\OO_K)f}{(\OO_K^*: \OO^*)} \prod\limits_{p\mid f}\left(1-\left(\frac{d_K}{p}\right)\frac{1}{p}\right) \]

且\(h(\OO_K)\mid h(\OO)\)。


对于复数域中具有复乘的椭圆曲线\(E/\CC\)与某个虚二次域的序\(\OO\)而言，\(\End(E)\cong \OO\)，故\(E/\CC\)与某个格\(\mathfrak{b}\subseteq \OO\)对应。反过来，\(\mathfrak{b}\)也对应一条椭圆曲线\(E_{\mathfrak{b}}\)。

考虑\(\mathfrak{a}\in J(\OO)\)在\(E_{\mathfrak{b}}\)上的作用：

\[ \mathfrak{a}E_{\mathfrak{b}} := E_{\mathfrak{a}^{-1}\ \mathfrak{b}} \]

对于主理想\(\mathfrak{a}\)而言，\(E_{\mathfrak{a}\mathfrak{b}} \cong E_{\mathfrak{b}}\)，于是我们可以自然地定义理想类群的作用：

\[ [\mathfrak{a}]j(E_{\mathfrak{b}}) := j(E_{\mathfrak{a}^{-1}\ \mathfrak{b}}),\quad [\mathfrak{a}]\in \cl(\OO) \]

我们考虑集合

\[ \text{Ell}_{\OO}(\CC) := \left\{j(E): E\text{ is defined over }\CC\text{ and }\End(E)\cong \OO \right\} \]

显然\(\cl(\OO)\)以群的方式作用在\(\text{Ell}_{\OO}(\CC)\)上，\(\cl(\OO)\)与\(\text{Ell}_{\OO}(\CC)\)之间存在双射，且只有\(\cl(\OO)\)中的单位元存在固定点——这意味着\(\cl(\OO)\)的作用是传递的。


对于从\(E/\CC\)到\(\mathfrak{a}E\)的同源\(\phi_{\mathfrak{a}}\)而言，不难证明（\(E\)具有\(\OO\)-复乘）

定理4-1：

  1. \(\ker{\phi_\mathfrak{a}} = E[\mathfrak{a}]\)
  2. \(\deg{\phi_\mathfrak{a}} = \text{N}\mathfrak{a} = (\OO:\mathfrak{a})\)

其中

\[ E[\mathfrak{a}] := \left\{P\in E(\CC): \alpha P=0,\ \forall \alpha\in\mathfrak{a}\right\} \]
  1. The Hilbert class polynomial

令

\[ H_{D}(X) := \prod\limits_{j\in\text{Ell}_{\OO}(\CC)} (X-j) \]

称其为Hilbert类多项式（Hilbert class polynomial (of discriminant \(D\))）。

定理5-1：Hilbert类多项式的系数为整数。

证明：设\(\OO\)为虚二次域的某个序，那么根据[7, Thm 9.12]，\(\cl(\OO)\)中的每个等价类都包含无穷多个质范理想，我们取其中的某个主理想\(\mathfrak{p},\ \text{N}\mathfrak{p} = p\)，那么显然\(\mathfrak{p}E\cong E\)，于是我们可以得到一个自同态：

\[ \begin{CD} E @>\mathfrak{p}>> \mathfrak{p}E\\ @. {_{\rlap{\quad \phi_{\mathfrak{p}}}}\style{display: inline-block; transform: rotate(30deg)}{{\xrightarrow[\rule{4em}{0em}]{}}}} @VV{\rotateninety{\sim}}V\\ @. E \end{CD} \]

根据定理4-1，\(E\to\mathfrak{p}E\)是度为\(p\)的同源，从而\(\phi_{\mathfrak{p}}\)是度为\(p\)的同源，于是根据定理3-2可得\(\Phi_p(j(E), j(E)) = 0\)，从而根据定理3-1的第四条每个\(j\in \text{Ell}_{\OO}(\CC)\)都是代数整数。

每个\(\sigma\in\Gal(\overline{\QQ}/\QQ)\)显然诱导一个自同态环间的同构：

\[ \begin{CD} \End(E^{\sigma}) @<\sigma<< \End(E)\\ @. {_{\rlap{\quad \style{display: inline-block; transform: rotate(25deg)}{\sim}}}\style{display: inline-block; transform: rotate(25deg)}{{\xleftarrow[\rule{3em}{0em}]{}}}} @AA{\rotateninety{\sim}}A\\ @. \OO \end{CD} \]

也即\(j(E^{\sigma}) = j(E)^{\sigma}\in \text{Ell}_{\OO}(\CC)\)，从而\(\Gal(\overline{\QQ}/\QQ)\)置换\( \text{Ell}_{\OO}(\CC) \)且保持\(H_D(X)\)的系数不变，即\(H_D(X)\in\QQ[X]\cap\overline{\ZZ}[X]=\ZZ[X]\)。

Q.E.D.

注：上述证明的开头使用的是弱化后的结论——即“存在质范主理想”——这无疑有大炮打蚊子的嫌疑。事实上，根据推论3-1，\(j(E) = j(\tau)\)是代数整数。


例5-1：对于\(D=-163\)而言，\(\OO = \left[\frac{1+\sqrt{-163}}{2}, 1\right]\)，\(h(\OO) = 1\)，从而\(H_{D}(X)\)仅有的一个根为整数。具有\(\OO\)-复乘的椭圆曲线\(E\)满足\(H_D(j(E)) = 0\)，利用\(j\)函数的q-级数展开式计算

\[ j\left(\frac{1+\sqrt{-163}}{2}\right) = \left.j\right\vert_{q = -\text{exp}(-\pi\sqrt{163})} \] \[ \abs{-e^{-\pi\sqrt{163}}} < 3.81\times 10^{-18} \]

可以预期，

\[ \begin{aligned} j\left(\frac{1+\sqrt{-163}}{2}\right) &\approx \frac{1}{q} + 744 + 196884q\\ &\approx -e^{\pi\sqrt{163}} + 744 + 7.5\times 10^{-13} \end{aligned} \]

这也就是说\(e^{\pi\sqrt{163}}\)几乎是整数。事实上，

\[ e^{\pi\sqrt{163}} \approx 262537412640768744 - 7.5\times 10^{-13} \]

于是我们可以得到

\[ j\left(\frac{1+\sqrt{-163}}{2}\right) = -262537412640768000 = -640320^3 \] \[ H_{-163}(X) = X + 262537412640768000 \]

例5-2：仿照上例，对于所有满足\(h(\OO) = 1\)的虚二次域判别式\(D\)而言，\(e^{\pi\sqrt{D}}\)都几乎是整数。

可以预期的是，随着\(\abs{D}\)的减小，q-级数中的误差便越大，从而对整数的近似效果也越差。

\[ e^{\pi \sqrt{43}}\approx 884736743.999777 \approx 960^3 + 744 \] \[ e^{\pi \sqrt{27}}\approx 12288743.983979 \approx 3\cdot 160^3 + 744 \]

例5-3：考虑\(h(\OO) = 2\)的虚二次域判别式\(D\)，我们写出所有判别式为\(D\)的约化二次型，它们形如

\[ x^2 + xy + \frac{1-D}{4}y^2,\quad ax^2 + bxy + \frac{b^2-D}{4a}y^2 \]

对于\(D = -427,-267,-235,-147,-123,-115,-75,-51\)而言\(a=b\)成立。根据Vieta定理，

\[ j\left(\frac{-1 + \sqrt{D}}{2}\right) + j\left(\frac{-b + \sqrt{D}}{2a}\right) \]

是整数。若\(a = b\)，那么理论上

\[ e^{\pi \sqrt{-D}} + e^{\pi \sqrt{-D} / a} \]

也几乎是整数，而这只有在两个和数均足够大时效果才明显，以\(D=-267\)为例，此时\(a = b = 3\)，

\[ e^{\pi \sqrt{267}} + e^{\pi \sqrt{267} / 3} \approx 19683091854079488001487.992708 \approx 19683091854079488000000 + 744\times 2 \]

由于\(e^{\pi \sqrt{267} / 3} = e^{\pi \sqrt{89/3}}\)，可以预期上式与整数的近似效果与上例中的\(e^{\pi \sqrt{27}}\)相近。

值得注意的是

\[ e^{\pi \sqrt{267} / 3} \approx 27000041.999971 \]

也几乎是一个整数。然而，这一点并不能用本文主要研究的j函数来解释。欲见造成这一点的原因可以参考[8]与[9]。













设\(f\)是\(2k\)阶非零自守函数，即\(f\)不恒为零，且对于\(\alpha = \begin{pmatrix}a & b \\ c & d\end{pmatrix}\in\Gamma\)而言，\(f(\alpha(z)) = (cz+d)^{2k} f(z)\)，且\(f\)在\(\infty\)处半纯。\(v_p(f)\)表示使得\((z-p)^{-v_p(f)}f(z)\)在\(z=p\)附近解析无零点的唯一的整数，那么根据留数定理可以算出

\[ v_\infty(f) + \frac{1}{2}v_i(f) + \frac{1}{3}v_\rho(f) + \sum\limits_{p\in(\Gamma\backslash\HH)-\{i,\rho\}} v_p(f) = \frac{2k}{12} \] \[ i=\sqrt{-1},\ \rho = e^{2\pi i/3} \]


定理1-1：对于域\(k\)上的椭圆曲线\(E/k\)而言，\(\End^0 (E)\)与以下三者之一同构

  1. 有理数域 \( \QQ \)
  2. 虚二次域 \( \QQ(\alpha),\quad \alpha^2 < 0 \)
  3. 四元数代数 \( \QQ(\alpha,\beta),\quad \alpha^2,\beta^2 < 0, \quad \alpha\beta=-\beta\alpha \)

证明：\(\QQ\subseteq\End^0(E)\)恒成立。若\(\alpha \in \End^0 (E)\)的像不在\(\QQ\)中，那么

\[ \Tr \left(\alpha-\frac{1}{2}\Tr \alpha\right) = \Tr \alpha - \frac{1}{2} \Tr\Tr\alpha = \Tr\alpha - \frac{1}{2}\cdot 2\Tr\alpha = 0,\quad \Tr=\Tr_{\QQ(\alpha)/\QQ} \]

此外，

\[ 0 \ne \alpha = r\otimes\phi, \quad \deg \phi > 0,\ r\in\QQ \] \[ \alpha^2 - (\Tr\alpha)\alpha + \Nm\alpha = 0 \implies \alpha^2 = -\Nm\alpha < 0 \]

这意味着虚二次域\(\QQ\left(\alpha-\frac{1}{2}\Tr \alpha\right)\subseteq\End^0(E)\)。现在不妨设\(\QQ(\alpha)\subsetneqq\End^0(E)\)，若\(\beta \in \End^0 (E)\)的像不在\(\QQ(\alpha)\)中（\(\Tr\alpha=0\)，且不妨设\(\Tr\beta=0\)），那么

\[ \Tr \left(\alpha\left(\beta-\frac{\Tr(\alpha\beta)}{2\alpha^2}\alpha\right)\right) = 0,\quad \Tr\beta = \Tr\left(\beta-\frac{\Tr(\alpha\beta)}{2\alpha^2}\alpha\right) \]

因此不妨设\(\Tr (\alpha\beta) = 0\)，此时

\[ \alpha\beta = -\widehat{\alpha\beta} = -\hat{\beta}\hat{\alpha} = -\beta\alpha \]

此外，不难验证\(1,\alpha,\beta,\alpha\beta\)张成一个\(\QQ\)-线性空间，接下来我们需要证明其\(\QQ\)-线性无关，首先显然

\[ \beta\notin\QQ(\alpha)\implies\alpha\notin\QQ(\beta) \]

即\(1,\alpha,\beta\)线性无关。其次，设\(\alpha\beta=a+b\alpha+c\beta,\ a,b,c\in\QQ\)，那么

\[ \alpha\beta\notin\QQ(\alpha),\QQ(\beta) \implies a,b,c\ne 0 \] \[ \implies -\alpha^2\beta^2=(\alpha\beta)^2=a^2+b^2\alpha^2+c^2\beta^2+2a(b\alpha+c\beta)+bc(\alpha\beta+\beta\alpha) \] \[ \implies b\alpha+c\beta\in\QQ \]

这与\(1,\alpha,\beta\)线性无关矛盾。这说明\(Q(\alpha,\beta)\)的确是一个四元数代数。进一步地，若\(\gamma \in \End^0 (E)\)的像不在\(\QQ(\alpha,\beta)\)中，不妨设\(\Tr\gamma=0,\ \Tr(\alpha\gamma)=0\)，于是

\[ \alpha\gamma=-\gamma\alpha,\quad \alpha\beta\gamma = -\beta\alpha\gamma = \beta\gamma\alpha \]

令\(\psi = \beta\gamma\)，则\(\alpha\psi = \psi\alpha\)，不妨设\(\Tr\psi=0,\ \Tr(\alpha\psi)=0\)，则\(\alpha\psi+\psi\alpha = 2\alpha\psi = 0\)。由于\(\End^0 (E)\)没有零因子，故\(\alpha=0\)或者\(\psi=0\)成立，而任何一者都是不可能的。

Q.E.D.




引理D-1：设\(f\)为零阶自守函数（\(\Gamma\)-模函数），即\(f\)是一个在\(\HH^*=\HH\cup\{\infty\}\)上\(\infty\)处半纯，在\(\Gamma\)下不变的函数，其在无穷远点有q-级数\(f=\sum\limits_{n=-N}^\infty c_nq^n\)，那么\(f\)可以表示为\(j\)的多项式，且系数为\(c_n\)的整系数线性组合。

证明：利用长除法，我们首先计算\(f_1=f-c_{M_1}j^{M_1},\ M_1 = -N\)，那么\(v_{\infty}f_1 > -N\)，重复此步骤算得\(f_2,f_3,\cdots,f_i,\cdots,\ M_i = v_{\infty}f_{i-1}\)，直到\(v_{\infty}f_k > 0\)，此时\(f_k\)在\(\HH^*\)上全纯，故根据Liouville定理与\(f_k\)的构造，\(f_k\)恒为0。

Q.E.D.


定理3-1：\(\Phi_n(X)\)满足

  1. \(\Phi_n(X)\in\ZZ[X,j]\)。
  2. \(\Phi_n(X)\)是\(\CC(j)\)上不可约的\(\psi(n)\)阶多项式。
  3. \(\Phi_n(X,j)=\Phi_n(j,X)\)。
  4. 若\(n\)不为平方数，则\(\Phi_n(j,j)\)次数大于1，且首项系数为\(\pm 1\)。

证明：

  1. 利用Smith标准形不难证明\(\Delta_n^* = \Gamma \alpha \Gamma,\ \alpha=\diag\{1, n\}\)，即\(\Gamma\)右传递置换\(j\circ\alpha_1,\cdots,j\circ\alpha_{\psi(n)}\in\Gamma\backslash\Delta_n^*\)，故\(\Gamma\)保持\(\Phi_n(X)\)的每个系数不变。又由于\(j\circ\alpha_i=\frac{1}{\zeta_{d_i}^{b_i}\cdot q^{a_i/d_i}}+\cdots\)，故\(\Phi_n(X)\)的系数在\(\HH\)上全纯，且在\(\HH^*\)上半纯。根据引理D-1，这意味着，

    \[ \Phi_n(X) \in \QQ(\zeta_n)((q^{1/n}))[X] =: k[X] \]

    显然\(k\)上的自同构

    \[ \sigma_r: \zeta_{n} \mapsto \zeta_n^r,\quad r\in (\ZZ/n\ZZ)^* \]

    保持\(\Phi_n(X)\)不变，于是我们可以将\(\Phi_n(X)\)的系数展开为\(\ZZ((q))\)中的q-级数，从而再次根据引理D-1，

    \[ \Phi_n(X) \in \ZZ[X],\quad \text{or } \Phi_n(X,j) \in \ZZ[X,j] \]

  2. 与上述类似，由于\(\Gamma\)传递置换\(j\circ\alpha_1,\cdots,j\circ\alpha_{\psi(n)}\in\Gamma\backslash\Delta_n^*\)，于是

    \[ \psi(n) = \abs{\Aut(L/K)} \ge [L:K],\quad K=\CC(j),\ L=K(j\circ\alpha_1,\cdots,j\circ\alpha_{\psi(n)}) \]

    故\(L/K\)是\(\psi(n)\)次Galois扩张，即证。

  3. 注意到

    \[ \Phi_n(j(\tau/n),j(\tau)) = 0 \implies \Phi_n(j(\tau),j(n\tau)) = 0 \]

    由于\(\Phi_n\)为上述\(X\)的极小多项式，故\(\Phi_n(X,j)\mid \Phi_n(j,X)\)，从而，

    \[ \Phi_n(j,X) = g(X,j) \Phi_n(X,j),\quad g\in\ZZ[X,j] \implies \Phi_n(X,j) = g(j,X) \Phi_n(j,X) \]

    于是，

    \[ \Phi_n(X,j) = g(X,j) g(j,X) \Phi_n(X,j) \implies g(X,j) g(j,X) = 1 \implies g(X,j) = \pm 1 \]

    \[ \implies \Phi_n(X,j) = \pm\Phi_n(j,X) \]

    若\(\Phi_n(X,j)=-\Phi_n(j,X)\)，则\(\Phi(j,j)=-\Phi(j,j)\)，与2.矛盾。

  4. 设

    \[ \alpha = \begin{pmatrix}a&b\\0&d\end{pmatrix} \in \Gamma\backslash\Delta_n^* \]

    \(ad=n\)，则\(a\ne d\)，于是

    \[ j-j\circ \alpha = \frac{1}{q} + \cdots - \frac{1}{\zeta_d^b q^{a/d}} - \cdots \]

    可以看出\(\Phi_n(j,j)\)的q-级数形为

    \[ \frac{c_m}{q^m}+\cdots \]

    即

    \[ \Phi_n(j,j) = c_mj^m+\cdots \]

    不难发现\(m>1\)，\(c_m\)为某个单位根，又由于\(c_m\in\ZZ\)，故必有\(c_m=\pm 1\)。

Q.E.D.




  1. Cheng Q. A new class of unsafe primes[J]. Cryptology ePrint Archive, 2002. https://eprint.iacr.org/2002/109
  2. Sedlacek V, Klinec D, Sýs M, et al. I Want to Break Square-free: The 4p-1 Factorization Method and Its RSA Backdoor Viability[C]//ICETE (2). 2019: 25-36. https://www.scitepress.org/Papers/2019/77866/77866.pdf
  3. S. Lang. Elliptic functions. Chapter 3, The Modular Function.
  4. S. Lang. Elliptic functions. Chapter 5, The Modular Equation.
  5. Moody D, Shumow D. Analogues of Vélu’s formulas for isogenies on alternate models of elliptic curves[J]. Mathematics of Computation, 2016, 85(300): 1929-1951. https://eprint.iacr.org/2011/430
  6. Neukirch J. Algebraic number theory[M]. Springer Science & Business Media, 2013. https://www.math.utoronto.ca/~ila/Neukirch_Algebraic_number_theory.pdf
  7. Cox D A. Primes of the Form x2+ ny2: Fermat, Class Field Theory, and Complex Multiplication. with Solutions[M]. American Mathematical Soc., 2022. https://www.math.utoronto.ca/~ila/Cox-Primes_of_the_form_x2+ny2.pdf
  8. Eta quotients of Dedekind eta functions. https://en.wikipedia.org/wiki/Dedekind_eta_function#Eta_quotients
  9. Ramanujan-Sato series. https://en.wikipedia.org/wiki/Ramanujan%E2%80%93Sato_series
  10. TravorLZH - 椭圆模函数（3）——模函数与模形式的基本性质 https://zhuanlan.zhihu.com/p/608669984
















Tags: #AlgebraicNumberTheory, #EllipticCurveCryptography, #ModularFunctions, #HomologyTheory, #ComplexAnalysis, #AlgebraicGeometry

Time: 2025-02-01 20:50