Shamir

import random
def ln(X,Y):
    sm = 0
    for j in range(len(Y)):
        p1=1
        p2=1
        for i in range(len(X)):
            if j != i:
                p1=p1*(0 - X[i])
                p2=p2*(X[j] - X[i])
            else:
                p1=p1*1
                p2=p2*1
        sm = sm+Y[j]*p1/p2
    return sm

def is_prime(n):
    if n< 2:
        return False
    if n == 2:
        return True
    for i in range(2, int(n/2)):
        if n % i == 0:
            return False
    return True

M = int(input("input secret"))

n=int(input(" number of all users: "))
k=int(input(" number of users to recover: "))
a =[]
for i in range(k-1):
    a.append(random.randint(2,10))
print("result of a ",a)
ki = []
x = [i for i in random.sample(range(15,40),n)]
print("x", x)
for i in range(n):
        sm = M
        for j in range(k-1):
            sm += a[j]*(x[i]**(k-j-1))
        ki.append(sm)
print("ki",ki)
stopslovo = ""
while stopslovo != 'stop':
    stopslovo = input("stop to break it")
    X = []
    Y = []
    print("choose ", k, " users to recover the secret")
    for i in range(k):
        print("user ", i+1,"choose")
        t = int(input())
        X.append(x[t-1])
        Y.append(ki[t-1])
    print("X",X)
    print("Y",Y)
    print(ln(X,Y))
    X.clear()
    Y.clear()