全同态加密数学基础—分圆多项式-3

更多精彩,请点击上方蓝字关注我们!

全同态加密数学基础—分圆多项式-3

本文由陈智罡博士撰写
前面说过,可以对 xn-1 分解为更低次数的不可约多项式,例如 xn-1= (xk-1) f(x)。 这就引出了我们要讲的中心概念:分圆多项式。 这个次数更低的不可约多项式,称为分圆多项式,记为全同态加密数学基础—分圆多项式-3。分圆多项式的次数就是 n 次单位原根的个数,即全同态加密数学基础—分圆多项式-3
另外,再次提醒:分圆多项式在有理数域上是不可约的。 所以,全同态加密数学基础—分圆多项式-3是在环全同态加密数学基础—分圆多项式-3上次数为的全同态加密数学基础—分圆多项式-3不可约多项式。
分圆多项式与 n 次单位原根产生了关系,具体地说,分圆多项式的次数就是 n 次单位原根的个数。这就是为什么我们花了很多口舌说单位原根的原因。 墙裂注意:n 次单位根中有全同态加密数学基础—分圆多项式-3个 n 次单位原根!!!!
再次重复: 那些在 n 次单位根中,不是 n 次单位原根的都是某个 a 次单位原根,其中 a 是 n 的一个因子。
而这全同态加密数学基础—分圆多项式-3个 n 次单位原根就是分圆多项式全同态加密数学基础—分圆多项式-3的根!令 n 次单位原根,对应全同态加密数学基础—分圆多项式-3。令 a 次单位原根,对应全同态加密数学基础—分圆多项式-3。所以就把 z,z 2,…,zn-1 进行了划分,表示为全同态加密数学基础—分圆多项式-3,其中 d 是 n 的因子。
问题来了,分圆多项式全同态加密数学基础—分圆多项式-3分解形式是什么样的?根据上面论述有:
全同态加密数学基础—分圆多项式-3全同态加密数学基础—分圆多项式-3
下面来看看分圆多项式与单位原根之间的关系。 由于每个 n 次单位根 ,要么是 n 次单位原根,要么是某个 d 次单位原根。所以 xn-1 可以表示成下面形式:
全同态加密数学基础—分圆多项式-3另外,n 次分圆多项式其实就是 xn-1 的一个“最大”的不可约多项式因子。最大就是对于任意 k,该 n 次分圆多项式都不是 xk-1 的因子。 所以分圆多项式还可以定义为:它是一个整系数首一多项式,该多项式是任何 n 次单位原根上的有理数域上的最小多项式。 根据上面公式,多项式 zn-1 的分解如下:
全同态加密数学基础—分圆多项式-3分圆多项式如下:
全同态加密数学基础—分圆多项式-3
分圆多项式在有理数域上是不可分解的,但是在复数域上可以分解为一次因子的乘积。那么,在有限域上表现如何呢? 应用最小多项式在有限域上,分圆多项式在有限域 Fp[x] 上可以分解为最小多项式的乘积。有如下性质: 假设有限域的元素个数是 p,其中 p 是素数而且 p 不是 n 的因子,则分圆多项式全同态加密数学基础—分圆多项式-3可以分解为全同态加密数学基础—分圆多项式-3个次数为 d 的不可约多项式,其中 pd=1 (mod n)。
这个性质经常用于全同态加密中明文空间的明文槽的划分。 最后说说最小多项式长得啥样。 假设 a 是域 F (元素个数为 n)的任意一个元素,a 的次数 d 是 n 的因子,则 a 最小多项式如下:
全同态加密数学基础—分圆多项式-3

有了这些知识,再看全同态加密论文中关于明文空间的划分就容易理解了。 格密链公司一直致力于全同态加密与区块链技术的研发。

全同态加密数学基础—分圆多项式-3

全同态加密数学基础—分圆多项式-2

全同态加密数学基础—分圆多项式-1

有哪些公认的精品计算机课程资源杀手级应用是如何炼成的-5杀手级应用是如何炼成的-4杀手级应用是如何炼成的-3杀手级应用是如何炼成的-2

杀手级应用是如何炼成的-1

2020 年 real world crypto 学术会议论文列表隐私保护计算技术指南 42020 年金融密码学与数据安全学术会议论文列表全同态加密资源汇总如何学习全同态加密

全同态加密资源汇总,全同态加密与机器学习论文列表

全同态加密数学基础—分圆多项式-3

欢迎收听“区块链杂谈”节目,国内最有质量的区块链知识分享节目。

全同态加密数学基础—分圆多项式-3

全同态加密数学基础—分圆多项式-3

全同态加密数学基础—分圆多项式-3

◆ ◆ ◆ ◆ ◆

全同态加密数学基础—分圆多项式-3

格密链

专注于区块链上的密码学技术

长按扫码可关注