Секрет Шамира

17

Учитывая n(количество игроков), t(пороговое значение) и s(секрет), выведите nсекреты, сгенерированные алгоритмом Shamir's Secret Sharing .

Алгоритм

Для целей этой задачи вычисления будут выполняться в GF (251) (конечное поле размера 251, также известное как mod 251 целых чисел ). Обычно поле выбирается таким образом, чтобы его размер был больше простого числа n. Чтобы упростить задачу, размер поля будет постоянным. 251был выбран, потому что это наибольшее простое число, представимое 8-битным целым числом без знака.

  1. Генерация t-1случайных целых чисел в (включительно) диапазоне [0, 250]. Добавьте эти с 1 через в Т-1 .
  2. Построить t-1полином i-й степени, используя sв качестве значения константы и случайные целые числа из шага 1 в качестве коэффициентов степеней x: f (x) = s + x * a 1 + x 2 * a 2 + ... + x t- 1 * Т-1 .
  3. Выход (f(z) mod 251)для каждого zв (включительно) диапазоне [1, n].

Реализация эталона

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

верификация

Следующий фрагмент стека может быть использован для проверки выходных данных:

Показать фрагмент кода

правила

  • sбудет неотрицательным целым числом меньше чем 251, nи tбудет положительным целым числом меньше 251и больше чем 1. Кроме того, вы гарантированно, что входные данные являются действительными (то естьt <= n ).
  • Ввод и вывод могут быть в любом разумном, однозначном и согласованном формате.
  • Случайные числа должны выбираться из равномерного распределения - каждое возможное значение должно иметь равную вероятность выбора.
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
источник
1
Нужно ли выводить z и f(z) ? Если я печатаю массив f(z)s по порядку, zподразумевается индекс. [[1, 5], [2, 2], [3, 9], [4, 14]]не содержит больше информации, чем [5, 2, 9, 14].
orlp
1
Задача сделать обратное .
FryAmTheEggman
@orlp Честная точка зрения.
Mego
Есть тесты?
Дрянная Монахиня
4
@LeakyNun Поскольку этот вопрос помечен случайным образом , я думаю, что проверочный фрагмент гораздо более полезен, чем контрольные примеры, которые будут варьироваться для каждого прогона.
FryAmTheEggman

Ответы:

13

Желе , 15 байт

251©xX€⁵0¦ḅЀ%®

Ожидает t , n и s в качестве аргументов командной строки. Попробуйте онлайн!

Как это устроено

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.
Деннис
источник
3
Замена последнего целого числа такая элегантная :)
Линн
8

Mathematica, 59 56 байт

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

Принимает три аргумента в порядке t , n и s . Создает 2d-массив с n строками и t -1 столбцами. Каждый вектор строки j , пронумерованный от 1 до n , содержит степени от j до j t -1 . Затем создается вектор случайных целых коэффициентов в диапазоне от 0 до 250 со значениями t -1. Это умножается на матрицу с 2d-массивом, а затем добавляется s поэлементно и берется модуль 251, чтобы получить значение многочлена в каждой из n точек.

миль
источник
1
Собирался опубликовать 79-байтовый ответ, хороший трюк с Sum!
LegionMammal978
1
У меня другой подход, но сейчас он на два байта длиннее. Может быть, у вас есть идея, как сократить его:Mod[x#+#2&~Fold~RandomInteger[250,#2-1]x+#3/.x->Range@#,251]&
Мартин Эндер
3

Pyth, 24 байта

J+EmOK251tEm%s.e*b^dkJKS

Попробуйте онлайн!

Порядок ввода: n s tразделенный переводом строки.

Дрянная Монахиня
источник
arrrrrgh, ninja'd Потому что я пошел, чтобы получить печенье
Maltysen
3

JavaScript, 181 байт

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

Я не знаю, как правильно это проверить, но я знаю, что было сложно заставить JS отображать новый массив, поскольку, очевидно, .mapпропускает неопределенные значения. Если кто-нибудь увидит какие-либо способы улучшения или недостатки, не стесняйтесь, дайте мне знать.

charredgrass
источник
123 байта:(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))
Дендробиум
Вы не используете n, что кажется неправильным. Ваш код также, кажется, предполагает индексирование на основе 1. [...Array()]немного короче чем fiil(). Кроме того, последние две строки могут быть уменьшены доreturn _.map(f);
Нил
3

C #, 138 134 байта

(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 # лямбда, где входные intи выходные данные IEnumerable<double>. Вы можете попробовать мой код на .NetFiddle .

Я не уверен на 100% в правильности моего алгоритма, пожалуйста, прокомментируйте, если я что-то неправильно понял.

4 байта , сохраненный с помощью @ рэггами в трюке .

aloisdg переходит на codidact.com
источник
3

MATL , 20 19 байтов

251tliq3$Yrihi:ZQw\

Входной заказ t, s, 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
Луис Мендо
источник
1

JavaScript (ES6), 116 байт

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

Я хотел бы думать, что это один из редких случаев, когда reduceудары map.

Нил
источник
1

Python 3 с NumPy , 103 байта

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

Я могу честно сказать, что я никогда не ожидал использовать NumPy для кода гольфа ...

Анонимная функция, которая принимает входные данные через аргумент и возвращает список.

Как это устроено

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

Попробуйте это на Ideone

TheBikingViking
источник
1

J , 32 30 байт

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

Принимает список со значениями n , t и s .

Сохраненный 2 байта, используя заменить на индекс 0 идеи от @ Денниса решения .

объяснение

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
миль
источник
0

Java 8, 224 байта:

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

Java 8 лямбда-выражение. Выводит разделенный запятыми массив целых чисел и прекрасно работает до тех пор, пока значения в выходном массиве не выйдут за пределы диапазона типа данных Java longили 64-разрядного целого числа со знаком, при котором они -200выводятся в массив.

Попробуйте онлайн! (Ideone)

Р. Кап
источник