分数求模(取余)过程 乘法逆元

《分数求模(取余)过程 乘法逆元》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、分数的模运算在ECC加密算法中需要用到对分数的模运算，但大多的资料只给结果没有给计算过程，就连初等数论书上面也找不到计算 方法，搜索了一下，终于在网上找到了相关资料，用的思路其实还是整数模运算的，直接copy下来下面是“分数”模运算的定义：b,m互质（互为素数）k=a/b(modm)<=>kb=a(modm)这里求x=1/17(mod2668)<=>17x=1(mod2668)<=>17x=2668k+1（k∈整数）取合适的k使得17

2、(2668k+1)【应该是17能被(2668k+1)整除,也即17xmod2668

3、=1】这里刚好17

4、(2668+1)所以k=1,x=(2668+1)/17=157当然，当k=1+17n时，x=(2668+17·n·2668+1)/17=157+2668n也符合条件（n任意整数）但如果限定2668>x>0，x是唯一的。分数求模（取余）过程[原创2008-03-2020:13:27]  字号：大中小貌似分数是这样取余的，好好学习，天天向上！计算a/x(modn)a/x(modn)=a*x^-1(modn)这里的d就相当于x，f相当于n计算1/x mod n=x^(-1) mod n就是求y，满足：y

5、x = 1 mod ny是有限域F(n)上x的乘法逆元素可用扩展的欧几里得算法求乘法逆元int ExtEnclid(int d,int f) k=x3/y3比如5/3=1；15/4=3{        int x1,x2,x3,y1,y2,y3,t1,t2,t3,k;if(d>f) d=d+f-(d=f);  //交换d和f使得d

6、=0)       return 0;       //没有逆元,gcd(d,f)=x3                if(y3==1)       return y2;      //逆元为y2,gcd(d,f)=1                k=x3/y3;                t1=x1-k*y1, t2=x2-k*y2, t3=x3-k*y3;                x1=y1,x2=y2,x3=y3;                y1=t1,y2=t2,y3=t3;        

7、}}int main(){        int d,f,res;        printf("you can try d=550 f=1769, d^-1 = 550, press ctrl+Z to quit...");        printf("intput the d and f value:");        while(scanf("%d%d",&d,&f)==2)        {                printf("Enclid : gcd(%d,%d)=%d",d,f,

8、Enclid(d,f));                res=ExtEnclid(d,f);                if(res==0)      printf("Not Exist the d^-1");                else                        if(res>0)       printf("ExtenderEnclid : d^-1 = %d ,                                          %d * %d = 1 

9、mod %d",res,d,res,f);                        else                        {                                printf("ExtenderEnclid : d^-1 = (%d) ,                                        %d * (%d) = 1 mod %d",res,d,res,f);                                printf

10、("ExtenderEnclid : d^-1 = %d , %d *                                           %d = 1 mod %d",res+f,d,res+f,f);                        }        }        return 0;}用扩展的欧几里德算