[Summary view] [Print] [Text view]

   1  <?php
   2  
   3  /**
   4   * PHP Montgomery Modular Exponentiation Engine with interleaved multiplication
   5   *
   6   * PHP version 5 and 7
   7   *
   8   * @category  Math
   9   * @package   BigInteger
  10   * @author    Jim Wigginton <[email protected]>
  11   * @copyright 2017 Jim Wigginton
  12   * @license   http://www.opensource.org/licenses/mit-license.html  MIT License
  13   * @link      http://pear.php.net/package/Math_BigInteger
  14   */
  15  
  16  namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions;
  17  
  18  use phpseclib3\Math\BigInteger\Engines\PHP;
  19  
  20  /**
  21   * PHP Montgomery Modular Exponentiation Engine with interleaved multiplication
  22   *
  23   * @package PHP
  24   * @author  Jim Wigginton <[email protected]>
  25   * @access  public
  26   */
  27  abstract class MontgomeryMult extends Montgomery
  28  {
  29      /**
  30       * Montgomery Multiply
  31       *
  32       * Interleaves the montgomery reduction and long multiplication algorithms together as described in
  33       * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36}
  34       *
  35       * @see self::_prepMontgomery()
  36       * @see self::_montgomery()
  37       * @access private
  38       * @param array $x
  39       * @param array $y
  40       * @param array $m
  41       * @param class-string<PHP> $class
  42       * @return array
  43       */
  44      public static function multiplyReduce(array $x, array $y, array $m, $class)
  45      {
  46          // the following code, although not callable, can be run independently of the above code
  47          // although the above code performed better in my benchmarks the following could might
  48          // perform better under different circumstances. in lieu of deleting it it's just been
  49          // made uncallable
  50  
  51          static $cache = [
  52              self::VARIABLE => [],
  53              self::DATA => []
  54          ];
  55  
  56          if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
  57              $key = count($cache[self::VARIABLE]);
  58              $cache[self::VARIABLE][] = $m;
  59              $cache[self::DATA][] = self::modInverse67108864($m, $class);
  60          }
  61  
  62          $n = max(count($x), count($y), count($m));
  63          $x = array_pad($x, $n, 0);
  64          $y = array_pad($y, $n, 0);
  65          $m = array_pad($m, $n, 0);
  66          $a = [self::VALUE => self::array_repeat(0, $n + 1)];
  67          for ($i = 0; $i < $n; ++$i) {
  68              $temp = $a[self::VALUE][0] + $x[$i] * $y[0];
  69              $temp = $temp - $class::BASE_FULL * ($class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
  70              $temp = $temp * $cache[self::DATA][$key];
  71              $temp = $temp - $class::BASE_FULL * ($class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31));
  72              $temp = $class::addHelper($class::regularMultiply([$x[$i]], $y), false, $class::regularMultiply([$temp], $m), false);
  73              $a = $class::addHelper($a[self::VALUE], false, $temp[self::VALUE], false);
  74              $a[self::VALUE] = array_slice($a[self::VALUE], 1);
  75          }
  76          if (self::compareHelper($a[self::VALUE], false, $m, false) >= 0) {
  77              $a = $class::subtractHelper($a[self::VALUE], false, $m, false);
  78          }
  79          return $a[self::VALUE];
  80      }
  81  }