#53: 題解


Ching367436 (Ching367436)

School : 一中
ID : 41
IP address : [172.68.62.162]
Last Login :
2021-04-08 09:15:31
c030. VII. $電電^{的指數^{的指數}}$ -- 臺中一中電腦資訊研習社 | From: [162.158.119.165] | Post Date : 2021-01-30 07:31

Fermat's little theorem:


if gcd(a, p) = 1

then

$$ a^{p-1} \equiv 1 \mod p $$


let $y^z = t$, $t = k(p-1)+b$

so $b=y^z\%(p-1)%$



$x^{y^z} \mod p$
$\equiv x^t$
$\equiv (x^{p-1})^{k} \times x^b$
$\equiv (1)^{k} \times x^b$
$\equiv x^b$
$\equiv x^{(y^z\%(p-1))}$



 
ZeroJudge Forum