分数模运算几种方法总结

2019-04-13 13:49发布

站内文章 / 模拟电子
10445 0 1355
对于分数a/b,模m,求a/b(mod m)  (b,m互素) 设k=a/b  (mod m)       0 则 kb=a  (mod m)

利用Extended Eucluid 扩展欧几里德算法求解 举例2/4 (mod23) 转换为一般形式为 4k=2 (mod23)
输入 :                          分子=2                          分母=4
                         模=23 流程:
初始化 X=(X1,X2,X3)=(1,0,23) Y=(Y1,Y2,Y3)=(0,1,4)
判断条件 Y3==0  返回无逆元                   Y3==2  返回逆元Y2 第一轮迭代:                 Q=23/4=5                 T=(T1,T2,T3)=(1-5*0,0-5*1,23-5*4);                 X=Y=(0,1,4)                 Y=T=(1,-5,3) 判断判断条件 第二轮迭代                  Q=4/3=1                 T=（0-1*1，1-（-5）*1，4-1*3）=（-1，6，1）                 X=Y=(0,1,4)                 Y=T=(-1,6,1) 判断判断条件 第三轮                Q=4/1=4;                 T=(4,-23,0)                  X=Y=(-1,6,1);                  Y=T=(4,-23,0); 判断判断条件
                发现没逆元 ------------------------------------------------------------------------------------------------------------------ 但是我们从上述计算过程中可以发现所有a/4存在逆元的的数为  4/4,3/4,1/4 但是2/4的乘法逆元应该为12 下面可得，但是这里求不出，可见欧几里德扩展方法是 针对真分数的。 2/4=1/4+1/4应该为12。




其他方法               一般形式为 4k=2 (mod23)              4k=2+23*x 
             x=(4k-2)/23
            由于k的取值不可能很大，所以我们用穷举法，令k=1,k=2,k=3,k4,-------  求能使x整除
  k=1   不行   余   2
k=2 不行               6
k=3,4,5都不行      10   14  18
k=6   不行               22
k=7                          3 8                               7 9                                11 10                             15 11                              19 12                               23
k=12                            0















热门文章