A toy Shamir Secret Sharing implementation in F#

ShamirSecretSharing.fsx

open System

let inline (mod) n d=
  ((n % d) + d) % d

let order = 39367
let finiteField x = x mod order

let rec pow b = function
  | 0 -> 1
  | e -> finiteField (b * pow b (e - 1))

let createPolynomial cs x =
  cs
  |> List.mapi (fun i c -> c * (pow x i))
  |> List.sum

let createShares secret k n =
  let coeffs = [for _ in [1..k-1] do finiteField (Random.Shared.Next())]
  let f = createPolynomial (secret :: coeffs)
  [ for x in [ 1..n ] do (x, finiteField (f x)) ]

let rec extendedEuclid a b =
  match a with
  | 0 -> b, 0, 1
  | _ ->
    let gcd, x, y = extendedEuclid (b mod a) a
    gcd, y - (b / a) * x, x

let modMultInverse a p =
  let _, x, _ = extendedEuclid a p
  x

let li shares xi =
  shares
  |> List.map fst
  |> List.filter (fun xj -> xi <> xj)
  |> List.map (fun xj -> xj * (modMultInverse (finiteField (xj - xi)) order) |> finiteField)
  |> List.reduce (fun a b -> finiteField(a * b))

let recoverSecret shares =
  shares
  |> List.map (fun (xi, yi) -> yi * (li shares xi))
  |> List.sum
  |> finiteField

// test it
let shares = createShares 12344 3 7

let secrets =
  shares
  |> List.windowed 4
  |> List.map recoverSecret