Rev 846 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
827 | daniel-mar | 1 | <?php |
2 | |||
3 | /** |
||
4 | * PHP Montgomery Modular Exponentiation Engine with interleaved multiplication |
||
5 | * |
||
6 | * PHP version 5 and 7 |
||
7 | * |
||
874 | daniel-mar | 8 | * @category Math |
9 | * @package BigInteger |
||
827 | daniel-mar | 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 | * |
||
874 | daniel-mar | 23 | * @package PHP |
827 | daniel-mar | 24 | * @author Jim Wigginton <terrafrost@php.net> |
874 | daniel-mar | 25 | * @access public |
827 | daniel-mar | 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() |
||
874 | daniel-mar | 37 | * @access private |
827 | daniel-mar | 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 | } |