Biorąc pod uwagę n(liczbę graczy), t(wartość progową) i s(sekret), ngeneruj sekrety generowane przez algorytm Shamir's Secret Sharing .
Algorytm
Na potrzeby tego wyzwania obliczenia zostaną wykonane w GF (251) (skończone pole wielkości 251, znane również jako liczby całkowite mod 251 ). Zazwyczaj pole jest wybierane w taki sposób, że jego wielkość jest liczbą pierwszą znacznie większą niż n. Aby uprościć wyzwanie, wielkość pola będzie stała. 251został wybrany, ponieważ jest największą liczbą pierwszą reprezentowaną przez 8-bitową liczbę całkowitą bez znaku.
- Generuj
t-1losowe liczby całkowite z zakresu (włącznie)[0, 250]. Oznacz je do 1 za pomocą t-1 . - Skonstruować
t-1algebraicznej p użyciusjako wartość stałą i liczb całkowitych z etapu 1, tak jak współczynniki uprawnieńx: f (x) = y + x * a 1 + x 2 * a 2 + ... + X t- 1 * a t-1 . - Wyjście
(f(z) mod 251)dla każdegozz zakresu (włącznie)[1, n].
Wdrożenie referencyjne
#!/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)Weryfikacja
Do weryfikacji wyników można użyć następującego fragmentu stosu:
Zasady
sbędzie nieujemną liczbę całkowitą, mniejszą251initbędzie całkowite dodatnie mniej niż251i więcej niż1. Ponadto masz gwarancję, że dane wejściowe są prawidłowe (znaczeniet <= n).- Dane wejściowe i wyjściowe mogą mieć dowolny rozsądny, jednoznaczny i spójny format.
- Próbki liczb losowych należy próbkować z równomiernego rozkładu - każda możliwa wartość powinna mieć jednakowe prawdopodobieństwo wyboru.
@orlp Fair point.
—
Mego
Jakieś przypadki testowe?
—
Leaky Nun
@LeakyNun Ponieważ to pytanie jest oznaczone losowo , uważam, że fragment weryfikacyjny jest o wiele bardziej wartościowy niż przypadki testowe, które będą różne dla każdego uruchomienia.
—
FryAmTheEggman
zif(z)? Jeśli wydrukuję tablicęf(z)s po kolei,zwynika to z indeksu.[[1, 5], [2, 2], [3, 9], [4, 14]]nie zawiera więcej informacji niż[5, 2, 9, 14].