# how to use the secret perfect shamir in Sage? Anonymous Good Morning. I need to resorve this problem. I have three fragments that I make with shamir's secret perfect and now I need to find the polinomy, but I dont know if there is a method which I can to solve the polinomy and have the secret with Sage.

For exemple I have this polinomy 56 + 10x + 5x^2 mod 101. I know that the secret is 56 and three fragments [25, 98], [47, 57], [19, 31], (56 +1025+525^2)mod 101 = 98

How I can to find the polinomy with these fragments? I can't use Lagrange because it is arithmetic modular.

Thank you.

edit retag close merge delete

This sounds like homework. Can you give us a reference to "shamir's secret perfect"? It sounds like a key-sharing or encryption scheme, perhaps one not implemented in Sage. Certainly we should have the infrastructure to deal with any polynomial stuff over Z_n, though.

Sort by » oldest newest most voted

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%2...

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)
`
more