El intercambio secreto de Shamir

17

Dado n(el número de jugadores), t(el valor del umbral) y s(el secreto), ngeneran los secretos generados por el algoritmo de intercambio secreto de Shamir .

El algoritmo

Para los propósitos de este desafío, los cálculos se realizarán en GF (251) (el campo finito de tamaño 251, también conocido como el número entero mod 251 ). Normalmente, el campo se elegiría de tal manera que su tamaño sea un primo mucho mayor que n. Para simplificar el desafío, el tamaño del campo será constante. 251ha sido elegido porque es el primo más grande representable por un entero sin signo de 8 bits.

  1. Genere t-1enteros aleatorios en el rango (inclusive) [0, 250]. Etiquetar estos un 1 a través de un t-1 .
  2. Construya un t-1polinomio de grado th usando scomo valor constante y los enteros aleatorios del paso 1 como los coeficientes de las potencias de x: f (x) = s + x * a 1 + x 2 * a 2 + ... + x t- 1 * a t-1 .
  3. Salida (f(z) mod 251)para cada uno zen el rango (incluido) [1, n].

Implementación de referencia

#!/usr/bin/env python
from __future__ import print_function
import random
import sys

# Shamir's Secret Sharing algorithm
# Input is taken on the command line, in the format "python shamir.py n t s"

n, t, s = [int(x) for x in sys.argv[1:4]]
if t > n:
    print("Error: t must be less than or equal to n")
    exit()
if n not in range(2, 251):
    print("Error: n must be a positive integer less than 251")
    exit()
if t not in range(2, 251):
    print("Error: t must be a positive integer less than 251")
    exit()
if s not in range(251):
    print("Error: s must be a non-negative integer less than 251")
    exit()
p = 251
a = [random.randrange(0, 251) for x in range(t-1)]

def f(x):
    return s + sum(c*x**(i+1) for i,c in enumerate(a))

# Outputting the polynomial is for explanatory purposes only, and should not be included
#  in the output for the challenge
print("f(x) = {0} + {1}".format(s, ' + '.join('{0}*x^{1}'.format(c, i+1) for i,c in enumerate(a))))
for z in range(1, n+1):
    print(f(z) % p)

Verificación

El siguiente fragmento de pila se puede utilizar para verificar salidas:

Mostrar fragmento de código

Reglas

  • sserá un número entero no negativo menor que 251, ny tserá un número entero positivo menor 251y mayor que 1. Además, tiene la garantía de que las entradas son válidas (significado t <= n).
  • La entrada y la salida pueden estar en cualquier formato razonable, inequívoco y consistente.
  • Los números aleatorios se tomarán de una distribución uniforme: cada valor posible debe tener la misma probabilidad de ser elegido.
code-golf number-theory random cryptography polynomials code-golf number code-golf math number sequence code-golf quine code-generation code-golf arithmetic set-theory code-golf sequence code-golf code-golf string math fastest-code optimization code-golf code-golf internet stack-exchange-api code-golf array-manipulation code-golf string internet string code-challenge internet test-battery code-golf math pi code-golf arithmetic primes code-golf array-manipulation code-golf string code-golf string palindrome code-golf sequence number-theory fastest-algorithm code-golf math number base-conversion code-golf number-theory sorting subsequence search code-golf permutations code-challenge popularity-contest code-generation Mego
fuente
1
¿Tenemos que salir z y f(z) ? Si imprimo una matriz de f(z)s en orden, zestá implícito en el índice. [[1, 5], [2, 2], [3, 9], [4, 14]]no contiene más información que [5, 2, 9, 14].
orlp
1
Desafío para hacer lo inverso .
FryAmTheEggman
@orlp Punto justo.
Mego
¿Algún caso de prueba?
Leaky Nun
44
@LeakyNun Dado que esta pregunta está etiquetada al azar , creo que el fragmento de verificación es mucho más valioso que los casos de prueba que variarán para cada ejecución.
FryAmTheEggman

