5 ms·

More backwards functions: Unevaluating polynomials

47 points by jliszka 13y ago

eliteraspberrie 13y ago
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.
- pm90 13y ago
  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.
  - gohrt 13y ago
    2 numbers, plus the assumption that the cooefficients are smaller than some amount, plus luck. It is interpolation with an underconstrained solution
    - brianpgordon 13y ago
      With the constraint that none of the coefficients are negative there's no element of luck.
      - gohrt 13y ago
        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
      - deleted 13y ago
        [deleted]
Osmium 13y ago
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.
- chinpokomon 13y ago
  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.
pm90 13y ago
I knew I had seen this somewhere before: http://en.wikipedia.org/wiki/Euclidean_algorithm 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.
j2kun 13y ago
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.

47 points by jliszka 13y ago

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.

pm90 13y ago
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.
- gohrt 13y ago
  2 numbers, plus the assumption that the cooefficients are smaller than some amount, plus luck. It is interpolation with an underconstrained solution
  - brianpgordon 13y ago
    With the constraint that none of the coefficients are negative there's no element of luck.
    - gohrt 13y ago
      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
    - deleted 13y ago
      [deleted]

Osmium 13y ago

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.

chinpokomon 13y ago
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.

pm90 13y ago

I knew I had seen this somewhere before: http://en.wikipedia.org/wiki/Euclidean_algorithm 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.

j2kun 13y ago

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.