分?jǐn)?shù)求模(取余)過程 乘法逆元

《分?jǐn)?shù)求模(取余)過程 乘法逆元》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、分?jǐn)?shù)的模運算在ECC加密算法中需要用到對分?jǐn)?shù)的模運算，但大多的資料只給結(jié)果沒有給計算過程，就連初等數(shù)論書上面也找不到計算 方法，搜索了一下，終于在網(wǎng)上找到了相關(guān)資料，用的思路其實還是整數(shù)模運算的，直接copy下來下面是“分?jǐn)?shù)”模運算的定義：b,m互質(zhì)（互為素數(shù)）k=a/b(modm)<=>kb=a(modm)這里求x=1/17(mod2668)<=>17x=1(mod2668)<=>17x=2668k+1（k∈整數(shù)）取合適的k使得17

2、(2668k+1)【應(yīng)該是17能被(2668k+1)整除,也即17xmod2668

3、=1】這里剛好17

4、(2668+1)所以k=1,x=(2668+1)/17=157當(dāng)然，當(dāng)k=1+17n時，x=(2668+17·n·2668+1)/17=157+2668n也符合條件（n任意整數(shù)）但如果限定2668>x>0，x是唯一的。分?jǐn)?shù)求模（取余）過程[原創(chuàng)2008-03-2020:13:27]??字號：大中小貌似分?jǐn)?shù)是這樣取余的，好好學(xué)習(xí)，天天向上！計算a/x(modn)a/x(modn)=a*x^-1(modn)這里的d就相當(dāng)于x，f相當(dāng)于n計算1/x?mod?n=x^(-1)?mod?n就是求y，滿足：y

5、x?=?1?mod?ny是有限域F(n)上x的乘法逆元素可用擴(kuò)展的歐幾里得算法求乘法逆元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;}用擴(kuò)展的歐幾里德算