大技きましたなw 引き算すると負数。絶対値にしても、多分7でわれるか？自分勝手にカッコをつけても、えーと・・・87・・・3でわれちゃうか。 5 と これくらいだと原始根のありがたみも(計算機がやってくれる前提のもので)わかる気がしますの。
しかし実際はpで割ったあまりだけに注目すればいいので、そんなに計算は大変ではないんですけどね。 5^100 % p = 5^64*5^32*5^4 % p = (5^64 % p)*(5^32 % p)*(5^4 %p)%p みたいな？ なのでまず5の冪を全部計算しといて、それを掛け算すればいいわけです。 その掛け算のどの段階でもpを超えたらp引いても問題ないから、オーバフローもないですし
余談） 4n+1の素数は平方数の和で表せると言うことで計算してみました。 10546^2 + 3081^2 計算方法は本を見て行ったけど、これは思いつかない。 (uA+vB)^2 + (vA-uB)^2 = (u^2 + v^2)(A^2 + B^2) を利用して、どんどん計算していくんですが、u, vをいかにうまく選ぶかのアルゴリズムが実に巧妙。