3704.sagews

#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 = randint(beta + 1, alpha)  #the secret number!
    R = [S % m for m in M]  #the residues of S
    return R, M

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

R = [12, 2, 63, 35, 36, 30, 10, 46, 7, 40, 35, 38, 5, 81, 73, 87, 15, 63, 96] M = [71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163] shares = [[12, 71], [2, 73], [63, 79], [35, 83], [36, 89], [30, 97], [10, 101], [46, 103], [7, 107], [40, 109], [35, 113], [38, 127], [5, 131], [81, 137], [73, 139], [87, 149], [15, 151], [63, 157], [96, 163]]

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

2145111796603317

#Test the threshold.  Re-evaluate using different values of t.
t = 7
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] )

I = {16, 1, 3, 5, 6, 10, 12} 48065157260453

#CRT( [residues], [moduli] )

CRT( [0, 15, 14], [17, 19, 23] )

1003