new_contents: # -*- coding: utf-8 -*-
  """
      Secret Sharing
      ~~~~~
  
      :copyright: (c) 2014 by Halfmoon Labs
      :license: MIT, see LICENSE for more details.
  """
  
  from random import randint
  
  
  def egcd(a, b):
      if a == 0:
          return (b, 0, 1)
      else:
          g, y, x = egcd(b % a, a)
          return (g, x - (b // a) * y, y)
  
  
  def mod_inverse(k, prime):
      k = k % prime
      if k < 0:
          r = egcd(prime, -k)[2]
      else:
          r = egcd(prime, k)[2]
      return (prime + r) % prime
  
  
  def random_polynomial(degree, intercept, upper_bound):
      """ Generates a random polynomial with positive coefficients.
      """
      if degree < 0:
          raise ValueError('Degree must be a non-negative number.')
      coefficients = [intercept]
      for i in range(degree):
          random_coeff = randint(0, upper_bound - 1)
          coefficients.append(random_coeff)
      return coefficients
  
  
  def get_polynomial_points(coefficients, num_points, prime):
      """ Calculates the first n polynomial points.
          [ (1, f(1)), (2, f(2)), ... (n, f(n)) ]
      """
      points = []
      for x in range(1, num_points + 1):
          # start with x=1 and calculate the value of y
          y = coefficients[0]
          # calculate each term and add it to y, using modular math
          for i in range(1, len(coefficients)):
              exponentiation = (x**i) % prime
              term = (coefficients[i] * exponentiation) % prime
              y = (y + term) % prime
          # add the point to the list of points
          points.append((x, y))
      return points
  
  
  def modular_lagrange_interpolation(x, points, prime):
      # break the points up into lists of x and y values
      x_values, y_values = zip(*points)
      # initialize f(x) and begin the calculation: f(x) = SUM( y_i * l_i(x) )
      f_x = 0
      for i in range(len(points)):
          # evaluate the lagrange basis polynomial l_i(x)
          numerator, denominator = 1, 1
          for j in range(len(points)):
              # don't compute a polynomial fraction if i equals j
              if i == j:
                  continue
              # compute a fraction and update the existing numerator + denominator
              numerator = (numerator * (x - x_values[j])) % prime
              denominator = (denominator * (x_values[i] - x_values[j])) % prime
          # get the polynomial from the numerator + mod inverse of the denominator
          lagrange_polynomial = numerator * mod_inverse(denominator, prime)
          # multiply the current y and the evaluated polynomial and add it to f(x)
          f_x = (prime + f_x + (y_values[i] * lagrange_polynomial)) % prime
      return f_x
  
  
  def secret_int_to_points(secret_int, point_threshold, num_points, prime):
      """ Split a secret (integer) into shares (pair of integers / x,y coords).
  
          Sample the points of a random polynomial with the y intercept equal to
          the secret int.
      """
      if point_threshold < 2:
          raise ValueError("Threshold must be >= 2.")
      if point_threshold > num_points:
          raise ValueError("Threshold must be < the total number of points.")
      if secret_int > prime:
          raise ValueError("Error! Secret is too long for share calculation!")
      coefficients = random_polynomial(point_threshold - 1, secret_int, prime)
      points = get_polynomial_points(coefficients, num_points, prime)
      return points
  
  
  def points_to_secret_int(points, prime):
      """ Join int points into a secret int.
  
          Get the intercept of a random polynomial defined by the given points.
      """
      if not isinstance(points, list):
          raise ValueError("Points must be in list form.")
      for point in points:
          if not isinstance(point, tuple) and len(point) == 2:
              raise ValueError("Each point must be a tuple of two values.")
          if not isinstance(point[0], int) and isinstance(point[1], int):
              raise ValueError("Each value in the point must be an int.")
      x_values, y_values = zip(*points)
      free_coefficient = modular_lagrange_interpolation(0, points, prime)
      secret_int = free_coefficient  # the secret int is the free coefficient
      return secret_int
  
subject: Create secretsharing.py