[27] We consider how information about x can be dispersed.

Let x ∈ N with l(x) = n and C(x) = n + O(1). Show that there are u, v, w ∈ N such that

(i) l(u) = l(v) = l(w) = 1 2n, C(u) = C(v) = C(w) = 1 2n (+O(1)), and they are pairwise independent: C(y|z) = 1 2n + O(1) for y, z ∈ {u, v, w}

and y = z;

(ii) x can be reconstructed from any two of them: C(x|y, z) = O(1), where y, z ∈ {u, v, w} and y = z.

Can you give a general solution for finding m+k elements of N such that each of them has length and complexity n/m, and x can be reconstructed from any m distinct elements?

Comments. It is surprising that x can be reconstructed from any two out of three elements, each of one-half the complexity of x. This shows that the identity of the individual bits is not preserved in the division.

Hint: Assume n = 2m and x = x1 ...x2m, u = u1 ...um, v = v1 ...vm, and w = w1 ...wm with ui = x2i−1, vi = x2i, and wi = vi ⊕ ui. (Recall that a ⊕ b = 1 iff a = b.) This solution apparently does not generalize.

A general solution to distribute x over m + k elements such that any group of m elements determines x can be given as follows: Compute the least integer y ≥ x1/m. Let pi be the ith prime, with p1 = 2. Distribute x over u1,...,um+k, where ui ≡ x mod p

α(i)

i , with α(i) = y logpi 2.

Using the Chinese remainder theorem we find that we can reconstruct x from any subset of m elements ui. Source: [A. Shamir, Comm. ACM, 22:11(1979), 612–613; M.O. Rabin, J. ACM, 36:2(1989), 335–348].