本文由陳智罡博士撰寫
前面說過，可以對xn-1 分解為更低次數的不可約多項式，例如xn-1= (xk-1) f(x)。
這就引出了我們要講的中心概念：分圓多項式。
這個次數更低的不可約多項式，稱為分圓多項式，記為
。
分圓多項式的次數就是n次單位原根的個數，即
。
另外，再次提醒：分圓多項式在有理數域上是不可約的。
所以，
是在環
上次數為的
不可約多項式。
分圓多項式與 n次單位原根產生了關係，具體地說，分圓多項式的次數就是n次單位原根的個數。這就是為什麼我們花了很多口舌說單位原根的原因。
牆裂注意：n次單位根中有
個n次單位原根！！！！
再次重複：那些在n次單位根中，不是n次單位原根的都是某個a次單位原根，其中a是n的一個因子。
而這
個 n次單位原根就是分圓多項式
的根！
令n次單位原根，對應
。
令a次單位原根，對應
。
所以就把z,z 2,…,zn-1 進行了劃分，表示為
，其中d是n的因子。
問題來了，分圓多項式
分解形式是什麼樣的？
根據上面論述有：
下面來看看分圓多項式與單位原根之間的關係。
由於每個n次單位根，要麼是n次單位原根，要麼是某個d次單位原根。所以xn-1可以表示成下面形式：
另外，n次分圓多項式其實就是xn-1 的一個「最大」的不可約多項式因子。最大就是對於任意k<n，該n次分圓多項式都不是xk-1 的因子。
所以分圓多項式還可以定義為：它是一個整係數首一多項式，該多項式是任何n次單位原根上的有理數域上的最小多項式。
根據上面公式，多項式zn-1的分解如下：
分圓多項式如下：
分圓多項式在有理數域上是不可分解的，但是在複數域上可以分解為一次因子的乘積。那麼，在有限域上表現如何呢？
應用最小多項式在有限域上，分圓多項式在有限域Fp[x]上可以分解為最小多項式的乘積。有如下性質：
假設有限域的元素個數是p，其中p是素數而且p不是n的因子，則分圓多項式
可以分解為
個次數為d的不可約多項式，其中pd=1 (mod n)。
這個性質經常用於全同態加密中明文空間的明文槽的劃分。
最後說說最小多項式長得啥樣。
假設a是域F（元素個數為n）的任意一個元素，a的次數d是n的因子，則a最小多項式如下：
有了這些知識，再看全同態加密論文中關於明文空間的劃分就容易理解了。
格密鏈公司一直致力於全同態加密與區塊鏈技術的研發。
全同態加密數學基礎—分圓多項式-2
全同態加密數學基礎—分圓多項式-1
有哪些公認的精品計算機課程資源
殺手級應用是如何煉成的-5
殺手級應用是如何煉成的-4
殺手級應用是如何煉成的-3
殺手級應用是如何煉成的-2
殺手級應用是如何煉成的-1
2020年real world crypto 學術會議論文列表隱私保護計算技術指南4
2020年金融密碼學與數據安全學術會議論文列表
全同態加密資源匯總
如何學習全同態加密
▼
全同態加密資源匯總，全同態加密與機器學習論文列表
▼
歡迎收聽「區塊鏈雜談」節目，國內最有質量的區塊鏈知識分享節目。
◆ ◆ ◆ ◆ ◆
格密鏈
專注於區塊鏈上的密碼學技術