■剰余の計算(その30)

[Q]2^5293 mod 5293,すなわち,2^5293を5293で割ったときの余りを求めよ.

===================================

 反復2倍乗法を応用した反復平方による累乗法を用いると,

  5293=5292=1+2^2+2^3+2^5+2^7+2^10+2^12

  2^5293=2^(1+2^2+2^3+2^5+2^7+2^10+2^12)=2・2^(2^2)・2^(2^3)・2^(2^5)・2^(2^7)・2^(2^10)・2^(2^12)

2^2=4,2^2^2=16,2^2^2^3=16^2=256,

2^2^2^4=256^2=2020,

2^2^2^5=2020^2=4790,

2^2^2^6=4790^2=4238,

2^2^2^7=4238^2=1495,

2^2^2^8=1495^2=1379,

2^2^2^9=1379^2=1454,

2^2^2^10=1454^2=2209,

2^2^2^11=2209^2=4828,

2^2^2^12=4828^2=4505  (mod5293)

以上より

2^5292=16・256・4790・1495・2209・4505=2890  (mod5293)

2^5293=5780=487  (mod5293)

===================================