矩阵离散对数 DLP in Matrix Groups

2024-03-19

字数统计: 1.7k字 | 阅读时长≈ 7分

矩阵离散对数 ：给定矩阵 $M \in \mathbb{F}_q^{n \times n}$ ，以及 $Y = M^x$ ，求解 $x$ 。

本篇博客参考文献[1][2] ，阐述如何基于若尔当标准型分解 $M = P J P^{-1}$ 将矩阵离散对数问题转换为有限域上的离散对数问题。

Remarks

通常矩阵会限制在线性群 $GL(n,q)$ 上（可逆矩阵），对于可逆矩阵，矩阵行列式不为 0，可以考虑行列式的幂同态，直接转换成有限域上的离散对数问题。针对矩阵行列式为 0 或者 1 的情况下，基于行列式的规约不可行。除此之外，我们需要矩阵更本质的数学结构来简化求解或者获取更多的指数信息（ $x\ge q$ ）。

若尔当标准型分解

Jordan Normal Form 是线性代数中一个非常重要的矩阵分解形式。在此之前，我们先简单介绍矩阵相似的概念，矩阵 $M$ 与 $J$ 相似，即存在可逆矩阵 $P$ 使得

$M = PJP^{-1}$

如果 J 是一个对角矩阵，那么称矩阵 $M$ 是可对角化矩阵（diagonalizable matrix），否则称为缺陷矩阵（defective matrix）。如何尝试将一个矩阵尽量对角化呢？这也是若尔当标准型分解的 motivation。

若尔当标准型

一般来说，一个域上的方阵 $A \in \mathbb{F}_q^{n \times n}$ 能够在原域或者其扩域上（如 $\mathbb{R} \implies \mathbb{C}$ ）相似于一个对角块矩阵（block diagonal matrix）。

$J=\left[\begin{array}{ccc} J_1 & & \\ & \ddots & \\ & & J_p \end{array}\right]$

其中每一个子矩阵 $J_i$ 称为一个若尔当块，具有下面形式：

$J_i=\left[\begin{array}{cccc} \lambda_i & 1 & & \\ & \lambda_i & \ddots & \\ & & \ddots & 1 \\ & & & \lambda_i \end{array}\right] .$

其中 $\lambda_i$ 是原矩阵 $A$ 的特征值。特别地，每个若尔当块维度为 1 时，矩阵 $J$ 就是一个对角矩阵。矩阵 $A$ 可对角化等价于：矩阵 $A$ 有 $n$ 个互不相同的特征值，具体证明在这里省略。

矩阵离散对数问题

矩阵离散对数 ：给定矩阵 $M \in \mathbb{F}_q^{n \times n}$ ，以及 $Y = M^x$ ，求解 $x < q \in \mathbb{Z}$ 。

定义在 $\mathbb{F}_q$ 上的矩阵离散对数可以转换到 $\mathbb{F}_q^{m_i}$ 上的一般有限域上的离散对数求解。转换方法就是通过若尔当标准型来做，对于任意可逆矩阵 $M$ ，存在一个可逆矩阵 $P$ ，使得：

$M = PJP^{-1}$

矩阵 $J$ 称为若尔当标准型，是一个近乎对角矩阵（上三角矩阵），具体形式与特征值有关。但是其对角线元素一定是矩阵 $M$ 的特征值，超对角线元素为 0 或者 1，其他位置均为 0，即：

$J = \begin{bmatrix} \lambda_1 & * & & \\ & \lambda_2 & \ddots & \\ & & \ddots &*\\ & & & \lambda_n \end{bmatrix} \\ J[i][i] = \lambda_i , \quad \text{eigenvalues of M}$

根据若尔当标准型分解， $Y$ 表示如下：

$Y = M^x = P J^x P^{-1} \\ \implies J^x = P^{-1} Y P$

而对于上三角矩阵来说：

$J^x = \begin{bmatrix} \lambda_1^x & & \cdots & \\ & \lambda_2^x & \cdots & \\ & & \ddots \\ & & & \lambda_n^x \end{bmatrix} \\$

我们只要求出若尔当矩阵 $J$ 和转换矩阵 $P$ ，于是矩阵离散对数就能规约成 $n$ 个有限域上的离散对数求解。但是，若尔当矩阵不一定在原有限域上存在（特征值不在有限域 $\mathbb{F}_q$ 上），需要在扩域上求解，最常见的方式是在分裂域上求解出所有特征值。

一般的矩阵离散对数问题规约

