Last 5 digits

$13^5 \equiv 71293 (100000)$

$71293^2 \equiv 13^{10} \equiv 91849 (100000)$

$91849^2 \equiv 13^{20} \equiv 38801 (100000)$

$38801 \times 71293 \equiv 13^{25} \equiv 39693 (100000)$

$39693^2 \equiv 13^{50} \equiv 34249 (100000)$

$34249^2 \equiv 13^{100} \equiv 94001 (100000)$

$94001 \times 39693 \equiv 13^{125} \equiv 81693 (100000)$

$81693^2 \equiv 13^{250} \equiv 46249 (100000)$

$46249^2 \equiv 13^{500} \equiv 70001 (100000)$

$70001^2 \equiv 13^{1000} \equiv 40001 (100000)$

$40001^2 \equiv 13^{2000} \equiv \fbox {80001} (100000)$

I don't see any shortcut here. If anyone has a more elegant solution, please tell me.