199 caractères dans 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) caractères

Si vous ne vous souciez pas d'obtenir des résultats cette semaine, 65 caractères suffisent:

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

Mais si vous recherchez l'efficacité, elle est légèrement plus longue à 86 caractères:

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

Ceci est disséqué beaucoup plus en détail que je ne veux le répéter ici sur mon blog .

Principalement pas mon travail, mais le fait de cracher lourdement de Nabb donne 47 caractères:

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

Remarque: je n'ai raisonné qu'à propos de ce code: essayer de l'exécuter serait inutile étant donné la durée et la quantité de mémoire qu'il utiliserait.

Golfscript - 52 46 (67)

Une approche par force brute pour des inverses modulaires en 46 caractères. Calcule de façon répétée a ^ (N-2) avec des entiers de précision arbitraires.

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

La mise en œuvre de l'algorithme euclidien étendu ne nous coûte que 15 caractères supplémentaires.

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

Ce code est entièrement détaillé sur mon article de blog , y compris quelques alternatives pour calculer l'inverse multiplicatif modulaire.

Lua 444 caractères

Fonctionne pour l'exemple sur la page wiki

3
2 1942
4 3402
5 4414

Mais en quelque sorte ne fonctionne pas pour les exemples ici sur cette page. Si quelqu'un peut trouver l'erreur?

Version non golfée:

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

Golfé (n'utilisant pas de champ fini), 444 caractères:

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 caractères

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

Non golfé:

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