首页原创精华区最新随笔(rss)

共2页: 1 2 更多 

关于格的基本定理简要总结

1. 三条定律:交换律、结合律、吸收律(对于半格是幂等律),吸收律包含了幂等律
2. 上下界:交半格每对元素都有唯一最大下界,并半格每对元素都有唯一最小上界,格每对元素都有唯一最大下界和唯一最小上界

3. 格定义一个偏序,偏序有三个性质:自反性、反对称性、传递性
4. 格与偏序的关系:每个格对应一个偏序,但不是所有偏序都对应一个格,要满足每对元素都有唯一最小上界和(或,对于半格)唯一最大下界。如果集合中的任何一个子集(包括空集)均存在最小上界和最大下界,那么对应一个完备格

5. 任何元素有限的格都是完备格,格中的交运算和并运算对于其定义的偏序来说是单调的
6. 格的乘积、和、提升、映射仍然是格,利用这个性质,可以在已有格的基础上增量地构造描述能力更丰富的格,这种技术称为论域精化,是提高程序静态分析精度的重要指导思想之一

2023-09-06 23:39 作者: 春秋十二月【评论:0】【阅读:378】 

总结支配结点相关结论的证明

【命题1】控制流图G中若a dom n,且b dom n,则a dom b 或b dom a
【证明】设G入口为s,假设结论不成立,即a 不dom b且b 不dom a,或a dom b且b dom a。根据支配结点定义,如果是前者,则从s有全部路径经a(或b)到n但不经过b(或a),这与题设b(或a)dom n矛盾;如果是后者,则从s有全部路径经a,然后经b,再经a,构成了无限循环a->b->a->•••,永远到不了n,这也与题设矛盾。故结论成立

【命题2】控制流图G中若m idom n,则m是唯一的,若d ≠ n 且d dom n ,则d dom m
【证明】设G入口为s,假设不唯一,G中有另一个结点m'且m' idom n,根据支配结点定义,从s经m到n的路径上必有m' dom m,从s经m'到n的路径上必有m dom m',根据支配关系的反对称性,有m'=m,故唯一。假设d 不dom m,则从s到m的路径上不必然经过d,又m是n的唯一直接支配结点,则从s到n的路径上不必然经过d,即d 不dom n,这与题设矛盾,故d dom m。可以看到用反证法证明后一个结论时,直接支配结点的唯一性很关键

2023-09-06 22:57 作者: 春秋十二月【评论:0】【阅读:321】 

伽罗瓦连接

     摘要: 【性质】 1. 判定两个完全格L和M能否构成伽罗瓦连接,即抽象化函数α: L—>M是否完全加性的,或具体化函数γ: M—>L是否完全乘性的 2. 构造抽象化函数和具体化函数,即对于一个Galois连接(L, α, γ, M),给定α可通过γ(m) = ⊔{l | α(l) &#...  阅读全文

2023-09-06 22:42 作者: 春秋十二月【评论:0】【阅读:210】 

经典有限循环群的选取生成

记输出为[G`, G, p, q, g],其中p为大素数,G`为模p的有限循环整数群,阶为p-1;q为大素数,为G的阶,G为G`的子群(模亦是p),生成元为g(G`的一个元素),另外满足如下条件:
1. 1<q的位长<p的位长,p、q随机选取,p同余于1 mod q,即q整除p-1,q为p-1的素因子
2. 1<g<=p-1,随机选取,测试它的(p-1)/q次幂是否等于1 mod p,若等于则重新选取,直到不等于
3. 上面选定的g,遍历1到q的幂模p,就得到G的各元素

数学基础:一个有限群,对每个元素它的阶整除群的阶,它的群阶幂次方等于单位元;一个有限循环群,它的生成元个数为群阶的欧拉数,若群阶是素数,则所有非1的元素都是生成元
结论:这种计算子群的方法由于保证阶为素数且只要超过160位长,就可避免针对阶为合数的质因子分解并利用中国剩余定理求离散对数的已知最好攻击,具有中长期安全强度

2023-09-06 22:28 作者: 春秋十二月【评论:0】【阅读:272】 

总结AES加密涉及的数学定理

定理:令K[x]是由次数小于8、系数为0或1的多项式组成的环,m(x)=x^8+x^4+x^3+x+1为不可约多项式,则K[x]/(m(x))(模m(x)剩余类环)同构于元素个数为256的有限域F

证明:
​1. 构造映射H: P->Z,P表示K[x]中的多项式,Z表示小于256的非负整数,定义函数h(p)=z(mod 256)。显然H为双射;依初等数论同余性质有h(p1+p2)=(z1+z2)mod 256=z1(mod 256)+z2(mod 256)=h(p1)+h(p2),h(p1*p2)=z1*z2(mod 256)=z1(mod 256)*z2(mod 256)=h(p1)*h(p2),故H保持加法乘法封闭性。这点保证支持任意明文/密文的运算

​2. 由一元多项式环的性质得多项式乘法可以交换,即f(x)•g(x)=g(x)•f(x),满足域的交换条件。其乘法单位元是常数项1,满足域的单位元条件

​3. 因非零多项式f(x)与m(x)互素,由一元多项式环的互素定理知存在g(x)、k(x)使得f(x)•g(x)+m(x)•k(x)=1(系数模2),即f(x)•g(x)模m(x)余1(这里1表示单位元),故f(x)存在逆元,由群定义知逆元必唯一,满足域的逆元条件。另aes规定零多项式的逆元为其自身。这点保证s盒及列混合操作可逆

2023-09-06 22:22 作者: 春秋十二月【评论:0】【阅读:1316】 

共2页: 1 2 更多 

导航

网站分类

统计信息

聚合

Blog客户端API

推荐客户端

博客排行榜[前6人]