Schemat dzielenia się sekretami Shamira to prosty sposób ochrony tajemnicy poprzez podzielenie jej na kilka części potrzebnych do jej odtworzenia.

Twoim zadaniem jest wdrożenie rekonstrukcji Shamir's Secret Sharing na polu skończonym określonym przez liczbę pierwszą 1928049029. Jeśli masz wątpliwości co do tego, co to oznacza, po prostu zapytaj lub zobacz Arytmetykę pola skończonego i pola skończonej w Wikipedii (więcej zasobów poniżej).

Wejście

Wprowadzanie odbywa się za pomocą stdin. Najpierw jest liczba całkowita k, a następnie k linii. Każda z tych linii zawiera parę liczb całkowitych x yreprezentujących sekret. Innymi słowy f(x) = yw oryginalnym wielomianu, który był używany do konstruowania sekretów.

Podana liczba sekretów jest zawsze wystarczająca, aby skonstruować odpowiedni sekret.

Wynik

Wyjście na standardowe wyjście zrekonstruowanego sekretu.

Przykłady

Wejście:

5         
1 564797566
2 804114535
4 1354242660
6 1818201132
7 503769263

Wynik:

1234

Wejście:

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

Wynik:

456457856

Zasoby

Artykuł w Wikipedii

Papier

Pole skończone Źródło: Wikipedia

Arytmetyka pola skończonego Źródło: Wikipedia

Wielomian Lagrange'a Źródło: Wikipedia

Rozdział o arytmetyki pola skończonego

bash, 271 znaków

r () {
[{{1/0 /}] && {r $ ((2% 1 $)) 1 $; ((t = u, u = v- 2 $ / 1 * * u, v = t));}
}
czytać
((N = 1928049029, n = 0))
podczas czytania x [$ n] y [$ n]
do ((n ++))
gotowy
dla ((i = n; z = (z + l)% N, i -;)) zrobić
dla ((j = n, l = y [i]; j -;)) wykonaj
((u = 0, v = 1, d = x [j] -x [i], M = N + d))
r MN
[$ {d / 0 /}] i& ((l = l * x [j]% N * (u + N)% N))
gotowy
gotowy
echo $ z

Znaki nowego wiersza można w większości przypadków zastąpić średnikami, ale nie sądzę, aby istniała niepotrzebna biała spacja.

(Do tej pory nie zdawałem sobie sprawy, że liczby całkowite basha są 64-bitowe - bardzo pomocne).

Dla basha rekurencyjny GCD (wykorzystujący stan globalny) wydaje się być bardziej kompaktowy niż iteracyjny. Jest to w większości proste; ciekawa sztuczka [ ${d/0/} ]&&foojest skutecznaif [ $d -ne 0 ];then foo;fi

199 znaków w oktawie:

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) znaków

Jeśli nie zależy ci na uzyskaniu wyników w tym tygodniu, wystarczy 65 znaków:

~](;2/0\:X{~\.X{0=}%^\{\.@- 1928049029:P.,\@{@*\%(!}++?**}+/+P%}/

Ale jeśli szukasz wydajności, jest ona nieco dłuższa przy 86 znakach:

~](;2/0\:X{~\.X{0=}%^\{\[.0](@-[1928049029:P%P]{.~/{\.(;@@~@*-+\}+2*.1=}do;0=*}+/+P%}/

Jest to omówione bardziej szczegółowo, niż chcę powtórzyć tutaj na moim blogu .

Głównie nie moja praca, ale ciężkie przekopywanie od Nabba daje 47 znaków:

n%(!\:A{~A{~;.3$- 1928049029:N((?1or**}/\/+N%}/

Uwaga: Jedynie myślałem o tym kodzie: próba uruchomienia go byłaby bezcelowa, biorąc pod uwagę czas i ilość używanej pamięci.

Golfscript - 52 46 (67)

Podejście brutalnej siły dla modułowych inwersji w 46 znakach. Wielokrotnie oblicza ^ (N-2) z liczbami całkowitymi o dowolnej precyzji.

n%(!\:A{~A{~;.3$-.!+1928049029:N((?**}/\/+N%}/

Wdrożenie rozszerzonego algorytmu euklidesowego kosztuje nas tylko dodatkowe 15 znaków.

n%(!\:A{~A{~;.3$-:|!1\1928049029:N{@2$|3$/*-\|\:|%.}do;;**}/\/+N%}/

Ten kod jest w pełni szczegółowy na moim blogu , w tym niektóre alternatywy dla obliczania modularnego odwrotności multiplikatywnej.

Lua 444 Chars

Działa w przykładzie na stronie wiki

3
2 1942
4 3402
5 4414

Ale jakoś nie działa w przypadku przykładów tutaj na tej stronie. Jeśli ktoś może znaleźć błąd?

Wersja bez gry w golfa:

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

-- Read data
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

Gra w golfa (bez pola skończonego), 444 znaki:

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))

Java, 435 407 znaków

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);}}

Nie golfowany:

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);
    }
}

Haskell, 183

p=1928049029
a#0=(1,0)
a#b=let(s,t)=b#mod a b in(t,s-div a b*t)
s d=sum[y*product[z*fst((z-x)#p)|[z,_]<-d,z/=x]|[x,y]<-d]
main=interact$show.(`mod`p).s.map(map read.words).tail.lines