模板
    1. 空基类优化
    2. 元编程技术
        2.1. 选择API
        2.2. 计算最值
        2.3. 类型选择
    3. 封装GCC原子操作
    4. 定制类对象的内存管理

算法
    1. 排序
        1.1. 改进的快速排序
        1.2. 原位统计排序     
    2. 多叉树
        2.1. 深度优先存储
        2.2. 迭代器的设计
        2.3. 前序遍历
        2.4. 后序遍历
        2.5. 兄弟遍历
        2.6. 叶子遍历
        2.7. 深度遍历 
    3. 优先级队列
        3.1. 原理
        3.2. 内幕
        3.3. 外观
    4. RSA加解密的证明
    5. DSA数字签名的推导
    6. 基于中国剩余定理优化RSA解密推论的证明
    7. 总结AES加密涉及的数学定理
    8. 为什么素检测存在概率多项式时间算法
    9. Blum数的基本定理及应用

GUI 
    1. MFC中的WM_COMMAND传递
    2. ATL和WTL中的消息反射
    3. 工作线程与消息循环
    4. 多窗口的组合与分离
        4.1. 接口
        4.2. 实现

跨平台
    1. 用户态自旋锁
    2. 互斥锁
    3. 信号量
    4. socket管道
    5. 锁框架的设计与实现

网络
    1. 运用状态机异步接收变长包
    2. 基于OpenSSL实现的安全连接
    3. TCP/IP FAQ
        3.1. 链路层、网络层和传输层
        3.2. 插口层和应用层
    4. Linux套接字与虚拟文件系统
        4.1. 初始化和创建
        4.2. 操作和销毁
    5. Linux ICMP消息的产生与转换
    6. nginx iocp
        6.1. tcp异步连接
        6.2. udp异步接收
        6.3. scm服务控制
    7. TCP分组丢失时的状态变迁
    8. 基于ENet实现可靠UDP通信的同步模型

Shell应用
    1. 自动生成并安装服务脚本
    2. nginx升级与恢复
    3. 使用awk定位反汇编输出
    4. 自动化批量编译

私钥分组加密  

  

  
   上图的证明中，r^(j)两两不同的概率计算是关键，下面给出详细过程
       
  Construction 5.3.9一次只能加密与密钥等长的明文，如果要加密更长的明文，怎么办？一个简单直接
  的方法是将明文分成多个大小为n的块，对每个块调用上述加密步骤，那么就得到形如下的密文块序列
       
  密文块序列从Proposition 5.3.10的证明中可知是计算不可分辨的，满足「多组消息安全性」。但对于解密
  需要存储每一块的随机数，因此比较占空间，所以衍生出下面更高效的方案Construction 5.3.12

定义
    

Berlekamp分解算法
    

AES有限域
   

  不可约性证明
       

  非本原性验证
      

  找出本原元
      

  不可约多项式个数
       

线性移位寄存器m序列
     根据参考文献1知线生移位寄存器产生m序列的充要条件是特征多项式f(x)为本原多项式。而确立有限域上的本原多项式，主要有两种方法：
      一种方法是根据F_q上所有次数为n的本原多项式的乘积正好等于割圆多项式Q_e，其中e=qⁿ-1，从而所有次数为n的本原多项式可以通过分解Q_e得到。
      另一种方法是通过构造本原元再求本原元的极小多项式，先素因子分解qⁿ-1=p₁p₂...p_k，如果对每一p_i都有ord(α_i)=p_i，那么α=α₁α₂...α_k的阶就是qⁿ-1，
      因此是F_q上的本原元，则f(x)=(x-α)(x-α²)...(x-α^r)，r=qⁿ-1（因为α是本原元，所以n是使α^{q^n}=α成立的最小正整数）。
   
    求解本原多项式
       假设线性移位寄存器的级数为4，这里使用上述二种方法求F₁₆上的本原多项式，过程如下
       分解割圆多项式法
          

        
         
   
  本原多项式个数
        

   m序列示例
       

【适用前提】大整数N=pq的素因子p<q<2p，解密指数d<(1/3)N^1/4

