13.4 环与域
本章目录 · 1 节
本章导读
【定义13.4.1】R上的两个二元运算记+、·。若⟨R,+⟩为阿贝尔群,⟨R,·⟩为半群,乘法对加法左右分配,则称环。本书这一环定义不预先要求乘法交换或乘法单位元。加法单位元记0,加法逆元记−a;乘法单位元存在时记1。a−b表示a+(−b),负元−a与乘法逆a⁻¹不能混淆。
【例13.4.1】Z、Q、R、C的通常加乘是环;同阶方阵加乘是矩阵环;P(B)的对称差作为加法、交作为乘法构成环,加法零元∅,乘法单位元B;Zₙ的模加、模乘构成模n整数环,n≥1。这里的+、·是抽象运算名称,并不在所有例子中等于普通数的加乘。(例完)
【定理13.4.1】环中有:(1)a0=0a=0;(2)(−a)b=a(−b)=−(ab),从而(−a)(−b)=ab;(3)a(b−c)=ab−ac,(b−c)a=ba−ca;(4)有限和展开
第一式由a(0+0)=a0+a0,再用加法消去;第二式由(−a)b+ab=0及负元唯一性;第三式由第二式与分配;第四式分别对两侧项数归纳展开,保持每个乘积中先aᵢ后bⱼ的次序。整个证明无需乘法交换。
【例13.4.2】非交换环中,
不能把aba与a²b、ba²合并,也不能无条件将中间两项写成−2ab。只有a、b互相交换时才可化成普通二项式公式。(例完)
【定义13.4.2】乘法交换称交换环;有乘法单位元称含幺环;ab=0必有a=0或b=0称无零因子。整环采用标准的非平凡定义:交换、含幺、1≠0且无零因子的环;域是每个非零元素均可逆的交换含幺环,亦要求1≠0。原书域定义中写|R|≥2,这个非平凡条件在整环处也明确补出,以免把单元素零环误当整环。一般环及含幺环仍可讨论零环,但须说明其1=0。
子环须对加、取负、乘封闭;若规定为“含同一单位元的子环”,还须含原环的1。子整环、子域采用相同运算,子域另须对非零取逆封闭。环同态保持指定加乘;是否保乘法单位元取决于是否将1列为签名常数,应按约定说明。
【例13.4.3】Z、Q、R、C都是整环,Q、R、C为域,Z因2等元素无整数乘法逆而不是域。2Z是交换、无零因子的环,但不含乘法单位元:若e·2=2必e=1,不在2Z,所以按本定义不是整环。
n≥2时Mₙ(R)为含幺环,不交换且有零因子。例如二阶矩阵A=diag(1,0)、B=diag(0,1)均非零,AB=O;嵌入高阶即可得到同样反例。Z₆交换、含幺,但2⊗3=0而两者非零,故不是整环、不是域。环中“零因子”指参与这种乘积为0的非零元素,不把0本身列作非零零因子。(例完)
【例13.4.4】p为素数,则Zₚ为域。若ij=0 mod p,素数整除积推出p|i或p|j,即无零因子;对i≠0,乘法映射x↦ix mod p为有限集合的单射,故满射,存在x使ix=1,交换性给两侧逆。因此所有非零元素可逆。反向,n≥2合数写n=ab,1<a,b<n,则a、b是非零零因子,所以Zₙ为域当且仅当n素数。有限域还可以有pᵏ个元素,但k>1时通常不是模pᵏ整数环;例如Z₄有零因子,不能当作四元域。(例完)
【定理13.4.2 费马小定理的组合证明】p素数、正整数m与p互素。把p个圆周位置用m种颜色着色,只把旋转视为相同。旋转群取0、θ、…,(p−1)θ,θ=2π/p,共p个不同旋转;0与pθ是同一个旋转,不能重复计入。
恒等旋转循环数p,其余p−1个旋转均为单个p循环,故轨道数 是整数。于是p|mᵖ−m;因p∤m,得 。任意整数的结论可先换成模p代表;若不要求互素,仍有mᵖ≡m mod p。用“手镯”一词时也要保留本证明“仅旋转”的等价关系,不能暗中增加翻转。
【有限域与平方根命题13.4.1】在Zₚ中,x²=1化为(x−1)(x+1)=0。p为奇素数时恰有两个不同根1、p−1;p=2时二者重合,只有根1。原命题若笼统写“素数时恰有两个根”,必须补上奇素数条件。
模12时根为1、5、7、11,其中5、7非平凡。找到不同于±1的平方根可判定合数;反向不成立,例如9是合数,模9的1的平方根仍只有1、8。因此不能把判素数完全等同于“寻找非平凡平方根”,还要结合幂同余测试。
【Miller–Rabin测试的依据】对奇数n>3,写n−1=2ˢd,s≥1、d为奇数。选底数a,2≤a≤n−2,构造 。素数n下,最后xₛ=1;从后向前遇到1时,前项只能是±1。于是必须有x₀=1,或x₀,…,xₛ₋₁之一等于n−1;不满足者给出确定的合数证据。
n=561、a=7时,s=4、d=35,完整平方链为241、298、166、67、1。67不是±1却平方为1,是非平凡根,所以561为合数。这也示范了“通过费马同余”仍不能证明为素数。
【算法与输出含义】先处理n<2为非素数,n=2或3为素数,其他偶数为合数。对剩余奇数执行一轮:随机均匀选a∈{2,…,n−2};若gcd(a,n)>1即为合数;求x=aᵈ mod n;若x=1或n−1,该轮通过;否则最多再平方s−1次,遇n−1通过,若在此之前遇1则判合数;循环结束仍未遇n−1则判合数。独立重复k轮,全通过后只输出“可能为素数”,不能将概率测试的返回值写成已证明素数。
对任意固定奇合数,标准Miller–Rabin定理给独立均匀随机底数的单轮漏检率至多1/4,k轮至多4⁻ᵏ;原书给的2⁻ᵏ是较弱上界,不能省掉独立抽样前提。这个条件概率是“给定n为合数仍通过测试”,不是无条件的“通过后n为素数的概率”,后者还与候选数的分布有关。固定的一组底数或非独立底数不能直接套这个随机误差界。
本结论不是由“所有强伪证底数自动形成真子群”一句话推出;强伪证底数集合通常不封闭,例如模65下底数8与18都能通过一轮测试,但乘积8·18 mod65=14不能通过;因此不能直接把全部通过底数作为真子群套用拉格朗日定理。原书相应略证需要这个修正。算法步骤核验参照NIST FIPS 186-5附录B.3.1,概率界可参照《Handbook of Applied Cryptography》第4章: https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.186-5.pdf ,https://cacr.uwaterloo.ca/hac/about/chap4.pdf 。此处仅用于数学原理与测试算法说明。
【全同态加密与环运算】2009年Craig Gentry提出基于理想格的全同态加密构造。它允许在不解密数据的条件下对密文执行计算,解密计算结果后得到相应明文函数值。严谨的正确性关系应写为
在方案规定的明文空间与支持计算范围内,以其正确性保证成立。对加、乘分别取F就得到加法、乘法同态。随机加密同一明文可以产生不同密文,因此不要求Eval所得密文字节串等于重新Enc结果;原书将二者简单写成密文完全相等,会掩盖这个区别。能做一次加法和一次乘法也不自动保证任意深度计算,仍须看方案的可支持电路与噪声控制条件。概念核验参照Gentry学位论文 https://crypto.stanford.edu/craig/craig-thesis.pdf 。
【RSA的代数示例】取不同素数p、q,n=pq,φ(n)=(p−1)(q−1),选e与φ(n)互素,令ed≡1 mod φ(n)。裸RSA映射在0≤m<n上为E(m)=mᵉ mod n,D(c)=cᵈ mod n。这里的e是公开指数,不要与群单位元的字母e混为同一对象。
在模n的明文乘法意义下,。但一般不保加法。例如p=5、q=11、n=55、e=3、d=27,E(1)=1而E(1+1)=8≠2=E(1)+E(1) mod55。它展示乘法同态,不能据此称全同态;以上是无填充的代数模型,不是可直接使用的安全加密方案,同态等式也不能随意推广到实际采用填充的RSA编码。
云端可以接收密文、执行受支持的计算并返回结果,由持有私钥的用户解密。这样的数据保密目标与是否计算正确、是否控制访问等是不同问题;不能从同态性一个等式推出所有安全属性都已满足。
