0

实现ML‐DSA所需的多项式和线性代数知识

Sun Yimin edited this page 2025-05-29 14:07:04 +08:00

Table of Contents

• 多项式
• 模运算
• 无穷范数

This file contains ambiguous Unicode characters

This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

大部分和实现Kyber所需的多项式和线性代数知识类似。

多项式

一个多项式是环 R_q 的一个元素[3]，看起来像这样：

f = f_0 + f_1 X + f_2 X^2 + \cdots + f_{255} X^{255}

但你甚至不需要知道这些。对你作为一个实施者来说，一个ML-DSA多项式就是一个有256个系数的数组。每个系数都是一个整数模 $q$，其中 $q = 8380417= 2^{23} - 2^{13} + 1$。一个系数数组被称为在 \mathbb{Z}_q^{256} 中，因为它由 256 个系数组成，每个系数都在 $\mathbb{Z}_q$，即整数模 $q$。

f_0 + f_1X + f_2X^2 + \cdots + f_{255}X^{255} \in R_q \downarrow

(f_0, f_1, f_2, ..., f_{255}) \in \mathbb{Z}_q^{256}

每个系数都适合放在一个uint32中，所以你可以为多项式编写一个类型，比如[256]uint32。

要加或减两个多项式（或者环元素），你需要逐个系数地进行（ c[0] = a[0] + b[0] ，以此类推）。在ML-DSA中，你永远不会直接乘以环元素。

模运算

ML-DSA中有两种模运算： mod 和 mod^{\pm} 。 mod^{\pm} 被称作对称模运算，其实只是在 mod 运算后，调整取值范围。

乘法结果适合放在一个uint64中。然后你可以选择Montgomery或Barrett约简算法。注意，Barrett约减的内积超过64位，所以我们选用Montgomery约简算法。你不能使用%，因为除法在硬件中不是总是恒定时间的。

无穷范数