polynomial.js

#!/usr/bin/env node

/**
 * Small program to figure solve the challenge and response based polynomial problem:
 * Adversary generates p(x) = a_0 + a_1*x + a_2*x^2 + ... + a_n*x^n
 * where a_i are non-negative integers.
 *
 * This program will compute all the a_i given only two inputs (challenges)
 * - p1 = p(1) (equal to the sum of coefficients by assumption of a_i)
 * - pN = p(p(1) + 1)
 *
 * The reason we can do this with only two inputs comes from the non-negative integer
 * assumption and the adaptive second query.
 *
 * For more information see the blogpost at:
 * https://jeremykun.com/2014/11/18/learning-a-single-variable-polynomial-or-the-power-of-adaptive-queries/
 */

const obtain_coefficients = (p1, pN) => {
  const N = p1 + 1;
  const y = [];
  const a = [];

  // first coefficient - just take pN mod N
  y[0] = pN;
  a[0] = y[0] % N;

  // rest by dividing away N and subtracting previous coeff, and mod N that
  // stop once our y_i values reach zero (nothing left mod N => we are done)
  for (var i = 1; y[i-1] !== 0; i += 1) {
    y[i] = (y[i-1] - a[i-1])/N;
    a[i] = y[i] % N;
  }
  return a.slice(0, -1); // last coeff always zero - discard it
};

if (module === require.main) {
  var p1 = parseInt(process.argv[2], 10); // 36
  var pN = parseInt(process.argv[3], 10); // 3710327447844
  console.log(p1, pN);
  obtain_coefficients(p1, pN).map((x, i) => {
    console.log('a_' + i + ' = ' + x);
  });
  // a_0 = 0
  // a_1 = 8
  // a_2 = 7
  // a_3 = 6
  // a_4 = 5
  // a_5 = 4
  // a_6 = 3
  // a_7 = 2
  // a_8 = 1
}