Month: March 2015

Multiple Personality Disorder

Human beings aren’t the only ones who face the problem of dissociative identities, you know? Numbers face this affliction as well. They can have multiple split personalities with respect to other members of their kind. When you modulo them with other numbers, they take on different personas w.r.t. each number. The problem today is to help them recover their original selves given their various personalities; help them find out who they really are !

Alternatively, more formally, say you are given the following system of congruence equations:
x \equiv c_{1} \pmod p_{1}\\  x \equiv c_{2} \pmod p_{2}\\  ...\\  ...\\  x \equiv c_{n} \pmod p_{n}\\
where the p_{i}‘s are prime numbers and c_{i}‘s are numbers belonging to the domain and you have to solve for x.

Essentially, we merge x’s identities one by one together into a whole. We find out what led to his different personalities and use that knowledge to reconstruct his whole self. In other words;
Small Primes Modular Computation is a useful technique that allows efficient computation of x by using the Chinese remainder algorithm (CRA). The implemented solution to the problem is available here and the algorithm is as follows:
Input: p_{1},...,p_{n} \in R , c_{1},...,c_{n} \in R , where R is a Euclidean domain.
Output: x \in R such that x \equiv c_{i} \pmod p_{i} for 1 \leq i \leq n
1. P \leftarrow p_{1}...p_{n}
2. for 1 \leq i \leq n do

3. return \sum_{1 \leq i \leq n} x_{i}\frac{P}{p_{i}}

To help x recover faster, there are two obvious ways, if you think about it. First, you take identities two at a time and unify them. Have a team of psychologists work simultaneously with two distinct identities to improve efficiency. Keep doing this recursively until you are left with the final unified one !!! That is…
The above algorithm can be sped up considerably by taking into account the following ideas.

  1. The number ‘n’ could be very large and as a result the product of the primes would be very large although the primes may be small. Thus the Extended Euclid would get very skewed inputs and would take longer to evaluate. Instead, we can sort the primes array and then recombine in pairs such as c_{i}, c_{n-i}. By recursively calling this recombine function, we can balance the inputs and solve faster.
  2. Since each of the individual iterations of the for loops are independent of each other, they can be evaluated in parallel. Even if the system has 2 cores (which has become common today), the time taken reduces by half.

Great ! Now, we’ve successfully helped one patient who had n split personalities. What if many more such patients showed up? What would we do then?
Alternatively, a generalization of the problem is to take as input a list of integer vectors C = \{c_{1},... c_{n}\} where c_{i} = \{c_{i1},...,c_{ik}\} and a list of coprime moduli M = \{m_{1},..., m_{n}\} . To solve this problem, instead of simply applying CRA to every pair of elements from the integer vectors and moduli, as in the function above, for each vector in the list, one can apply the vector form of the CRA. In other words, apply CRA component wise by first finding the CRA_basis E = \{e_{1},...,e_{n}\} where e_{i} \equiv 1 \pmod m_{i} and e_{i} \equiv 0 \pmod m_{j} \forall j \neq i.

This post and implementation is a result of the discussion with the mentors from fplll, Martin Albrecht and Damien Stehle.