[drostie]

Maybe somewhat. I think you can offer a simple explanation, but it depends a little on how you have already set up the problem.

Here's the problem setup: So we want to share a secret byte (178) among Alice, Bob, and Carol, so that we need all 3 of them to contribute to it. Three points defines a parabola so we choose two more random bytes: [38, 68], our polynomial is y = 178 + 38x + 68x². We then give Alice the point (1, 284), Bob the point (2, 526), and Carol the point (3, 904).

Now supposing that we have compromised both Bob and Carol's points we know that we have the two equations,

   9a + 3b + c = 904
   4a + 2b + c = 526

We can then eliminate b to get:

   6a - c = 230

which we can rearrange as

   c = 6a - 230.

Since `a` cannot be a fraction, we must be able to cut down the number of possibilities for c to just 42 possibilities, {4, 10, 16, 22, 28, ...}, since they must be separated by sixes. I'm not 100% sure but I think this factor grows like n!/(n-k)! for "I have compromised k of n secrets, by what factor have I reduced the search space?"

Here's how modular arithmetic solves this: It turns out that modulo a prime, all fractions are also whole numbers. That is, if I am working modulo the prime 13, I will find that I can divide 7/5 to find 4. Remember what division means, it inverts multiplication: I can find that 5 × 4 = 20 and then that 20 = 13 + 7, so they are at the same place "on the clock". In fact it suffices to just find 1/5 and multiply by 7, so you can find that 1/5 is 8 in the mod-13 ring, 8 × 5 = 40 = 39 + 1. You can also find that 1/6 is 11, so 6 × 11 = 66 = 65 + 1.

The proof that this must be the case is that if you take

    [1, 2, ..., p-1].map(x => (x * n) % p)

this list cannot repeat itself: if it did, the resulting `x1 - x2` would divide `p`, by the distributive law of multiplication. It also is confined to only contain the numbers 1 through p-1, and so it must contain all of them exactly once: so if it doesn't repeat itself, it has to have a 1 in there somewhere.

That's kind of a brute force argument so you may want to also mention that there are two efficient ways to find these, one is called the "Extended Euclidean algorithm" (do a GCD computation to find that the GCD=1, but you can take the dividends that you discarded and cleverly assemble them to recover the constants from Bezout's identity, which in this case gives you the modular inverse) and the other is called "Fermat's little theorem" (since a^(p-1) % p == 1 for prime p, raise something to the p-2 power. Using exponentiation by squaring you only need ~log p multiplications that each take no more than ~log p time.