Implement Shamir's Secret Sharing reconstruction

Shamir's secret sharing scheme is a simple way of protecting a secret by splitting it into several parts needed to reconstruct it.

Your task is to implement Shamir's Secret Sharing reconstruction over the Finite Field defined by the prime 1928049029. If you have any doubts about what this means, just ask or see Finite Field & Finite Field Arithmetic in wikipedia (more resources below).

Input

Input is done using stdin. First comes an integer k, then k lines follow. Each of these lines contains a pair of integers x y that represent a secret. In other words f(x) = y in the original polynomial that was used to construct the secrets.

The number of secrets given is always enough to construct the corresponding secret.

Output

Output to stdout the reconstructed secret.

Examples

Input:

5
1 564797566
2 804114535
4 1354242660
6 1818201132
7 503769263


Output:

1234


Input:

7
1 819016192
2 1888749673
3 1737609270
4 365594983
5 1628804870
6 1671140873
7 492602992


Output:

456457856


Resources

Wikipedia article

Paper

Finite field Source: Wikipedia

Finite field arithmetic Source: Wikipedia

Lagrange polynomial Source: Wikipedia

Chapter on Finite field arithmetic

bash, 271 chars

r(){
[ ${1/0/} ]&&{ r$(($2%$1)) $1;((t=u,u=v-$2/$1*u,v=t));} } read ((N=1928049029,n=0)) while read x[$n] y[$n] do((n++)) done for((i=n;z=(z+l)%N,i--;))do for((j=n,l=y[i];j--;))do ((u=0,v=1,d=x[j]-x[i],M=N+d)) r M N [${d/0/} ]&&((l=l*x[j]%N*(u+N)%N))
done
done
echo $z The newlines could be replaced in most cases with semicolons, but I don't think there's any unnecessary whitespace. (I hadn't realised before today that bash's integers are 64-bit - very helpful). For bash the recursive GCD (exploiting global state) seems to be more compactible than the iterative one. This is mostly straightforward; the interesting trick is [${d/0/} ]&&foo which is effectively if [ $d -ne 0 ];then foo;fi • Nice! I never expected to see a bash answer to this problem. +1 Commented Mar 5, 2011 at 18:58 • @Juan, I started doing it in Perl, and got fed up with having to force it to do integer division rather than float. And I know bash better anyway, so it involves less beating of head against wall. Commented Mar 5, 2011 at 20:35 199 characters in Octave: m=@(x)mod(x,1928049029);[d,l]=scanf('%d');c=d(1);e=repmat(int64(d(2:2:l)),1,c);[_,b]=gcd(e-e',1928049029*ones(c));b=eye(c)+m(e.*b);x=b(1,:);for i=2:c;x=m(x.*b(i,:));end;disp(m(sum(m(x'.*d(3:2:l)))))  Golfscript, 114 112 111 110 109 65 (86) chars If you don't care about getting results this week, 65 chars suffice: ~](;2/0\:X{~\.X{0=}%^\{\.@- 1928049029:P.,\@{@*\%(!}++?**}+/+P%}/  But if you're looking for efficiency, it's slightly longer at 86 chars: ~](;2/0\:X{~\.X{0=}%^\{\[.0](@-[1928049029:P%P]{.~/{\.(;@@~@*-+\}+2*.1=}do;0=*}+/+P%}/  This is dissected in far more detail than I want to repeat here on my blog. Mainly not my work, but cribbing heavily from Nabb gives 47 chars: n%(!\:A{~A{~;.3$- 1928049029:N((?1or**}/\/+N%}/


Note: I've only reasoned about this code: trying to run it would be pointless given the length of time and amount of memory it would use.

Golfscript - 52 46 (67)

A brute force approach for modular inverses in 46 characters. Repeatedly computes a^(N-2) with arbitrary precision integers.

