Wankan

Polynomial Secret Keys

Sep 19th, 2020 (edited)
1,024
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1.  
  2. import {lstsq} from "adv_math.cf"
  3. import {Tensor, arange} from "ds.cf"
  4.  
  5. data Point = (Num x, Num y)
  6.  
  7. -- Solving for the secret
  8.  
  9. points_to_xy_tensors :: [Points] ->> (Tensor.1D, Tensor.1D)
  10. pts => (Tensor.1D pts@\.x, Tensor.1D pts@\.y)
  11.  
  12. polynomial :: Tensor.1D, Tensor.Scalar ->> Tensor.Scalar
  13. -- P here is the list of coefficients, starting from the x^0 coef
  14. P, x => zip P [0..] >\ (y, (p, i) => y + p * x ** i) 0
  15.  
  16. vandermonde_matrix :: Int, Tensor.1D ->> Tensor.2D
  17. N, x => (x ** (arange N)[:, Empty]).T
  18.  
  19. polyfit_weights :: Tensor.1D, Tensor.1D, Int ->> Tensor.1D
  20. xs, ys, n => lstqs (_vm xs) ys
  21. where _vm = vandermonde_matrix n
  22.  
  23. try_to_get_secret :: [Point] ->> Num
  24. keys => polynomial (polyfit_weights xs ys keys.length) 0
  25. where xs, ys = points_to_xy_tensors keys
  26.  
  27. -- Generating the secret / keys
  28.  
  29. WEIGHT_HIGHER_BOUND = Static 3
  30. WEIGHT_LOWER_BOUND = Static -3
  31. KEY_HIGHER_BOUND = Static 100
  32. KEY_LOWER_BOUND = Static 100
  33.  
  34. random_weights :: Int ->> Random Tensor.1D
  35. n => Tensor.Random.rand WEIGHT_LOWER_BOUND WEIGHT_HIGHER_BOUND [n]
  36.  
  37. random_polynomial :: Int ->> Random (Tensor.Scalar ->> Tensor.Scalar)
  38. n => polynomial (random_weights n) <0?>
  39.  
  40. polynomial_with_secret :: Num, Int ->> Random (Tensor.Scalar ->> Tensor.Scalar)
  41. secret, n => polynomial Tensor.1D [secret, ... random_weights n-1] <0?>
  42.  
  43. get_keys :: (Tensor.Scalar ->> Tensor.Scalar), Int ->> Random [Tensor.Scalar]
  44. f, n ~> {
  45.     f, n => f, Tensor.Random.rand KEY_LOWER_BOUND KEY_HIGHER_BOUND [n],
  46.     f, r => r @\ (x => Point(x, f x))
  47. }
RAW Paste Data