(import (chicken random) srfi-1 (math base) (math number-theory))

(define (make-polynom x0 coefficients)
  (lambda (x)
    (apply + `(,x0 ,@(map (lambda (c i) (* c (expt x i))) coefficients (iota (length coefficients) 1))))))

(define (make-polynom-in-field x0 coefficients p)
  (let ((f (make-polynom x0 coefficients)))
    (lambda (x) (modulo (f x) p))))

(define (split-secret secret shares needed-for-recovery)
  (let* ((number-of-coefficients (- shares needed-for-recovery))
         (p (random-prime (expt 2 128)))
         (cs (list-tabulate number-of-coefficients (lambda (i) (random-bits 128))))
         (f (make-polynom-in-field secret cs p)))
    (append (list 'n shares 'k needed-for-recovery 'p p 'shares)
                 (list-tabulate shares (lambda (i) (cons i (f (add1 i))))))))