0

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

Sun Yimin edited this page 2025-04-30 09:20:47 +00: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}

无穷范数