不可约多项式判别算法的改正

原本算法

    摘抄参考文献1中附录的算法流程如下

    

例子测验
   
    

改正后的算法

       改正之前，先理清原本算法判别不可约多项式所用的原理。其原理是若f(x)可约，当且仅当存在次数i<=d=[deg(f(x))/2]的不可约因子g(x)，而此时gcd(x^{q^i}-x, f(x))≠1。
   根据参考文献2（详见如下定理），x^{q^i}-x是所有i次不可约多项式的乘积，因此它必定包含g(x)而与f(x)存在公因子。不可约判别算法的思想应该是遍历次数1到d的所有不可约多项式
 （没必要检测大于d的不可约多项式，因为若f(x)可约则其分解因子中必定存在不大于d的不可约多项式），检测输入多项式与它们是否存在公因子。所以这个原理是正确的，只是实现不对，
   略作改正如下（类c语言描述）
   

重新测验
   

   

参考文献

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

   [2] 代数学基础与有限域   林东岱

2024-09-07 23:07 作者: 春秋十二月【评论:0】【阅读:207】 

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

通用算法

   先摘抄参考文献[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】【阅读:305】 

求解离散对数问题的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】【阅读:556】