I've just started a cryptography course, so i am not experienced at all how to calculate such big numbers. Clearly, i can't use a calculator, because the number is too big, so i have to calculate it by hand.
Since $101$ is a prime number, i think i should use here Fermat's little theorem. Found some example and tried to solve it this way, but i am totally not sure, if it is correct and if my approach must be this one.
Calculate $5^{3^{1000}}\bmod 101$.
First of all i think i should calculate $3^{1000}\bmod 101$. From Fermat's little theorem i get to $3^{100}\equiv 1\bmod 101$.
Thus $1000=x100+0$ and $x=10$.
$3^{1000}\equiv 3^{999^{10}} = 1 ^{10} \equiv 102\bmod 101 $
Later i have to calculate $5^{102}\bmod 101$.
Again by Fermat $5^{100}\equiv 1\bmod 101$.
$$102=100\cdot 1 +2$$
Here i am not sure how to move on... I think that my solution is wrong, but i'd love to see your suggeststions and remarks how to solve the problem.
Thank you very much in advance!
Answer
By Fermat's little theorem we know that $5^{100} \equiv 1 \bmod 101$.
What exactly does this tell us? It tells us that the powers of $5$ when reduced mod $101$ repeat every $100$ times.
So to find out what $5^{3^{1000}}$ is mod $101$ we really need to find out what $3^{1000}$ is mod $100$.
You can use the generalisation of FlT mentioned in another answer to see that $3^{40} \equiv 1 \bmod 100$, so that $3^{1000} = (3^{40})^{25} \equiv 1^{25} \equiv 1 \bmod 100$.
Alternatively you can do it by little step by step calculations.
Either way we find that $5^{3^{1000}} \equiv 5 \bmod 101$.
No comments:
Post a Comment