无聊中测试了一个关于a^p mod n这样的一个公式

shikang999

1、因为自己一直想写一个关于a^p mod n这样的算法公式,其中p是大于30位的大数据,一直写不出一个好算法,无意中把上面公式一改,写成如下的公式:
a^p mod n=(a mod n)^(p\n+p mod n) mod n【其中p\n表示p除以n取整数部分,经常写程序的应该不陌生】
2、如果上面那个公式成立就漂亮了,呵呵,可惜那公式是不成立的,不过问题的关键是我经过对10组测试数据发现一个很有趣的现象,在测试的数据中有超过半数的数据是满足上面的公式的。
3、其中10组数据中每组测试1000个表达式,每个表达式里的a、p、n都在[1,1000000]中随机生成
4、在10组数据中,不满足上面公式的比例分别为
445/1000、447/1000、445/1000、457/1000、442/1000、443/1000、452/1000、477/1000、453/1000、461/1000
5、下面给部分算例【a^p mod n=正确值|上面新公式计算得的值】
407241^422067 mod 185696 = 39481|68105
798498^465092 mod 267310 = 64606|119882
3940^513326 mod 396054 = 11416|267166
914865^372277 mod 63564 = 48717|33297
516621^328884 mod 150747 = 10818|104721
212499^428361 mod 227783 = 204934|196978
807947^804129 mod 778940 = 619927|719629
111131^92399 mod 35728 = 24051|7195
190151^710715 mod 90939 = 12731|43931
957912^660053 mod 478714 = 15690|410500
472001^990550 mod 660962 = 481213|77563
515574^540674 mod 18690 = 5616|12006
';*************************************
18910^210780 mod 521930 = 413650|413650
69268^224479 mod 822035 = 358372|358372
892867^290010 mod 675349 = 555822|555822
831978^909973 mod 874729 = 651424|651424
499997^6425 mod 114878 = 56051|56051
145128^385229 mod 599491 = 117868|117868
2842^371361 mod 890492 = 808584|808584
39173^99618 mod 259195 = 96164|96164
521535^112443 mod 531893 = 486724|486724
508804^404685 mod 536133 = 132274|132274
566445^194923 mod 649131 = 159339|159339
148950^132358 mod 675863 = 45600|45600
989013^330274 mod 602517 = 311862|311862
263695^420620 mod 501803 = 235525|235525
6、本文纯属数学娱乐。我要睡觉了!