简单连分数攻击RSA的迭代次数分析

     摘要: 【适用前提】大整数N=pq的素因子p<q<2p，解密指数d<(1/3)N1/4 【攻击方法】       1）用欧几里得算法计算e/N的各个渐近分数ki/di，i>=1，直至di>=(1/3)N1/4，记录此时的i为m。令i=1        2）计算T=(e*di-1)/ki...  阅读全文

2024-04-04 18:19 作者: 春秋十二月【评论:0】【阅读:102】 

有限循环群的结构及生成元的判定

群结构  
  定理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

2024-03-20 22:49 作者: 春秋十二月【评论:0】【阅读:153】 

混合线性同余发生器的引理验证

     摘要: 混合线性同余发生器（MLCG）             Xn ≡ αXn-1 + c mod m    0<X0, α, c<m，X0为种子，n=1、2、3... 定理 如果下列3个条件都满足，则 MLCG达到满周期(即周期d=m)    ...  阅读全文

2024-03-12 17:30 作者: 春秋十二月【评论:0】【阅读:177】 

Blum数的基本定理及应用

     摘要: 【定义】设整数N=P×Q，P与Q皆为素数，如果P≡Q≡3 (mod4)，则N为一个Blum（布卢姆）数 【定理】设N为Blum数，N ∤ d，若同余方程x2≡d (mod N)有解，则d的平方根中有一半的Jacobi符号为1，另一半Jacobi符号为-1；且仅有一个平方根为模N的二次剩余     证明： &...  阅读全文

2024-02-25 23:29 作者: 春秋十二月【评论:0】【阅读:224】 

关于（零知识）计算复杂性的总结

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

2024-02-09 22:19 作者: 春秋十二月【评论:0】【阅读:120】