adapter = $adapter; } /** * @param $poly * @param $polymod * @param $p * @return array */ public function polynomialReduceMod($poly, $polymod, $p) { $count_polymod = count($polymod); if (end($polymod) == 1 && $count_polymod > 1) { while (count($poly) >= $count_polymod) { if (end($poly) != 0) { for ($i = 2; $i < $count_polymod + 1; $i++) { $poly[count($poly) - $i] = $this->adapter->mod( $this->adapter->sub( $poly[count($poly) - $i], $this->adapter->mul( end($poly), $polymod[$count_polymod - $i] ) ), $p ); } } $poly = array_slice($poly, 0, count($poly) - 1); } return $poly; } throw new \InvalidArgumentException('Unable to calculate polynomialReduceMod'); } /** * @param $m1 * @param $m2 * @param $polymod * @param $p * @return array */ public function polynomialMultiplyMod($m1, $m2, $polymod, $p) { $prod = array(); $cm1 = count($m1); $cm2 = count($m2); for ($i = 0; $i < $cm1; $i++) { for ($j = 0; $j < $cm2; $j++) { $index = $i + $j; if (!isset($prod[$index])) { $prod[$index] = 0; } $prod[$index] = $this->adapter->mod( $this->adapter->add( $prod[$index], $this->adapter->mul( $m1[$i], $m2[$j] ) ), $p ); } } return $this->polynomialReduceMod($prod, $polymod, $p); } /** * @param $base * @param $exponent * @param $polymod * @param $p * @return array|int */ public function polynomialPowMod($base, $exponent, $polymod, $p) { if ($this->adapter->cmp($exponent, $p) < 0) { if ($this->adapter->cmp($exponent, 0) == 0) { return 1; } $G = $base; $k = $exponent; if ($this->adapter->cmp($this->adapter->mod($k, 2), 1) == 0) { $s = $G; } else { $s = array(1); } while ($this->adapter->cmp($k, 1) > 0) { $k = $this->adapter->div($k, 2); $G = $this->polynomialMultiplyMod($G, $G, $polymod, $p); if ($this->adapter->mod($k, 2) == 1) { $s = $this->polynomialMultiplyMod($G, $s, $polymod, $p); } } return $s; } throw new \InvalidArgumentException('Unable to calculate polynomialPowMod'); } /** * @param $a * @param $p * @return int|string */ public function squareRootModP($a, $p) { if (0 <= $a && $a < $p && 1 < $p) { if ($a == 0) { return 0; } if ($p == 2) { return $a; } $jac = $this->adapter->jacobi($a, $p); if ($jac == -1) { throw new \LogicException($a." has no square root modulo ".$p); } if ($this->adapter->mod($p, 4) == 3) { return $this->adapter->powmod($a, $this->adapter->div($this->adapter->add($p, 1), 4), $p); } if ($this->adapter->mod($p, 8) == 5) { $d = $this->adapter->powmod($a, $this->adapter->div($this->adapter->sub($p, 1), 4), $p); if ($d == 1) { return $this->adapter->powmod($a, $this->adapter->div($this->adapter->add($p, 3), 8), $p); } if ($d == $p - 1) { return $this->adapter->mod( $this->adapter->mul( $this->adapter->mul( 2, $a ), $this->adapter->powmod( $this->adapter->mul( 4, $a ), $this->adapter->div( $this->adapter->sub( $p, 5 ), 8 ), $p ) ), $p ); } //shouldn't get here } for ($b = 2; $b < $p; $b++) { if ($this->adapter->jacobi( $this->adapter->sub( $this->adapter->mul($b, $b), $this->adapter->mul(4, $a) ), $p ) == -1 ) { $f = array($a, -$b, 1); $ff = $this->polynomialPowMod( array(0, 1), $this->adapter->div( $this->adapter->add( $p, 1 ), 2 ), $f, $p ); if ($ff[1] == 0) { return $ff[0]; } // if we got here no b was found } } } throw new \InvalidArgumentException('Unable to calculate square root mod p!'); } }