5864^5863÷29 の余りを求めよ。
という問題を中学生に出され、

5864÷29=202…6　だから、
6^5863÷29 の余りと同じ。

(以下 A÷Bの余り　を　A mod B で表記します)
6^0 mod 29 = 1
6^2 mod 29 = 7
6^3 mod 29 = 13
〜
6^11 mod 29 = 9
6^12 mod 29 = 25
6^13 mod 29 = 5
6^14 mod 29 = 1

余りのパターンが、乗数が14増えた時に一周してる事がわかるので、
6^5863 mod 29
= 6^(418*14+11) mod 29
= 6^11 mod 29
= 9

という答えに至ったのですが、手計算でやると、
6^0mod29〜6^14mod29を求めたりしなければならず
10分前後かかってしまいます。

もっと手際のいい方法があるようなのですが、
ご教授願えませんでしょうか？