shamir_secret_sharing.cpp

// (k,n)-threshold scheme
#include<iostream>
#include<stdio.h>
#include <random>
#include <vector>
#include <cmath>
using namespace std;

#define prime  65537

void generateShare(vector<int> &share, int k, int n, int data);
double recoveryData(int x[], vector<int> &y, int k);
int f(int coefficient[], int k, int data, int x);

int main(){
    vector<int> share,point;
    int k, n, data;
    double rdata;
    
    k = 5;
    n = 10;
    printf("***(%d,%d)--threshold scheme***\n", k, n);
    data = 12345;
    printf("data=%d\n", data);
    
    generateShare(share, k, n, data);
    int x[] = {1,2,3,4,5,6,7,8,9,10};
    rdata = recoveryData(x, share, k);
    printf("recovered data=%lf\n", rdata);
    return 0;
}

void generateShare(vector<int> &share, int k, int n, int data){
    int coefficients[k];

    std::random_device rnd;
    std::mt19937 mt(rnd());
    std::uniform_int_distribution<> rand_(1, prime-1);

    for (int i = 0; i < k; i++) {
        coefficients[i] = rand_(mt);
    }
    for (int i = 0; i < n; i++) {
        share.push_back(f(coefficients, k, data, i+1));
        printf("%d-th share: %d\n", i+1, share[i]);
    }
}

int f(int coefficient[], int k, int data, int x){
    int y = data;
    for (int i=0;i < k-1;i++){
        y += coefficient[i] * pow(x, i+1);
    }
    return y;
}

double recoveryData(int x[], vector<int> &y, int k)
{
    double s, p;
    int i, j;
    int t = 0;
    
    s = 0.0;

    for (i = 0; i < k; i++) {
        p = y[x[i]-1];
        for (j = 0; j < k; j++) {
            if (i != j){
                p *= (double)(t - x[j]) / (double)(x[i] - x[j]);
            }
        }
        s += p;
    }

    return s;
}

I refer to the blog post "https://www.mk-mode.com/octopress/2013/03/10/cpp-interpolate-lagrange/" (Lagrange polynomial)