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