1. 对于rsa，给定大整数n分解的一对素因子p和q，p或q是否素数决定不了rsa的安全性，但决定rsa算法的正确性，也就是说p或q不能为合数，而安全性取决于n的位数及p、q的距离，因为素数测试是一个P问题，而因子分解是一个NP问题，其耗时是关于n的指数
2. 对于dh密钥交换，通常选择阶为素数的有限循环(子)群，这时素数决定了安全性。因素数不能再因子分解，故避免了针对阶为合数的质因子分解且利用中国剩余定理求离散对数的(已知最好)攻击
3. 周知Shamir门限方案基于多项式的拉格朗日插值公式，普遍的设计采用GF(q)域上的多项式，秘密s为f(0)，q是一个大于n的大素数（n是s被分成的部分数）。正常来讲，参与者个数必须至少是设计时的k，才能恢复出正确的s。如果个数少于k比如k-1，则只能猜测s0=f(0)以构建第k个方程，那么恢复得到的多项式g(x)等同设计时的多项式f(x)的概率是1/q。因为g(x)的项系数可以看作关于s0的同余式即h(s0)=(a+b*s0)mod q的形式，因q为素数，故依模剩余系遍历定理，当s0取GF(q)一值时，则h(s0)唯一对应另一值。所以h(s0)等于f(0)的概率为1/q。由此可见，当q取80位以上，敌手攻击概率不大于1/2^80，这已经很低了。这种门限方案如同RSA加密，再次佐证了素数越大安全性越高
4. PGP是密码学经典应用，体现在首先支持保密与认证业务的正交，即独立或组合，且组合时按认证、压缩、加密的顺序，这个顺序是经考究有优势的；其次会话密钥是一次性的，由安全伪随机数生成器生成，且按公钥加密；最后使用自研的密钥环与信任网解决公钥管理问题。理论本质上，PGP提供的是一种保密认证业务的通用框架，因为具体的对称加密算法、随机数生成、公钥算法，都可依需要灵活选配扩展。PGP有两个问题跟组合与概率相关，一个是算密钥环N个公钥中，密钥ID(64位)至少有两个重复的概率？设所求概率为p，先算任意两个不重复的概率q，令m=2^64，则q=m!/((m-N)!*m^N)，则p=1-q，不难看出，N越小则q越大则p越小，因实际应用N<<m，故p非常小可忽略，即PGP取公钥中最低64有效位作密钥ID，是可行的。另一个是签名摘要暴露了前16位明文，对哈希函数安全的影响有多大？这问题意思应该是敌手拿到消息后但没发送方的私钥作签名，只能穷举变换原消息并求哈希值，使之与消息摘要剩余位组相等。这本质是求两类生日攻击碰撞概率大于0.5时所需的输入量。在仅认证模式中，抗弱碰撞计算量降低为原来的1/2^16，抗强碰撞计算量至少降低为原来的1/2^8。另外，考虑到这16位明文可能的特殊性，有没更快的代数攻击，需进一步研究
摘要: 布尔数据 边的相交
eryar@163.com
1 Introduction
在OpenCASCADE中对于边的相交分为三类：边与点，边与边，边与面，边与点的相交已经归结为点与边的相交处理了，边的相交主要处理边与边，边与面的相交。边与边、边与面的相交会引入一个新的数据结构-公共部分Common Part，用于保存重叠的公共部分数据。
2 Edge/Edge Interferences
对... 阅读全文
[开源]-OpenCASCADE-IMGUI
1 IMGUI
ImGui 是一个用于C++的用户界面库，跨平台、无依赖，支持OpenGL、DirectX等多种渲染API，是一种即时UI（Immediate Mode User Interface）库，保留模式与即时模式的区别参考保留模式与即时模式。ImGui渲染非常快，但界面上有大量的数据集需要渲染可能会有一些问题，需要使用一些缓存技巧。缓存只是避免数据的更新逻辑耗时太久影响渲染，实际渲染过程不存在瓶颈。
IMGUI很轻量，还支持跨平台，对于小的测试程序IMGUI是理想的GUI。
2 OcctImgui
基于opencascade的glfw sample加入IMGUI，这样就可以开发一些带有GUI的程序。这些程序小巧且能方便跨平台，看上去效果也不错。
现在将OcctImgui开源，开源地址：https://github.com/eryar/OcctImgui
使用Premake来生成解决方案，只需要将premake5.lua中的相关第三方库的路径修改一下，即可以直接编译运行。
3 Next
目前occt的视图作为整个背景，下一步可以做成像CADRays中那样，将occt的视图作为视图的一部分，这样就可以使用IMGUI的Docking功能。
使用IMGUI也可以开发出很Cool的界面，最后放两个基于IMGUI开发的图形界面：
https://github.com/adriengivry/Overload
https://github.com/sasobadovinac/CADRays
https://github.com/MeshInspector/MeshLib
摘要: 布尔数据 BOPDS_DS
eryar@163.com
1 Introduction
在OpenCASCADE中，布尔相关的算子Operator有General Fuse Operator(GFA)，Boolean Operator(BOA)，Section Operator(SA)，Splitter Operator(SPA)，这些布尔算子都共用一套数据结构BOPDS_DS，其中存储了输入... 阅读全文
周知编译原理龙书阐述的基本块指令调度算法，它所使用的空的资源预约表RTD与每个指令的资源预约表RT，可以看作二维矩阵，行表示时钟周期、列表示cpu资源，其定位的元素值1表示占用/预约，0表示空闲/非预约。前者是随周期递增而动态扩大的矩阵，后者是固定尺寸(维数)的矩阵（指令花费周期与每周期预约资源皆已知）。在调度时，按带优先级比如关键路径的拓扑排序基本块内的指令，顺序选取一条指令Inst，计算每前驱发射周期加延迟的结果tmp，取所有tmp的最大值tmax作为Inst的发射周期，再判断处理器资源是否可用，即RTD和RT作与运算，得到一个新矩阵RTN，若RTN为全零矩阵则tmax为Inst的最终发射周期，否则递增tmax再做矩阵与运算，直至得到全零矩阵。最后更新RTD，即RTD与RT作或运算结果存于RTD。重复上述过程直到基本块末尾。
综上不难看出，如果一个基本块很大比如有1000条指令，平均每指令花2个周期，则RTD需要2000个条目，若一条目即矩阵每行占用32字节（256种资源数），则总量约64k。当然这对于现代内存体量来说不算什么，但可以有更好的节省内存的做法：RTD尺寸其实可以相对固定，其上限为基本块中耗费周期最多指令的周期的一个大于1常数因子倍（为兼顾指令并行性），这样一来就要增加当指令完成时（当前指令发射周期大于前一条的终止周期时复位前一条指令的RTD）从发射周期处复位RTD即作一个矩阵反运算的操作，其它步骤对应的矩阵与、矩阵或运算的操作保留不变。另由于RTD固定了尺寸，因此发射周期递增后要取模
【备注】以上是我针对简单机器模型（每种资源数量仅一个，比如整数运算单元1个，内存访问单元1个，浮点运算单元1个）用布尔矩阵作的优化。如果是复杂的超标量机器即每种资源数有多个，那么只需修改如下：布尔矩阵换成整数矩阵；新增一个机器资源可用总数整数矩阵RDA（单列资源数同值），布尔矩阵与运算换成加法并与RDA比较，若大于RDA则递增tmax；布尔矩阵或运算换成加法；布尔矩阵反运算换成减法，RTD减RT存于RTD
摘要: 布尔数据 BOPDS_Iterator
eryar@163.com
1 Introduction
OpenCASCADE中新的布尔工具TKBO相对已经废弃的TKBool代码更规范，更易于理解。与ModelingData和ModelingAlgorithms大的模块组织一样，主要也是数据结构Data Structure+算法Algorithm的组织形式。
其中BOPDS为布尔中的数据结构... 阅读全文
OpenCASCADE GLFW IMGUI
如果从事过C++ Windows客户端开发，大家对MFC、Qt、DuiLib、WxWidgets等各种DirectUI应该有了解，本篇给大家介绍一个超级轻量级的C++开源跨平台图形界面框架ImGUI. ImGUI主要用于游戏行业，所有的控件都需要手绘实现，当然性能也是满满的，毕竟是直接用dx/opengl来实现。ImGUI仓库：https://github.com/ocornut/imgui
ImGUI又称为Dear ImGui，它是与平台无关的C++轻量级跨平台图形界面库，没有任何第三方依赖，可以将ImGUI的源码直接加到项目中使用，也可以编译成dll, ImGUI使用DX或者OpenGL进行界面渲染，对于画面质量要求较高，例如客户端游戏，4k/8k视频播放时，用ImGUI是很好的选择，当然，你得非常熟悉DirectX或者OpenGL，不然就是宝剑在手，屠龙无力。相对于Qt、MFC、DuiLib、SOUI等，ImGUI的拓展性更好，也更轻量级，当然对于开发者的要求也更高.ImGUI没有类似于Qt/MFC这种，可以拖拽控件进行搭建界面，ImGUI的所有控件都必须手写实现。ImGUI的demo基本提供了所有控件、图表等的实现，源码也有，可以对照的学习。在PC端技术选型时，如果公司有音视频、图形图像、4k/8k视频业务，或者一些简单的UI可以考虑一下使用ImGUI，毕竟是直接使用DX/OpenGL来进行绘制渲染，其它功能就直接使用C++来实现。
OpenCASCADE提供了一个GLFW的示例程序，将OpenCASCADE与IMGUI集成起来，对于实现一些简单的小的三维应用程序的UI，有满满的科技感。很多游戏相关的小程序都是使用IMGUI来做界面。
其中OpenCASCAE开源的光线追踪程序CADRays的UI就是用IMGUI实现的：
IMGUI也支持Docking，常见的控件都有，并且也支持跨平台，只依赖OpenGL，生成的程序体积很小。
使用GLFW配置IMGUI可以实现跨平台的界面开发，对于不复杂的应用程序是个不错的选择。
摘要: 几何内核与数学
1 概述
从1950年第一台图形显示器（美国麻省理工大学MIT旋风I号Whirlwind I）的诞生，到1962年MIT林肯实验室的Ivan E. Sutherland发表题为“Sketchpad: 一个人机交互的图形系统”确定计算机图形学作为独立科学分支。经过70多年的发展，计算机图形学中的几何造型技术成了现在的几何内核。
数学是我们从小学、中学到大... 阅读全文
曾因朋友问到监控，致使我探究了kretprobe的实现，想到编译中的尾调用优化，作个小结
1. kretprobe_trampoline_holder该跳转函数无参是必须的或说最好的通用设计，因为替换返回地址是非正常程序流程，即被探测函数的调用者无感知，不存在为跳转函数准备入参。若要设计传参且只读，则不会破坏被探测函数调用者的上下文，但跳转函数内部流程怎么用参数是个问题，这需要一种约定
2. 跳转函数为调用trampoline_handler准备入参，即在栈上构造一个（不完整的）pt_regs，再把它地址即栈顶赋给rdi，rdi是x86_64上传入第一参数使用的寄存器，同时预留一个栈单元存放原返回地址（为什么要预留？因为被探测函数返回时，其调用者存放返回地址的栈空间被释放了，所以得在跳转函数内造一个）。由于trampoline_handler内调到用户自定义handler而传入pt_regs，因此自定义handler内要注意最好别改动pt_regs，否则会破坏被探测函数调用者的上下文
3. 表面看kretprobe的实现流程有点像尾调用优化，但有本质区别。后者中被调尾函数直接释放父调用者的栈帧，就可恢复到父调用者的返回地址；前者不能这样干，因为被探测函数的返回地址被替换了，所以需要一个时地（时机地点）恢复，而这时地正是跳转函数的收尾序列代码，把原来的返回地址放于上述2所讲的预留栈单元，这样最后的ret指令弹出它并跳到原返回地址执行。为保证恢复后正常执行，还得恢复被探测函数调用者的上下文即寄存器信息（无须恢复栈内容，因为上述1讲到了跳转函数是无参的）
有理数域的本原多项式与有限域的本原多项式定义不同，前者不要求不可约（由高斯引理知两个本原多项式的乘积还是本原），后者则必须不可约（确保生成的有限域其每个元素有逆元）。aes基于有限域F{0,1}设计，故使用的模8次多项式不可约P(x)=x^8+x^4+x^3+x+1，但不是本原多项式，因为它的阶是51而非255。有限域次数为8的本原多项式有16个、不可约多项式有30个（由莫比乌斯反演推出），具体多项式影响s盒与列混合操作的实现。不可约加之0的逆元规定为0，保证正确加解密。若0的逆元规定为非0比如x，则导致x有两个逆元，便违反了逆元唯一性，除非s盒不用有限域设计。逆元等于其自身的非0元素只有1，原因可类比模素数二次剩余的求解
1. 若DFA D是用子集构造法从NFA N构造出来的，则L(D)=L(N)
2. 一个语言L被某个DFA接受，当且仅当被某个NFA接受
3. 一个语言L被某个£-NFA接受，当且仅当被某个DFA接受
4. 若对于某个DFA A，L=L(A)，则存在一个正则表达式R使得L=L(R)
5. 每一个用正则表达式定义的语言也可用有穷自动机定义
6. 若通过填表算法不能区分两个状态，则它们是等价的
7. DFA的状态等价性是传递的
8. 若对于DFA每个状态q及与q等价的所有状态组成块，则不同的状态块形成状态集合的划分。也就是说，每个状态恰好属于一个块，同一块中的所有成员都是等价的，从不同块中选择的状态对都不是等价的
9. 根据等价状态划分算法最小化DFA D得到的DFA M是唯一的。也就是说，不存在其它等价于D的DFA N，其状态数比M少
----------------------------------------------------------------------------------------
10. 对于正则表达式，空集是并运算的单位元、连接运算的零元，空串是连接运算的单位元
11. 若L和M都是正则语言，则L和M的并、交、差也是
12. 若L是字母表T上的正则语言，则~L=T*—L也是
13. 若L是正则语言，则L的反转也是
14. 若L是字母表T上的正则语言，h是T上的一个同态，则h(L)也是正则的
15. 若h是字母表A到字母表T的同态，且L是T上的正则语言，则逆同态h^-1(L)也是正则的
因为一个整数p，若检测为合数，这永远是真命题；而检测为素数，这命题只以较大概率成立。 可构造一种NP检测算法，步骤如下：
1. 猜测p（位长度n）的因子列表｛p1,p2,…pi｝，这是非确定的，每个分支耗时O(n)
2. 验证p1*p2*…pi？=p-1，耗时不超过O(n^2)
3. 若各因子乘积等于p-1，则用当前算法递归验证每个因子都是素数
4. 随机选择p最小剩余系内的一个数x，计算x^((p-1)/q) （q遍历上述列表经过步骤3验证过的素因子）是否都不同余于1模p，若是则必有x^(p-1)同余于1模p，则由指数整除p的欧拉数及费马小定理，知p为素数，考虑到有少量的合数也满足费马小定理，故需多次选择x重复验证，选择个数最多为log(p)
分析：本算法涉及的数论定理——设p是奇素数，p-1的所有素因子是q1,q2,…qs，那么g为原根的充要条件是，g^((p-1)/qj)不同余1模p，j=1,2…,s
结论：第3步可以看成递归调用树，每个顶点为待检测整数，其每个子结点为一个因子，则最多n层，每层至多耗时O(n^4)，所以每个路径即检测p是否素数的非确定任一分支中，总耗时O(n^5)。 2002年，印度科学家发现素检测确定性多项式时间算法，于是从NP前进到了P
摘要: 1. 整数r>s>0，(r, s)=1，2∤r+s，x=r^2-s^2, y=2rs, z=r^2+s^2，求证(x, y)=1，(y, z)=1
证明：由2∤r+s（r与s必一奇一偶）知2∤r-s，故2∤r^2-s^2，以及2∤(r+s)(r+s)。又1=(r, s)=(r+s, r)=(r+s, s)=(r+s, rs)。同理得1=(r, s)=(r-s, rs)，故1=((r+s)(r-... 阅读全文
1. 三条定律：交换律、结合律、吸收律（对于半格是幂等律），吸收律包含了幂等律
2. 上下界：交半格每对元素都有唯一最大下界，并半格每对元素都有唯一最小上界，格每对元素都有唯一最大下界和唯一最小上界
3. 格定义一个偏序，偏序有三个性质：自反性、反对称性、传递性
4. 格与偏序的关系：每个格对应一个偏序，但不是所有偏序都对应一个格，要满足每对元素都有唯一最小上界和（或，对于半格）唯一最大下界。如果集合中的任何一个子集（包括空集）均存在最小上界和最大下界，那么对应一个完备格
5. 任何元素有限的格都是完备格，格中的交运算和并运算对于其定义的偏序来说是单调的
6. 格的乘积、和、提升、映射仍然是格，利用这个性质，可以在已有格的基础上增量地构造描述能力更丰富的格，这种技术称为论域精化，是提高程序静态分析精度的重要指导思想之一
【命题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。可以看到用反证法证明后一个结论时，直接支配结点的唯一性很关键
摘要: 【性质】
1. 判定两个完全格L和M能否构成伽罗瓦连接，即抽象化函数α: L—>M是否完全加性的，或具体化函数γ: M—>L是否完全乘性的
2. 构造抽象化函数和具体化函数，即对于一个Galois连接（L, α, γ, M），给定α可通过γ(m) = ⊔{l | α(l) ⊑ m}确定γ，这对于所有m成立，且由于&... 阅读全文
记输出为[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，即p-1整除q，q为p-1的素因子
2. 1<g<=p-1，随机选取，测试它的q次幂是否等于1 mod p，若不等于则重新选取，直到等于
3. 上面选定的g，遍历1到q的幂模p，就得到G的各元素
数学基础：一个有限群，对每个元素它的阶整除群的阶，它的群阶幂次方等于单位元；一个有限循环群，它的生成元个数为群阶的欧拉数，若群阶是素数，则所有非1的元素都是生成元
结论：这种计算子群的方法由于保证阶为素数且只要超过160位长，就可避免针对阶为合数的质因子分解并利用中国剩余定理求离散对数的已知最好攻击，具有中长期安全强度
定理：令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盒及列混合操作可逆
摘要: OpenCASCADE曲面交线分类
eryar@163.com
Abstract. OpenCascade classify the intersection line between two surfaces. A intersection line may be either geometric: line, circle, ellipse, parabola, hyperbola as ... 阅读全文
摘要: 性能提升-BVH层次包围体
eryar@163.com
Abstract. OpenCASCADE provides BVH to achieve high performance in AIS of visualization module. To understand BVH usage will help us to understand many code of openc... 阅读全文
摘要: 性能提升-空间二叉查找树
eryar@163.com
Abstract. OpenCASCADE provides NCollection_UBTree to achieve high performance search overlapped boxes. The algorithm of unbalanced binary tree of overlapped bounding... 阅读全文
摘要: PipeCAD ISO 图框及文字配置
eryar@163.com
Abstract. PipeCAD IsoAlgo supports user to define backing frame instead of program standard drawing frame. And can put pipeline attribute as positioned text i... 阅读全文
Licensecc-C++ License Manager
eryar@163.com
Licensecc: a C++ software license manager。使用Licensecc可以给开发的软件加上保护，限制软件的使用。通过授权控制来限制软件的使用，也可以限制软件的使用时间，及限制软件在指定机器上运行。Licensecc是基于BSD协议开源的软件授权系统用来帮助你的软件闭源。Licensecc使用C++ 11开发，支持跨平台使用。
Licensecc主要功能列表：
Issue a “demo” license with only expiry date.
支持试用许可功能：不绑定具体的机器，但是限制使用时间或者其他限制。
Licenses linked to “physical” hardware id
绑定机器的许可功能：让软件绑定机器硬件，只能在授权的机器上运行。
时间限制
硬盘ID限制
IP地址限制
CPU限制
对于一些小的软件，可以使用licensecc来加上license对软件进行保护。