论证有限域上平方根的求解

通用算法

   先摘抄参考文献[1]中的算法流程如下
   

   正确性分析
      下面证明以上算法用到的事实结论，提炼为如下几个引理
      
     

   算法构造思想
         用到二次剩余知识，即一个待求平方元ɑ可以且只能表示为两个平方因子的乘积，其中一因子为任意随机选取的非平方因子β的偶数幂，
      另一因子为叶子群H的一元素r，H作为陪集划分根群（有限域乘法群）得到β生成的集合即商群G/H的一个代表元系。这样一来，将开方转化为β与r的乘方运算，
      迭代的过程就是为求那个具体的代表元β^e中的指数e（注意e必为偶数），从G_s-2到G₀=H，迭代结束后r被唯一确定，r的开方等于r的(t+1)/2次方（因为t是H的阶且为奇数，r^t+1=r）

   例子测验
      
      

特殊算法
   当q是素数且q≡3(mod 4)时，存在更快的算法及测验如下 

   

参考文献

   [1]  算法数论   裴定一、祝跃飞

2024-08-30 22:22 作者: 春秋十二月【评论:0】【阅读:51】 

求解离散对数问题的Terr算法

     摘要: 基本原理          再来看Terr算法用到的如下定理      定理 （基于参考文献1改正后的描述）对每一正整数t，存在唯一确定的一组整数k和j，0<=k<j，使得t=Tj+1-k，其中T0=0，Tn=Tn-1+n-1，n>=1     ...  阅读全文

2024-08-15 22:35 作者: 春秋十二月【评论:0】【阅读:225】 

简单私钥加密构造的验证及安全性分析

     摘要: 私钥分组加密            上图的证明中，r(j)两两不同的概率计算是关键，下面给出详细过程             另外两个分布统计的不同意味着计算可分辨（反之则计算不可分辨），亦即r(j)至少两个相同的概率。  &nb...  阅读全文

2024-06-29 17:00 作者: 春秋十二月【评论:0】【阅读:387】 

二元有限域及其扩域上的计算

     摘要: 定义      Berlekamp分解算法      AES有限域       不可约性证明           非本原性验证          找...  阅读全文

2024-05-16 13:41 作者: 春秋十二月【评论:0】【阅读:663】