看板KS87-308
標 題Re: 再問一下 a^-1 mod p = ?
發信站松濤情懷與斑城故事 (Sun Feb 17 22:48:31 2002)
轉信站Ptt!松濤情懷與斑城故事!khhsbbs
> ※ 引述《Isaac (加油～～～)》之銘言：
> > ※ 引述《showermi (累死了><)》之銘言：
> > > 我猜答案是 1111112/2=555556 如果B一樣是2的話`~~~
> > > 對不對ㄚ!?
> > 不是ㄝ 呵呵 我是不知道怎麼算～
> > 不過如果P= 1111111, B=2...用程式跑出來是832501...
> 路人插花......
> --
> 應是555556 用電腦跑會因數值太大而產生錯誤 況且2*832501除以1111111餘數不是1
> (如果是用pow這種函數的話)
> 若想用前面提到的算法 則
>
> 1111111=239*4649 兩者都是質數
> 則B^[238和4649的公因數]=1 mod 1111111
> 故B^-1=B^[79016-1] mod 1111111=555556
> 其中79016是238和4649的(最小)公因數
> --
如果這樣算...那若 P = 21 = 3 x 7
則 B^6 = 1 mod 21
所以 B^-1 = B^6-1 mod 21 = 11
但 B^-1 = B^21-1-1 mod 21 = 2
不就不符合ㄌ...
--
我程式邊跑邊mod 應該沒有溢位的問題...
--
※ Origin: 松濤情懷與斑城故事 <khhs.twbbs.org>
◆ From: 61-217-86-38.HINET-IP.hinet.net