Revision history [back]

You seem to be refering to Shamir Secret Sharing a secret-sharing scheme invented by Shamir: paper here

Described nicely here: http://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing

The following Sage code works fine to reconstruct the polynomial from the shares:

F = FiniteField(101) # Construct finite field
P = F['x'] # Polynomial ring

# How to use P:
original_polynomial = P("56 + 10x + 5x^2")
# Convert the shares to elements of F (otherwise lagrange_polynomial will fail)
shares = [(F(x), F(y)) for x,y in [(25, 98), (47, 57), (19, 31)]]
# Now lagrange_polynomial works fine
reconstructed_polynomial = P.lagrange_polynomial(shares)

print "Correct reconstruction!" if reconstructed_polynomial == original_polynomial else "Something wrong!"
print "p(x) =", reconstructed_polynomial
print "Secret = p(0) =", reconstructed_polynomial(0)