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 16namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions; 17 18use 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 */ 27abstract 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