<?php

class ShamirSecretSharing_Testing
{
   protected $prime = 2621;
   public function encryptSecret($secret, $threshold, $shares)
   {
    		$coefficients = $this -> generatePolynomial($secret, $threshold, $this->prime);
//     		$coefficients = $this -> generatePolynomial($secret, $threshold, $prime);
    		print("Coefficients are:\n");
    		foreach ($coefficients as $val){
            	print($val);
            	print("\n");
            }
            $points = $this -> createShares($coefficients, $shares, $this->prime);
                		print("Shares created are:\n");
                		for($row=0; $row< $shares; $row++)
                        {
                            for($col=0; $col<2; $col++){
                                print($points[$row][$col]);
                                print("\t");
                            }
                            print("\n");
                        }
    		//$points = $this -> createShares($coefficients, $shares, $prime);
    		return $points;
   }


    public function generatePolynomial($secret, $threshold, $prime)
    {
           $coefficients = [$secret];

           for($i = 0; $i < $threshold-1; $i++){
            	$coefficients[] = random_int(0, $prime-1);
           }
           return $coefficients;
    }

    public function yCoordinate($x, $coefficients, $prime){
        $y = 0;

        for ($i = 0; $i < count($coefficients); $i++)
        {
            $exp = pow($x, $i);
            $val = $coefficients[$i] * $exp;
            $y = $y + $val ;
        }
        return $y % $prime;
    }


    public function createShares($coefficients, $shares, $prime){

         $points = [];
         for($i = 1; $i <= $shares; $i++)
         {
             $x = $i;
             $y = $this -> yCoordinate($x, $coefficients, $prime);
             $points[] = [$x , $y];
         }
         return $points;
    }

    //public function decryptSecret($points){
    public function decryptSecret($points){

    	    $secret = $this -> reconstruct($points, 0, $this->prime);
    	    print("\nThe secret is\n");
    	    print($secret);
    	    print("\n");
    }

    public function reconstruct($points, $x, $prime){

    	    $xArray = [];
    	    $yArray = [];
    	    $fx	= 0;

            foreach ($points as $p)
            {
                $xArray[] = $p[0];
            	$yArray[] = $p[1];
            }

            $denominator = 1;
            $numerator = 0;
            $numeratorList[] = array();

            for ($i = 0; $i < count($points); $i++)
            {
                $xList = $xArray;
                $curr = $xList[$i];
                unset($xList[$i]);
                $numeratorList[$i] = 1;
                $denominatorList[$i] = 1;

                foreach($xList as $xVal){
                   $numeratorList[$i] = $this->multiply($numeratorList[$i], $x - $xVal);
                   $denominatorList[$i] = $this->multiply($denominatorList[$i],$curr - $xVal);
                }

            }


            foreach($denominatorList as $den){
                   $denominator*= $den;
            }


            for ($i = 0; $i < count($points); $i++)
            {
                $temp = $numeratorList[$i] * $denominator * $yArray[$i];
                $first = $this ->checkNegative($temp, $prime);
                $numerator += $this->modInverse($first, $denominatorList[$i], $prime);
            }


            $final = $this->modInverse($numerator, $denominator, $prime);
            return $this->checkNegative($final, $prime);

            //return ($this->modInverse($numerator, $denominator, $prime) + $prime) % $prime;
    	}

    function checkNegative($sum, $prime){
        if($sum < 0){
            return ($prime + ($sum % $prime)) % $prime;
        }
        return $sum % $prime;
    }

   function multiply($product1, $product2){
        return $product1 * $product2;
   }

    function modInverse($numerator, $denominator, $p)
    {
        $res = $this->gcdExtended($denominator, $p)[0];
        return $numerator * $res;
    }

    // function for extended Euclidean Algorithm
    function gcdExtended($a, $b)
    {
            $x = 0;
            $last_x = 1;
            $y = 1;
            $last_y = 0;
            while($b != 0){
                $quot = floor($a / $b);

                $temp3 = $b;
                $b = $a % $b;
                $a = $temp3;
                if ($b < 0)
                {
                    $b = $b + $a;
                }

                $temp1 = $x;
                $x = $last_x - $quot * $x;
                $last_x = $temp1;

                $temp2 = $y;
                $y = $last_y - $quot * $y;
                $last_y = $temp2;
            }
        return [$last_x, $last_y];
    }
    }

    $test = new ShamirSecretSharing_Testing();

        $points = $test -> encryptSecret(1994, 3, 5);
        $getPoints[] = $points[0];
        $getPoints[] = $points[2];
        $getPoints[] = $points[3];
        $secret = $test -> decryptSecret($getPoints);
?>