看板KS87-308
标 题Re: 再问一下 a^-1 mod p = ?
发信站松涛情怀与斑城故事 (Sun Feb 17 21:13:01 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的(最小)公因数
--
※ Origin: 松涛情怀与斑城故事 <khhs.twbbs.org>
◆ From: ks34-16.dialup.seed.net.tw