【攻击方法】 
     1）用欧几里得算法计算e/N的各个渐近分数k_i/d_i，i>=1，直至d_i>=(1/3)N^1/4，记录此时的i为m。令i=1  
     2）计算T=(e*d_i-1)/k_i，若T不为整数则转到4），否则转到3）  
     3）解方程f(x)=x²-(N-T+1)x+N=0的根，如果有正整数根且两个根皆小于N，则输出p、q，并返回成功。否则转到4）  
     4）递增i，若i<m则转回2），否则返回失败
   该方法即Wiener算法用到了关于连分数的一个定理：若α为任一实数，有理数p/q适合|α-(p/q)|<1/(2q²)，则p/q必为α的某一渐近分数。证明详见参考文献[2]。
   由定理可知攻击方法是可行的，必能找到使f(x)=0有合理解的某渐近分数。下面证明：攻击迭代次数的上界为

【证明】
     


【例子】N = 9449868410449，e = 6792605526025，d<(1/3)N^1/4≈584，试分解N
     

参考文献
     [1] 公钥密码学的数学基础  王小云、王明强、孟宪萌
     [2] 算法数论                   裴定一、祝跃飞

群结构  
  定理1：若G为一个循环群，则G内每个满足ord(α)=s的元素α都是拥有s个元素的循环子群的生成元
  证明：
      

  定理2：若G为一个阶为n的有限循环群，g为对应的生成元，则对整除n的每个整数k，G都存在一个唯一的阶为k的循环子群H。
    这个子群是由g^n/k生成的。H是由G内满足条件α^k=1的元素组成的，且G不存在其它子群
  证明：
     

  推论：从上述两定理可知有限循环群、子群及生成元的关系如下
      
  例子：依据上述推论得如下
      

生成元判定算法
  输入：循环群G、某子群的阶k  
    1）若k=1，则直接输出e。否则转到2）
    2）随机从G-{e}中选择一元素x
    3）若x^k≠e，则转回2）。否则若k为素数，则跳到5）；若k为合数，则转到4）  
    4）遍历整除k的真因子d，若x^d=e，则转回2）    
    5）输出x

混合线性同余发生器（MLCG）      
      X_n ≡ αX_n-1 + c mod m    0<X₀, α, c<m，X₀为种子，n=1、2、3...

定理 如果下列3个条件都满足，则 MLCG达到满周期(即周期d=m)
     (1) (c, m)=1，即 c、m互素
     (2) 对 m的任一素因子p，有α≡1 mod p
     (3) 如果4|m，则 α≡1 mod 4
  该定理的证明在参考文献[2]中证明并用到如下两个引理：
  引理5 设p为素数，α∈Z⁺且p^α>2，如果 x=1(mod p^α)，x≠1(mod p^α+1)；则x^p=1(mod p^α+1)， x^p≠1(mod p^α+2)
    该引理给出了求一个整数的阶的判别方法，是理解MLCG周期等于m的充要条件之关键。
    本文阐述为什么p是使x^p=1(mod p^α+1)成立的最小正整数，以及一般情形m=p^w(w≥1)是使x^m=1(mod p^α+w)成立的最小正整数；为什么前提条件是p^α>2。

    ◆ 先论证不存在一个整数1≤b<p使得x^b=1(mod p^α+1)成立
       
    ◆ 再证不存在一个整数1≤b<m使得x^b=1 (mod p^α+w)成立
       
     其实这里当α=1(mod 2)且α≠1(mod 4)，结论也是成立的。比如取α=3，m=16，则 (3¹⁶ -1)=81⁴ -1=(-15)⁴ -1=-15×-7×-7 -1=-15×-15 -1=9×-7 -1=0(mod 32)，
     即(3¹⁶ -1)/(3-1)=0(mod 16)。但只有当α=1(mod 4)时，m才是使结论成立的最小正整数。论证如下
         

参考文献    
     [1] 现代密码学第4版 杨波    
     [2] 混合线性同余发生器的周期分析 张广强、张小彩

【定义】设整数N=P×Q，P与Q皆为素数，如果P≡Q≡3 (mod4)，则N为一个Blum（布卢姆）数

