深度详谈 | 格困难问题之分圆多项式

上一篇我们介绍了 4 个格困难问题：SVP、CVP、SIS、BDD，加上“初探格理论（下）”中介绍的 LWE，我们一共了解了 5 个格中困难问题。这 5 个是格中比较基础的困难问题，许多基于格的密码算法都是由这 5 个困难问题构造的。

但是格中的困难问题可远远不止这些，上一篇提到过的 NIST 第三轮入选的 5 个格密码算法，就是基于一些定义更复杂的格中困难问题构造的，如 PFP、Module-LWE、Module-LWR 等。 

如果我们想要学习这些困难问题，需要先学一个抽象代数中的概念：分圆多项式环。

首先，了解一个小概念：  次单位根。

01

n次单位根

 次单位根，也就是使等式  成立的  ，我们要注意的是，后续的定理都需要在有模数  的情况下成立，故后续我们的定理都是在具有模数  的情况下进行讨论，为简单起见，我们将略去  (即此处是  )。

在大学的高等数学或者数学分析课上应该有学过一个很好用的公式–泰勒公式，就是把各种常见的函数都写成多项式的形式。这里需要用到 3 个: 

这 3 个公式有一个关系：  ，其中  是复数符号，  。

不过这可不是我们想要得到的结果，我们想要的是单位根！既然都说是单位根了，当然要有单位“  ”，上面的式子有“  ”吗？没有，我们得代入  ，  ，  才等于“  ”。 

也就是说，  。终于，单位“  ”浮出水面，那  次单位根也不远了，只要开  次方就好，   ，写成三角函数的形式就是   。

我们得到了  次单位根的两种形式：

指数形式

三角函数形式

如果想比较直观地认识，可以画一个图：把一个单位圆等分成  份，每一个小红点就是一个  次单位根。

  次单位根

其实无论是哪种形式，都很容易看出  次单位根共有  个。如果要用形式化表示，我们以  作为一个  次单位根，有  ，那么有  ，也就是每个  都是一个  次单位根。

为了引出下一个小概念，我们需要在这里先定义一个“阶”的概念：对于一个  次单位根  ，使  成立的最小正整数  ，就是  的阶，写作  。

 对于每个  次单位根  ，当然有  ，但  却不总是使该式成立的最小正整数。比如  时的单位根中有”  ”，  成立，但  也成立，  才是使  成立的最小正整数。

02

n次本原根

了解了  次单位根后，我们再学习一个小概念：  次本原单位根：在所有  次单位根  中，满足  的  次单位根  被称为  次本原单位根。

根据定义也可以看出，  次本原单位根是从  次单位根中取出来的部分根，   次本原单位根的个数肯定是小于等于  的，但是究竟有多少个呢？需要一点点数论的知识：

如果存在整数  ，使得  ，则我们说  整除  ，写作  ；两个整数  、  的最大公因子写作  ；有一个定理是这样的：如果  ，且  ，那么有  。

根据前面对于  次单位根的形式化，我们知道  都是  次单位根。现在我们想判断  是否属于  次本原单位根，即判断  是否等于  。我们假设  ，即  。

现在有  ，且  ，那么  。根据这个数论中的定理，我们可以知道如果  ，且  ，则  ，在这里我们考虑  、  都是正整数，则  。那么  的阶为  ，即  。

也就是说，满足  的  次单位根  是  次本原单位根。我们通常用欧拉函数  来表示满足  的  的个数。表示成图的形式： 

  次本原单位根

说完  次本原单位根，我们终于可以进入“多项式”啦。

03

分圆多项式

前面我们说过共有  个  次本原单位根，现在我们将它们写出来：  。通过之前画的图也可以很直观地看出来，  次单位根将一个圆均分为  等份，所以在这里我们定义一个多项式，叫做“分圆多项式”：  。 

稍稍介绍了一下分圆多项式的定义，下一篇我们将正式进入许多格困难问题基于的数学结构–分圆多项式环。

如有问题欢迎大家讨论与指教。

—END—

  文案 | 季炜丹      排版 | 刘晨

推荐阅读