Man is blindest where he thinks he sees most clearly; his deceptions are his truest reflections.
the polynomial we construct will have degree 1 + Sum_(i=1)^(i=N-3)i in dd
our task here is to compute this polynomial in a constructive way starting from the N signatures in the given list order
the generic formula will be given in terms of differences of nonces, i.e. k_ij = k_i - k_j where i and j are the signature indexes
each k_ij is a first-degree polynomial in dd
this function has the goal of returning it given i and j
def k_ij_poly(i, j):
hi = Z(h[i])
hj = Z(h[j])
s_invi = Z(s_inv[i])
s_invj = Z(s_inv[j])
ri = Z(r[i])
rj = Z(r[j])
poly = dd*(ri*s_invi - rj*s_invj) + hi*s_invi - hj*s_invj
return polythe idea is to compute the polynomial recursively from the given degree down to 0
the algorithm is as follows:
for 4 signatures the second degree polynomial is:
k_12k_12 - k_23k_01
so we can compute its coefficients.
the polynomial for N signatures has degree 1 + Sum_(i=1)^(i=N-3)i and can be derived from the one for N-1 signatures
let's define dpoly(i, j) recursively as the dpoly of degree i starting with index j
def dpoly(n, i, j):
if i == 0:
return (k_ij_poly(j+1, j+2))*(k_ij_poly(j+1, j+2)) - (k_ij_poly(j+2, j+3))*(k_ij_poly(j+0, j+1))
else:
left = dpoly(n, i-1, j)
for m in range(1,i+2):
left = left*(k_ij_poly(j+m, j+i+2))
right = dpoly(n, i-1, j+1)
for m in range(1,i+2):
right = right*(k_ij_poly(j, j+m))
return (left - right)icc{1f_G0d_1s_d34d_3v3ryth1ng_1s_p3rm1tt3d}
-