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