【定理】设N为Blum数，N ∤ d，若同余方程x²≡d (mod N)有解，则d的平方根中有一半的Jacobi符号为1，另一半Jacobi符号为-1；且仅有一个平方根为模N的二次剩余
    证明：
    

【推论】设N为Blum数，N=P×Q，令
    
   证明：
    

【例子】由定义知N=21=3×7为Blum数，则相关乘法群、二次剩余子群、Jacobi集合如下
   


【应用一】Blum-Goldwasser公钥加密
      
    解密正确性是因为步骤1用到了欧拉定理及求平方根的如下算法，步骤2用到了中国剩余定理

       
       从上可得x=s^(P+1)/4 mod P或x=P-s^(P+1)/4 mod P，因(-1)^(P-1)/2等于-1 mod P，故前者为模P的二次剩余。从加密流程可知{s₁,s₂,...,s_n+1}正是模N二次剩余类的子集。
    所以从密文中r=s_n+1求它的(p+1)/4次幂、(q+1)/4次幂，迭代n次就得到了s₁模p的解、s₁模q的解，又因p、q、n在迭代中不变，故用欧拉定理预计算d_p mod (p-1)、d_q mod (q-1)。
    另一种（不太高效而直接的）解密如下
       
    另加密与明文异或的那部分实际是伪随机比特发生器，因为平方模N构成二次剩余类上的单向陷门置换，其最低有效位是核心断言，故从s_i+1求出lsb(s_i)是不可行的。简单证明如下
       
      由于均匀选择一个种子s₀，所以为概率加密，进而由可证明安全定理（每个概率公钥加密都是多项式安全的，及每个多项式安全的公钥加密都是语义安全的）知满足IND-CPA安全性
    易知IND-CCA2安全性是不满足的，因为敌手可用如下攻击方法获取明文：已知目标密文C=(r, m⊕σ₁σ₂⋯σ_n)，构造新密文C’=(r, m’⊕m⊕σ₁σ₂⋯σ_n)，将C’发给解密预言机得到m’’，则m=m’’⊕m’。
    由于加密产生的r与σ₁σ₂⋯σ_n都是伪随机的，所以密文(r, x⊕σ₁σ₂⋯σ_n)的分布是伪随机的，在目标密文前的解密询问会得到若干密文与明文对，无论怎么构造一对明文，任选其一加密得到的密文都不可区分。因此IND-CCA1安全性是满足的

【应用二】无爪函数/置换构造
      
      
    如上构造用到Blum数的上述推论，及基于大整数因子分解的困难假设。这里主要解释下为什么由两个Jacobi符号不同的平方根可计算大整数的素因子
      

【应用三】伪随机数发生器
                X_n+1=X_n² mod N      n=0、1、2...，X₀为种子
     显然种子不为1。若为一个非二次剩余，则从X₁开始就为二次剩余子群的元素，但最后必回到X₁而非X_0；若为二次剩余，则为了安全需要考究随机数数列的周期是否整周期（二次剩余子群的大小减1）。
  下面具体分析周期。先举例几个很小的Blum数
      
     从上面例子可以发现，由二次剩余子群构成的随机数数列不一定是整周期的，对于N=33无论种子怎么选，都是整周期4；对于N=57若种子选-8或7则周期为2，选其它则为6。
  现在一般化考虑，什么情况下才产生整周期？论证如下
       

经典的复杂性关系 
 P是多项式时间确定型图灵机可识别的语言类，NP是多项式时间非确定型图灵机可识别的语言类，NPC表示NP完全问题类，coNP表示NP的补，coNPC表示NPC的补。确定型图灵机是一种从不选择移动的特殊的非确定型图灵机，故自然有P属于NP

     
 
 coNP、coNPC的定义之集合表述
      
 上面顶部的图有个假设前提是：coNPC不属于NP，即我们相信NP完全问题的补都不属于NP。但当P=NP或NP=coNP时，可以发现coNPC属于NP

 ◆ 为什么coNPC属于coNP？
   

 ◆ 为什么NPC 不属于coNP？
   

 ◆ 为什么P属于coNP?
   

 ◆ 当P=NP时，为什么NP=coNP？
   
 ◆ 当NP=coNP时，为什么NPC=coNPC？