IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
  • 登录 注册

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

    春秋十二月发表于 2024-08-30 14:22:00
    love 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]  算法数论   裴定一、祝跃飞


    春秋十二月 2024-08-30 22:22 发表评论


沪ICP备19023445号-2号
友情链接