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.

  • 1
    $\begingroup$ It is not clear what you are asking. It seems instead of power in the first line you mean value. Next you are hoping to calculate $2^{99999999999999} + 6^{567563535463455555} \pmod p$ for a set of primes. This is achievable using Fermat's little theorem If you use enough primes, you will get an unambiguous answer, but I don't think that is any easier than just calculating. $\endgroup$ Feb 25 '14 at 5:35
  • $\begingroup$ 66 is incorrect. It should be 27. $\endgroup$ Aug 29 '16 at 13:25

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).

  • $\begingroup$ Got it! thanks a lot! $\endgroup$
    – Krimson
    Feb 25 '14 at 7:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.