Respuestas:

13

Jalea , 15 bytes

251©xX€⁵0¦ḅЀ%®

Espera t , n , y s como argumentos de línea de comandos. Pruébalo en línea!

Cómo funciona

251©xX€⁵0¦ḅЀ%®  Main link. Left argument: t. Right argument: n Third argument: s

251©             Yield 251 and copy it to the register.
    x            Repeat [251] t times.
     X€          Random choice each; pseudo-randomly choose t integers from
                 [1, ..., 251]. Since 251 = 0 (mod 251), this is equivalent to
                 choosing them from [0, ..., 250].
       ⁵0¦       Replace the last generated integer (index 0) with s (⁵).
          ḅЀ    Interpret the resulting array as a base-k number, for each k in
                 [1, ..., n], and convert to integer.
              ®  Yield 251 from the register.
             %   Take the generated integers modulo 251.
Dennis
fuente
3
Reemplazar el último entero es muy elegante :)
Lynn
8

Mathematica, 59 56 bytes

Mod[Power~Array~{#2,#-1}.RandomInteger[250,#-1]+#3,251]&

Toma tres argumentos en el orden t , n y s . Construye una matriz 2d con n filas y t -1 columnas. Cada fila vector j , numerados del 1 al n , contiene los poderes de j thru j t -1 . Luego, se crea un vector de coeficientes enteros aleatorios en el rango de 0 a 250 con valores t -1. Eso se multiplica por la matriz con la matriz 2d, y luego se agrega s por elemento y se toma el módulo 251 para obtener el valor del polinomio en cada uno de los n puntos.

millas
fuente
1
Estaba a punto de publicar una respuesta de 79 bytes, ¡buen truco con Sum!
LegionMammal978
1
Tengo un enfoque diferente, pero actualmente es dos bytes más largo. Quizás tengas una idea de cómo acortarlo:Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]&
Martin Ender
3

Pyth, 24 bytes

J+EmOK251tEm%s.e*b^dkJKS

Pruébalo en línea!

Orden de entrada: n s tseparado por salto de línea.

Monja permeable
fuente
arrrrrgh, ninja porque yo fui a buscar una galleta
Maltysen
3

JavaScript, 181 bytes

(n,t,s)=>{r=Array(t-1).fill(0).map($=>{return Math.random()*251});f=(x=>{p = 0;r.map((k,c)=>p+=k*Math.pow(x, c));return s+p});_=Array(t-1).fill(0);_.map((l,i)=>_[i]=f(i));return _;}

Sin golf:

(n, t, s) => {
    r = Array(t - 1).fill(0).map($ =>{return Math.random() * 251});
    f = (x => {
        p = 0;
        r.map((k, c) => p += k * Math.pow(x, c));
        return s + p
    });
    _ = Array(t - 1).fill(0);
    _.map((l, i) => _[i] = f(i));
    return _;
}

No sé cómo verificarlo correctamente, pero sí sé que fue difícil hacer que JS mapee en una nueva matriz, ya que aparentemente .mapomite valores indefinidos. Si alguien ve alguna forma de mejorar, o defectos, no dude en hacérmelo saber.

hierba carbonizada
fuente
123 bytes:(n,t,s,A=f=>Array(t-1).fill(0).map(f),r=A($=>Math.random()*251))=> A((l,i,_,p=0)=>(r.map((k,c)=>p+=k*Math.pow(i,c)),s+p))
Dendrobium
No estás usando n, lo que parece incorrecto. Su código también parece estar asumiendo una indexación basada en 1. [...Array()]es un poco más corto que fiil(). Además, las dos últimas líneas se pueden reducir areturn _.map(f);
Neil
3

C #, 138 134 bytes

(n,t,s)=>new int[n+1].Select((_,x)=>(s+new int[t-1].Select(k=>new Random(e).Next(251)).Select((c,i)=>c*Math.Pow(x+1,i+1)).Sum())%251);

C # lambda donde están las entradas inty la salida es un IEnumerable<double>. Puedes probar mi código en .NetFiddle .

No estoy 100% seguro de la validez de mi algoritmo, comente si entendí mal algo.

4 bytes guardados con el truco de @ raggy .

aloisdg dice Reinstate Monica
fuente
3

MATL , 20 19 bytes

251tliq3$Yrihi:ZQw\

Orden de entrada es t, s, n.

Pruébalo en línea!

Explicación

251t    % Push 251 twice
l       % Push 1
iq      % Take input t. Subtract 1
3$Yr    % Generate t-1 random integers in [1 2 ... 251]
ih      % Take input s. Concatenate with the random integers
i:      % Take input n. Generate range [1 2 ... n]
ZQ      % Evvaluate polynomial at those values
w       % Swap to move copy og 251 to the top of the stack
\       % Modulo. Implicitly display
Luis Mendo
fuente
1

JavaScript (ES6), 116 bytes

(n,t,s)=>[...Array(n)].map((_,i)=>++i&&t.reduce((r,a)=>r*i+a)%251,t=[...Array(t)].map(_=>--t?Math.random()*251|0:s))

Me gustaría pensar que este es uno de los raros casos en los que reducelate map.

Neil
fuente
1

Python 3 con NumPy , 103 bytes

from numpy import*
lambda n,t,s:[poly1d(append(random.randint(0,251,t-1),s))(i+1)%251for i in range(n)]

Puedo decir honestamente que nunca esperé usar NumPy para el golf de código ...

Una función anónima que toma datos a través de argumentos y devuelve una lista

Cómo funciona

from numpy import*         Import everything in the NumPy library
lambda n,t,s...            Function with input number of players n, threshold value t and
                           secret s
random.randint(0,251,t-1)  Generate a NumPy array R of t-1 random integers in [0,250]
append(...,s)              Append s to R
poly1d(...)                Generate a polynomial p of order t-1 with coefficients R and
                           constant term s
...for i in range(n)       For all integers i in [0,n-1]...
...(i+1)                   ...evaluate p(i+1), so for all integers in [1,n]...
...%251                    ...and take modulo 251
...:[...]                  return as list

Pruébalo en Ideone

TheBikingViking
fuente
1

J , 32 30 bytes

251|(1+i.@{.)p.~{:0}251?@#~1&{

Toma una lista con los valores n , t y s .

Ahorró 2 bytes usando la idea de reemplazar en el índice 0 de la solución de @ Dennis .

Explicación

251|(1+i.@{.)p.~{:0}251?@#~1&{  Input: [n t s]
                           1&{  Select at index 1 (t)
                    251  #~     Create that many copies of 251
                       ?@       Generate that many random integers in [0, 251)
                {:              Get the tail of the input (s)
                  0}            Replace the value at index 0 of the random integer list
                                with s to make a coefficient list of the polynomial
          {.                    Get the head of the input (n)
       i.@                      Make the range [0, n-1]
     1+                         Add 1 to each to get [1, n]
             p.~                Evaluate the polynomial at each value [1, n]
251|                            Take each value mod 251 and return
millas
fuente
0

Java 8, 224 bytes:

(n,t,s)->{int[]W=new int[t-1];for(int i=0;i<t-1;i++){W[i]=new java.util.Random().nextInt(251);};long[]O=new long[n];for(int i=1;i<=n;i++){long T=0;for(int h=1;h<t;h++){T+=W[h-1]*Math.pow(i,h);}O[i-1]=((T+s)%251);}return O;};

Una expresión lambda de Java 8. Emite una matriz de enteros separados por comas y funciona perfectamente hasta que los valores en la matriz de salida alcanzan más allá del rango del longtipo de datos de Java , o entero de 64 bits, sobre el cual -200se emite en la matriz.

¡Pruébelo en línea! (Ideone)

R. Kap
fuente