I am having problems with calculating $$x \mod m$$
with $$x = 2^{\displaystyle2^{100,000,000}},\qquad m = 1,500,000,000$$
I already found posts like this one
https://stackoverflow.com/questions/2177781/how-to-calculate-modulus-of-large-numbers
But can someone explain me how to use this in my case, please?
On
In this case, I would do repeated squaring:
$x_0 = 2\\ for\ i=1\ to\ 100000000\\ \quad x_i = x^2_{i-1} \bmod m\\ $
By induction, since $x_0 = 2^{2^0}$, $x_i = 2^{2^i}$.
Since $m$ is so large, you would have to use multiple-precision arithmetic, although, if you work with 64-bit integers, double-word arithmetic would work.
I would recommend looking for existing code that would do this, rather than writing your own, unless that is a requirement.
On
Okay, so you want to calculate $a^b\ mod \ m$ with $b$ and m are very large numbers and a and m are coprime. We can use an interesting result called Euler's theorem: $$ a^{\phi(m)} \ mod \ m=1$$
So now we reduce to problem to calculate $$ b\ mod \ \phi(m) $$ , because if $r=b\ mod \ \phi(m) $ then $$ a^b\ mod\ m = a^{q \phi(m) +r} \ mod\ m= (a^\phi(m))^q.a^r\ mod\ m = a^r\ mod\ m$$
Thus, the problem is reduced.
So in your exemple you have to calculate
And i will let you to do the rest of calculations. This how to do it manually , but in the general case the calcul of $\phi$ is very hard!
Using the Chinese Remainder Theorem in addition to other bits.
Observe that your modulus factors like $m=2^8\cdot3\cdot 5^9$. Your number is very obviously divisible by $2^8$, so we can forget about that factor until the end.
Modulo $3$? The number $2^{2^{\text{ZILLION}}}$ is clearly a power of $4$, so its remainder modulo $3$ is equal to $1$.
Modulo $5^9$? Because $2$ is coprime with $5^9$ we can use the Euler totient function $\phi$. We have $\phi(5^9)=(5-1)5^8=4\cdot5^8.$ Call this number $K$. We know from elementary number theory that $2^K\equiv1\pmod{5^9}$. Consequently also $2^N\equiv 2^n\pmod{5^9}$ whenever $N\equiv n\pmod{K}$. Therefore we want to calculate the remainder of $M=2^{100000000}$ modulo $K$. Let's repeat the steps. $M$ is clearly divisible by $4$, so we concentrate on the factor $5^8$. Euler's totient gives $\phi(5^8)=4\cdot5^7$. Clearly $100000000=10^8=2^8\cdot5^8$ is divisible by $4\cdot5^7$. This implies that $M\equiv 2^0=1\pmod{5^8}$.
Now we begin to use the Chinese Remainder Theorem. We know that $M\equiv 0\pmod 4$ and $M\equiv 1\pmod {5^8}$. The CRT says that these congruences uniquely determine $M$ modulo $K=4\cdot5^8$. As $5^8\equiv1\pmod4$, we see that $3\cdot5^8+1$ is divisible by four. As it is clearly also congruent to $1\pmod{5^8}$ we can conclude that $M\equiv 3\cdot5^8+1=1171876\pmod K$.
This, in turn, means that $$ 2^M\equiv 2^{1171876}\pmod{5^9}. $$ This exponent, finally, is small enough for square-and-multiply. I cheat and use Mathematica instead. The answer is that $$ 2^{1171876}\equiv1392761\pmod{5^9}. $$
Now we know every thing we need about the remainders: $$ \begin{aligned} 2^M&\equiv0\pmod{2^8},\\ 2^M&\equiv1\pmod3,\\ 2^M&\equiv 1392761\pmod{5^9}. \end{aligned} $$ All that remains is to put these bits together by yet another application of CRT. Have you implemented those routines?
Edit: I did this run of CRT with Mathematica. Barring an earlier error (in the above calculations) the answer is that $$ X=2^{2^{100000000}}\equiv 741627136 \pmod{1500000000}. $$ The observations leading to this are: