The Chinese Remainder Theorem gives a unique solution to a set of linear congruences if their moduli are coprime.
This means, that given a set of arbitrary integers a_{i}
, and pairwise coprime integers n_{i}
, such that the following linear congruences hold:
Note "pairwise coprime integers" means that if we have a set of integers {n_{1}, n_{2}, ..., n_{i}}
, all pairs of integers selected from the set are coprime: gcd(n_{i}, n_{j}) = 1
.
x ≡ a_{1} mod n_{1}
x ≡ a_{2} mod n_{2}
...
x ≡ a_{n} mod n_{n}
There is a unique solution x ≡ a mod N
where N = n_{1} * n_{2} * ... * n_{n}
.
In cryptography, we commonly use the Chinese Remainder Theorem to help us reduce a problem of very large integers into a set of several, easier problems.
Given the following set of linear congruences:
x ≡ 2 mod 5
x ≡ 3 mod 11
x ≡ 5 mod 17
Find the integer a
such that x ≡ a mod 935
Starting with the congruence with the largest modulus, use that for x ≡ a mod p
we can write x = a + k*p
for arbitrary integer k
.
You must be logged in to submit your flag.
You are now level Current level