17
\$\begingroup\$

Given n (the number of players), t (the threshold value), and s (the secret), output the n secrets generated by Shamir's Secret Sharing algorithm.

The Algorithm

For the purposes of this challenge, the computations will be done in GF(251) (the finite field of size 251, otherwise known as the integers mod 251). Ordinarily, the field would be chosen such that its size is a prime much greater than n. To simplify the challenge, the field size will be constant. 251 has been chosen because it is the largest prime representable by an 8-bit unsigned integer.

  1. Generate t-1 random integers in the (inclusive) range [0, 250]. Label these a1 through at-1.
  2. Construct a t-1th degree polynomial using s as the constant value and the random integers from step 1 as the coefficients of the powers of x: f(x) = s + x*a1 + x2*a2 + ... + xt-1*at-1.
  3. Output (f(z) mod 251) for each z in the (inclusive) range [1, n].

Reference Implementation

#!/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)

Verification

The following Stack Snippet can be used to verify outputs:

var validate = function() {
  $('#nts-error').attr('hidden', parseInt($('#n').val()) >= parseInt($('#t').val()));
  $('#check').prop('disabled', parseInt($('#n').val()) < parseInt($('#t').val()));
};

// the following function is taken from https://rosettacode.org/wiki/Combinations#JavaScript
var combinations = function(arr, k) {
  var i,
    subI,
    ret = [],
    sub,
    next;
  for (i = 0; i < arr.length; i++) {
    if (k === 1) {
      ret.push([arr[i]]);
    } else {
      sub = combinations(arr.slice(i + 1, arr.length), k - 1);
      for (subI = 0; subI < sub.length; subI++) {
        next = sub[subI];
        next.unshift(arr[i]);
        ret.push(next);
      }
    }
  }
  return ret;
};

// The following code is taken from https://en.wikipedia.org/wiki/Shamir%27s_Secret_Sharing#Javascript_example with the modification that the prime is 251, not 257

var prime = 251;

/* Gives the decomposition of the gcd of a and b.  Returns [x,y,z] such that x = gcd(a,b) and y*a + z*b = x */
function gcdD(a, b) {
  if (b == 0) return [a, 1, 0];
  else {
    var n = Math.floor(a / b),
      c = a % b,
      r = gcdD(b, c);
    return [r[0], r[2], r[1] - r[2] * n];
  }
}

/* Gives the multiplicative inverse of k mod prime.  In other words (k * modInverse(k)) % prime = 1 for all prime > k >= 1  */
function modInverse(k) {
  k = k % prime;
  var r = (k < 0) ? -gcdD(prime, -k)[2] : gcdD(prime, k)[2];
  return (prime + r) % prime;
}

/* Join the shares into a number */
function join(shares) {
  var accum, count, formula, startposition, nextposition, value, numerator, denominator;
  for (formula = accum = 0; formula < shares.length; formula++) {
    /* Multiply the numerator across the top and denominators across the bottom to do Lagrange's interpolation
     * Result is x0(2), x1(4), x2(5) -> -4*-5 and (2-4=-2)(2-5=-3), etc for l0, l1, l2...
     */
    for (count = 0, numerator = denominator = 1; count < shares.length; count++) {
      if (formula == count) continue; // If not the same value
      startposition = shares[formula][0];
      nextposition = shares[count][0];
      numerator = (numerator * -nextposition) % prime;
      denominator = (denominator * (startposition - nextposition)) % prime;
    }
    value = shares[formula][1];
    accum = (prime + accum + (value * numerator * modInverse(denominator))) % prime;
  }
  return accum;
}

$('#check').click(
  function() {
    var good = true;
    var problem = [];
    var n = parseInt($('#n').val());
    var t = parseInt($('#t').val());
    var s = parseInt($('#s').val());
    combinations([...Array(n + 1).keys()].slice(1), t).forEach(
      function(xArr) {
        var xfArr = xArr.map(
          function(x) {
            return [x, parseInt($('#f' + x).val())];
          }
        );
        var L = join(xfArr);
        if (L !== s) {
          good = false;
          problem.push(xArr);
        }
      }
    );
    $('#valid').html(good ? "True" : ("False (problematic secret sets: {" + problem.map(
      function(elem) {
        return "[" + elem.join(', ') + "]";
      }) + "})"));
  }
);

$('#n').change(
  function() {
    var inputHTML = "";
    for (var i = 1; i <= parseInt($('#n').val()); i++) {
      inputHTML += 'f(' + i + '): <input type="number" min="0" max="250" value="0" id="f' + i + '"><br>\r\n';
    }
    $('#inputs').html(inputHTML);
    validate();
  }
);

$('#t').change(
  function() {
    validate();
  }
);
<script src="https://ajax.googleapis.com/ajax/libs/jquery/2.1.1/jquery.min.js"></script>
n:
<input type="number" min="2" max="250" value="6" id="n">t:
<input type="number" min="2" max="250" value="3" id="t">s:
<input type="number" min="0" max="250" value="230" id="s">
<br>
<div id="nts-error" hidden="true">t must be less than or equal to n!</div>
<br>
<br>
<div id="inputs">
  f(1):
  <input type="number" min="0" max="250" value="35" id="f1">
  <br>f(2):
  <input type="number" min="0" max="250" value="95" id="f2">
  <br>f(3):
  <input type="number" min="0" max="250" value="159" id="f3">
  <br>f(4):
  <input type="number" min="0" max="250" value="227" id="f4">
  <br>f(5):
  <input type="number" min="0" max="250" value="48" id="f5">
  <br>f(6):
  <input type="number" min="0" max="250" value="124" id="f6">
