随笔-155  评论-223  文章-30  trackbacks-0
通用算法
   先摘抄参考文献[1]中的算法流程如下
   

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

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

   例子测验
      
      

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


参考文献
   [1]  算法数论   裴定一、祝跃飞
posted on 2024-08-30 22:22 春秋十二月 阅读(264) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理