Subversion Repositories oidplus

Rev

Rev 846 | Go to most recent revision | Blame | Compare with Previous | Last modification | View Log | RSS feed

  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 <terrafrost@php.net>
  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 <terrafrost@php.net>
  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. }
  82.