I knew I had seen this somewhere before: http://en.wikipedia.org/wiki/Euclidean_algorithm

This is such a natural way to introduce it! I remember that I didn't fully grasp the concepts of what a 'base' is until my first year in college.

One reason this is interesting is because polynomial interpolation is used for secret sharing, so this method constitutes an "attack" on a poorly implemented polynomial interpolation sharing scheme.

Luckily for crypto, the coefficients used in a properly implemented scheme are so large as to not be vulnerable to such an attack.

Very fun. I love how it's possible to accidentally discover something cool like this, only to realise (in retrospect) that the result is "obvious." Almost always learn something really useful from it.

That reminds me of the time I rediscovered averaging. I thought I was "inventing" a new type of averaging by imagining masses attached to a massless beam. I started solving for a fulcrum when the torque would evenly balance. I then imagined instead of points, that I had one or more masses distributed continuously along the line, where the mass at any point along the line could be described by the area under a curve. It was only after I realized that I had calculated a centroid for the system, that it donned on me, I was actually calculating the average, as I had first done in elementary school. In short, nothing I was doing was new. I had simply discovered a new way to think about the problem that was not immediately clear when I came up with the thought experiment. In hind sight, it was completely obvious, but not before I ventured into calculus to solve this "tough" problem.

Great article, very useful for someone learning Scala like myself. If I understood correctly this is an example of polynomial interpolation. One method of solving is Neville's algorithm.

Polynomial Interpolation:

Input: a set of points

Output: polynomial that passes through all points of Input

Here, since the input are just two numbers, I don't think it is polynomial interpolation.

2 numbers, plus the assumption that the cooefficients are smaller than some amount, plus luck. It is interpolation with an underconstrained solution

With the constraint that none of the coefficients are negative there's no element of luck.

    f(x) = x^2 + 11x  

OR f(x) = x

    f(10) = 110

     = 1 * 10^2 +  1 * 10^1
     = 0 * 10^2 + 11 * 10^1

    f(0) = 0
     = 1 * 0^2 +  1 * 0^1
     = 1 * 0^2 + 11 * 0^1