n%(!\:A{~A{~;.3$-.!+1928049029:N((?**}/\/+N%}/  Implementing the extended Euclidean algorithm only costs us an additional 15 characters. n%(!\:A{~A{~;.3$-:|!1\1928049029:N{@2$|3$/*-\|\:|%.}do;;**}/\/+N%}/


This code is fully detailed on my blog post, including some alternatives for computing the modular multiplicative inverse.

• Nice, but I think there are still at least two chars to be saved. Replace {*N%2<} with {*N%1=} as in the blog and you can ditch the (; after N,. But then for the performance-is-irrelevant entry you can use Fermat's little theorem without bothering about the modular side of the exponentiation - just leave that for the final tidy - so recip becomes N((?. Commented Oct 7, 2011 at 19:28
• @Peter: {*N%1=}+ will miss the case with the denominator zero, which would take at least 3 characters to handle. Good catch on simply doing x^(N-2) though, we can actually get 46 characters using this.
– Nabb
Commented Oct 8, 2011 at 3:52

Lua 444 Chars

Works for the example on the wiki page

3
2 1942
4 3402
5 4414


But somehow does not work for the examples here on this page. If anyone can find the error?

Non-golfed version:

-- Reconstruct shamir secret
-- convention, poly = {[0]=a0,a1,...,an}
f=math.fmod
w=1928049029
k=i():match"%d+"
x={} -- Will contain X values
y={} -- Will contain Y values
p={} -- will contain lagrange polynomials

for j=0,k-1 do
x[j],y[j]=i():match("(%d+) (%d+)")
print(j,x[j],y[j])
end
-- Multiplication and scaling function
function mul(p,q,s)
-- multiply polies
r={} -- poly to be returned
for k=0,#p do
for l=0,#q do
r[l+k]=r[l+k] or 0 -- if the coeff for degree l+k of x doesn't exist, put 0
p[k]=p[k] or 0 -- if p hasn't got a coeff for x^k
q[l]=q[l] or 0 -- idem for q
r[l+k]=(r[l+k]+s*p[k]*q[l]%w -- calculate increment for coeff for x^(l+k)
end
end
-- Debugging
io.write"Multiplied "
printPoly(p)
io.write"With       "
printPoly(q)
io.write("And scaling factor ",tostring(s),"\n")
io.write"Yielding   "
printPoly(r)
return r
end

function printPoly(p) -- "Pretty" printing of the polynomial
for k=#p,1,-1 do
io.write(tostring(p[k] or 0),"x^",tostring(k),"+")
end
io.write(p[0])
io.write"\n"
end
function egcd(a,b)
if a == 0 then
return b, 0, 1
else
local g, y, x = egcd(b % a, a)
return g, x - math.floor(b / a) * y, y
end
end

function inv(a,m)
a=a>=0 and a or a+m
local g,x,y = egcd(a,m)
if g== 1 then
return x%m
else
print(a,"has no inverse mod",m)
end
end

-- generate lagrange polynomials
for j=0,#x do
print("j=",j,"*********")
for m=0,k-1 do
if m~=j then -- if m==j, continue
p[j]=p[j]or{[0]=1} -- if this poly doesn't exist, take 1
p[j]=mul( p[j], {[0]=-x[m],1},inv(x[j]-x[m],w))-- multiply with (x-x_m)/(x_j-x_m)
io.write"---------------------------------\n"
end
end
end
r=0 -- Result for x^0
for k=0,#p do
print("l_"..k)
printPoly(p[k]) -- print l_k
r=r+f(y[k]*p[k][0],w) -- add coeff for x^0 to result
end
print("Secret was",f(r,w)) -- display result


Golfed (not using finite field), 444 chars:

i=io.read f=math.fmod w=1928049029 k=i():match"%d+"x={}y={}p={}for j=0,k-1 do x[j],y[j]=i():match("(%d+) (%d+)")end
function mul(p,q,s)r={}for k=0,#p do for l=0,#q do r[l+k]=r[l+k]or 0 p[k]=p[k]or 0 q[l]=q[l]or 0 r[l+k]=f(r[l+k]+s*p[k]*q[l],w)end end return r end
for j=0,#x do for m=0,k-1 do if m~=j then p[j]=p[j]or{[0]=1}p[j]=mul(p[j],{[0]=-x[m],1},1/(x[j]-x[m]))end end end r=0 for k=0,#p do r=r+f(y[k]*p[k][0],w)end
print(f(r,w))

• The Wikipedia example doesn't use a finite field, which is really a shame, that would have been a lot more instructive. That is most likely the source of your error. Commented Mar 2, 2011 at 16:56

Java, 435 407 chars

import java.util.*;public class G{public static void main(String[]args){Scanner s=new Scanner(System.in);int i,k,n=s.nextInt();long N=1928049029L,x[]=new long[n],y[]=new long[n],z=0,l,c;for(i=n;i-->0;){x[i]=s.nextInt();y[i]=s.nextInt();}for(i=n;i-->0;){l=y[i];for(long j:x)if(x[i]!=j){c=1;for(long a=N+j-x[i],b=N,d=0,t;b>0;){t=d;d=c-a/b*d;c=t;t=b;b=a%b;a=t;}l=l*j%N*(c+N)%N;}z+=l;}System.out.println(z%N);}}


Ungolfed:

import java.util.*;
public class G {
public static void main(String[] args) {
Scanner s=new Scanner(System.in);
int i,k,n=s.nextInt();
long N=1928049029L,x[]=new long[n],y[]=new long[n],z=0,l,c;
for (i=n; i-->0;) {
x[i]=s.nextInt();
y[i]=s.nextInt();
}
for (i=n; i-->0;) {
l=y[i];
for (long j:x)
if (x[i]!=j) {
// Extended Euclid algorithm - iterative version -
// to find the reciprocal of j-x[i] (mod N)
c=1;
for (long a=N+j-x[i], b=N, d=0, t; b>0;) {
t=d; d=c-a/b*d; c=t;
t=b; b=a%b; a=t;
}
l = l*j%N;
l = l*(c+N)%N;
}
z+=l;
}
System.out.println(z%N);
}
}


p=1928049029
main=interact\$show.(modp).s.map(map read.words).tail.lines