Supposed we want to calculate the power of:
$2^{99999999999999} + 6^{567563535463455555}$
and we have a set of prime numbers $\{x : x \in\mathbb{Z}, \text{ isPrime}(x)\}$
Now its obvious that trying to calculate the power of the above expression is near impossible on computers since there aren't enough bits and memory to represent such a number so we use CRT
I know we have to set up equation in congruence classes and solve the system to retrieve the final value.
For example in the following system
$x ≡ 6\mod 7$
$x ≡ 5\mod 11$
we know that $x$ is $66 \in \dfrac{\mathbb{Z}}{77\mathbb{Z}}$
I'm confused how to apply the problem stated above using the CRT. Can you help me?
Note: CRT refers to Chinese Remainder Theorem.
Best Answer
Given a set of primes, $\{p_i \mid i\in[1,k]\}$, compute a basis: A set of integers $b_i$ such that $b_i \cong 1 \mod p_i$ and $b_i \cong 0 \mod p_j$ for $j \neq i$. Since they're primes, they are coprime, so there is a linear combination of them that produces one, and this is what you need to find your basis.
Suppose then that some number, $n$, is simultaneously congruent to $a_i \mod p_i$ for the set of primes. Then $n \cong \left( \sum a_i b_i \right) \mod \prod_{i=1}^k p_i$.
(Watching how all that happens, the basis does act as a matrix to multiply the vector of the various residues.)
Observation: The set of primes must be large enough and/or contain enough primes that the resulting product is smaller than the product of the primes. Otherwise the results "roll over" and you will lose uniqueness (unless you have some additional way to keep track of how many times the result has rolled over. An easy way to do that is add a bigger prime).