Mignotte Secret Sharing

#The code below does not need to be modified. #Evaluate this cell (once) to define the function and you won't need to do it again. def Mignotte(t, n): if t > n: print "t must not exceed n" return False i = 0 while True: i = i + 1 M = [nth_prime(i) for i in range(i, i+n)] #a list of n consec. primes, starting with the ith prime. alpha = prod(M[:t]) #product of first t primes beta = prod(M[-(t-1):]) #product of last t-1 primes if alpha > beta: break S = ZZ.random_element(beta + 1, alpha) #the secret number! R = [S % m for m in M] #the residues of S return R, M 

R, M = Mignotte(4, 10) print "R = ", R print "M = ", M print "shares = ", [ [R[i], M[i]] for i in range(len(R)) ] 

#The secret can be recovered by using CRT on all the shares CRT(R, M) 

#Test the threshold. Re-evaluate using different values of t. t = 3 n = len(M) #Create a random index set of t elements from among {0, ..., n-1} I = Subsets(range(n), t).random_element() print "I = ", I #Show what the CRT applied to a random choice of t shares produces. CRT( [R[i] for i in I], [M[i] for i in I] )