</div>
<br>
<input type="submit" id="check" value="Verify">
<br>
<br>Valid:
<div id="valid"></div>

Rules

  • s will be a non-negative integer less than 251, and n and t will be positive integers less than 251 and greater than 1. Furthermore, you are guaranteed that the inputs are valid (meaning t <= n).
  • Input and output can be in any reasonable, unambiguous, and consistent format.
  • Random numbers are to be sampled from a uniform distribution - each possible value should have equal probability of being chosen.
\$\endgroup\$
  • 1
    \$\begingroup\$ Do we have to output z and f(z)? If I print an array of f(z)s in order, z is implied by index. [[1, 5], [2, 2], [3, 9], [4, 14]] does not contain more information than [5, 2, 9, 14]. \$\endgroup\$ – orlp Jul 7 '16 at 15:44
  • 1
    \$\begingroup\$ Challenge for doing the inverse. \$\endgroup\$ – FryAmTheEggman Jul 7 '16 at 15:45
  • \$\begingroup\$ @orlp Fair point. \$\endgroup\$ – Mego Jul 7 '16 at 15:46
  • \$\begingroup\$ Any testcases ? \$\endgroup\$ – Leaky Nun Jul 7 '16 at 15:47
  • 4
    \$\begingroup\$ @LeakyNun Since this question is tagged random, I think the verification snippet is much more valuable than test cases that will vary for each run. \$\endgroup\$ – FryAmTheEggman Jul 7 '16 at 15:50

12 Answers 12

13
\$\begingroup\$

Jelly, 15 bytes

251©xX€⁵0¦ḅЀ%®

Expects t, n, and s as command-line arguments. Try it online!

How it works

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.
\$\endgroup\$
  • 3
    \$\begingroup\$ Replacing the last integer is so elegant :) \$\endgroup\$ – Lynn Jul 7 '16 at 17:26
8
\$\begingroup\$

Mathematica, 59 56 bytes

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

Takes three arguments in the order t, n, and s. Constructs a 2d-array with n rows and t-1 columns. Each row vector j, numbered from 1 thru n, contains the powers of j thru jt-1. Then a vector of random integer coefficients in the range 0 thru 250 is created with t-1 values. That is matrix-multiplied with the 2d-array, and then s is added element-wise and taken module 251 to get the value of the polynomial at each of the n points.

\$\endgroup\$
  • 1
    \$\begingroup\$ Was just about to post a 79-byte answer, nice trick with Sum! \$\endgroup\$ – LegionMammal978 Jul 7 '16 at 15:58
  • 1
    \$\begingroup\$ I've got a different approach, but it's currently two bytes longer. Maybe you have an idea how to shorten it: Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]& \$\endgroup\$ – Martin Ender Jul 7 '16 at 16:08
5
\$\begingroup\$

CJam, 27 25 bytes

{,:)@({;251mr}%@+fb251f%}

Test it here.

\$\endgroup\$
3
\$\begingroup\$

Pyth, 24 bytes

J+EmOK251tEm%s.e*b^dkJKS

Try it online!

Input order: n s t separated by linefeed.

\$\endgroup\$
  • \$\begingroup\$ arrrrrgh, ninja'd cuz i went to get a cookie \$\endgroup\$ – Maltysen Jul 7 '16 at 15:58
3
\$\begingroup\$

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

Ungolfed:

(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 _;
}

I don't know how to properly check it, but I do know that it was a pain to get JS to map across a new array since apparently .map skips undefined values. If anyone sees any ways to improve, or flaws, don't hesitate to let me know.

\$\endgroup\$
  • \$\begingroup\$ 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)) \$\endgroup\$ – Dendrobium Jul 7 '16 at 17:15
  • \$\begingroup\$ You're not using n, which seems wrong. Your code also seems to be assuming 1-based indexing. [...Array()] is slightly shorter than fiil(). Also, the last two lines can be reduced to return _.map(f); \$\endgroup\$ – Neil Jul 8 '16 at 9:32
3
\$\begingroup\$

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 where inputs are int and output is an IEnumerable<double>. You can try my code on .NetFiddle.

I am not 100% sure about the validity of my algorithm, please comment if I misunderstood something.

4 bytes saved with @raggy's trick.

\$\endgroup\$
3
\$\begingroup\$

MATL, 20 19 bytes

251tliq3$Yrihi:ZQw\

Input order is t, s, n.

Try it online!

Explanation

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
\$\endgroup\$
2
\$\begingroup\$

Julia, 48 bytes

f(n,t,s)=(1:n).^(0:t-1)'*[s;rand(0:250,t-1)]%251

Try it online!

\$\endgroup\$
1
\$\begingroup\$

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

I'd like to think this is one of the rare cases where reduce beats map.

\$\endgroup\$
1
\$\begingroup\$

Python 3 with 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)]

I can honestly say that I never expected to use NumPy for code golf...

An anonymous function that takes input via argument and returns a list.

How it works

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

Try it on Ideone

\$\endgroup\$
1
\$\begingroup\$

J, 32 30 bytes

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

Takes a list with the values n, t, and s.

Saved 2 bytes by using the replace at index 0 idea from @Dennis's solution.

Explanation

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
\$\endgroup\$
0
\$\begingroup\$

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

A Java 8 lambda expression. Outputs a comma separated integer array, and works perfectly until values in the output array reach beyond the range of the Java's long, or 64-bit signed integer, data type, upon which -200 is output into the array.

Try It Online! (Ideone)

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.