Saturday, March 02, 2013

[tqgxzhex] Reconstructing a polynomial from absolute values

A secret order-128 polynomial is evaluated at, say, 256 points but with the absolute value taken.  (1, |f(1)|), (2, |f(2)|), (3, |f(3)|), ... Can the original polynomial be reconstructed from these points? (Obviously yes if we get all 128 zeroes.)

Inspired by Shyam Sunder Gupta's quintic polynomial with constant term 6823316/4 discovered in Zimmermann's programming contest, which takes negative prime values.

Possible cryptography applications, perhaps a polynomial over a finite field.  Balanced ternary for absolute value.

No comments :