给定 $M \in \mathbb{F}_q^{n \times n}$ ，以及 $Y = M^x$ ，规约如下：

计算若尔当标准型 $J$ 与转化矩阵 $P$ 使得：
$M = PJP^{-1}$
计算矩阵 $Y$ 在转化矩阵下的作用：
$J^\prime = J^x = P^{-1} Y P$
得到 $n$ 个 $\mathbb{F}_q$ 或者扩域 $\mathbb{F}_{q^k}$ 上的离散对数问题：
$\begin{aligned} J^\prime[0][0] & = (J[0][0])^x \in \mathbb{F}_{q^k} \\ &\cdots \\ J^\prime[n-1][n-1] & = (J[n-1][n-1])^x \in \mathbb{F}_{q^k} \\ \end{aligned}$
简记对角元 $J_i = J[i][i]$ , $|J_i|$ 代表 $J_i$ 的乘法阶，则 $x_i = log_{J_i}(J_i^\prime)$ 满足 $x_i = x \mod |J_i|$

特别地，当矩阵 $M$ 的若尔当标准型存在大于等于 2 的若尔当块时，离散对数的求解可以进一步规约成有限域上的线性方程求解。考虑二维的若尔当块，我们有：

$J_2^x = \begin{bmatrix} \lambda & 1 \\ & \lambda \end{bmatrix}^x = \begin{bmatrix} \lambda^x & x \lambda^{x-1} \\ & \lambda^x \end{bmatrix}$

已知 $\lambda, \lambda^x, x\lambda^{x-1}$ , 求解 $x$ 是简单的。

基于特征值的矩阵 DLP

在某些情况下，求矩阵 $M \in \mathbb{F}_q^{n \times n}$ 的若尔当标准型并不容易，特别是某些特征值在 $F_q$ 不存在的情形，此时我们需要改变矩阵的基环（base ring 此处应该为 base field）为对应的扩域，再求 Jordan Form。但是很多时候我们并不需要求出完整的 $J,P$ 矩阵。

我们最关注的是矩阵特征值和矩阵幂的同态关系，注意到上节规约的最终结果是求解两个矩阵对应特征值的离散对数： $k = log_x(y) , \text{ where } y = \lambda^k, x = \lambda$ , 于是我们可以考虑对部分特征值求离散对数。

对一般矩阵 $M \in \mathbb{F}_q^{n \times n}$ 而言，它不一定在 $\mathbb{F}_q$ 上存在 $n$ 个特征值，考虑 $M, Y=M^k$ 的特征多项式：

$\rm \begin{aligned} p_M(x) &= \bf{det} (xI - M) \\ p_{Y}(x) &= \bf{det} (xI - Y) \end{aligned}$

假定 $p_M(x)$ 存在特征值 $\lambda \in \mathbb{F}_q$ ，则其对应 $\lambda^k \in \mathbb{F}_q$ ，并且 $\lambda^k$ 也一定是矩阵 $Y=M^k$ 的特征值（特征值满足 $Mv = \lambda v$ , 易证），从而 $p_Y(x)$ 一定存在根 $\lambda^k$ 。

基于特征值的矩阵 DLP 规约如下：
给定 $M \in \mathbb{F}_q^{n \times n}$ ，以及 $Y = M^k$

计算特征矩阵 $p_M(x) , p_Y(x)$
如果 $p_M(x)$ 在 $\mathbb{F}_q$ 存在至少一个非 0 根，继续进入下一步。否则基于 $p_M(x)$ 的分解重新选择基域的扩域 $\mathbb{F}_{q^t}$ ，并且求解 $p_M(x)$ 在新的基域上的根。
假定我们在第二步中得到的最终基域为 $\mathbb{F}$ , $p_M(x)$ 存在 $m$ 个根 $x_1, \cdots, x_{m}$ 。同样地，我们在 $\mathbb{F}$ 中计算 $p_Y(y)$ 的根，我们能够得到 $m$ 个根 $y_1, \cdots, y_{m}$ 。
选择（固定）一个特征值 $x_i$ ，尝试依次对 $y_j$ 求解离散对数，存在某个匹配的 $i, j$ 使得 $k = log_{x_i}(y_j)$ ，即离散对数 $Y = M^k$ 。

Remarks

感兴趣的读者可以参考 The Discrete Logarithm Problem in GL(n, q) 中的 Section 4 中的 Jordan canonical form 算法 1 和 Section 5 中的规约算法 2，了解更多的数学细节。

参考文献：