Shamir 2-of-2 Recover

Problem

Recover the secret from two points of a linear Shamir sharing scheme modulo the prime p. Using Lagrange interpolation evaluated at 0:

secret = (y1 * x2 - y2 * x1) * inverse(x2 - x1) mod p

Return the recovered secret. Implement the modular inverse by searching 1..p-1 so no library calls are needed.

Hint

The secret is the value of the degree-1 polynomial at x = 0.

case 1

in: [101,1,42,2,47]

expected: 37

case 2

in: [17,1,10,3,16]

expected: 7

case 3

in: [97,2,40,5,55]

expected: 30

case 4

in: [13,1,0,2,4]

expected: 9

Starter codePython

def shamir_recover_2(p, x1, y1, x2, y2):
    # Your code here
    pass

4 test cases · run your code against them in the editor