1<?php
2
3/**
4 * PHP Montgomery Modular Exponentiation Engine
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;
17
18use phpseclib3\Math\BigInteger\Engines\Engine;
19use phpseclib3\Math\BigInteger\Engines\PHP;
20use phpseclib3\Math\BigInteger\Engines\PHP\Reductions\PowerOfTwo;
21
22/**
23 * PHP Montgomery Modular Exponentiation Engine
24 *
25 * @package PHP
26 * @author  Jim Wigginton <terrafrost@php.net>
27 * @access  public
28 */
29abstract class Montgomery extends Base
30{
31    /**
32     * Test for engine validity
33     *
34     * @return bool
35     */
36    public static function isValidEngine()
37    {
38        return static::class != __CLASS__;
39    }
40
41    /**
42     * Performs modular exponentiation.
43     *
44     * @template T of Engine
45     * @param Engine $x
46     * @param Engine $e
47     * @param Engine $n
48     * @param class-string<T> $class
49     * @return T
50     */
51    protected static function slidingWindow(Engine $x, Engine $e, Engine $n, $class)
52    {
53        // is the modulo odd?
54        if ($n->value[0] & 1) {
55            return parent::slidingWindow($x, $e, $n, $class);
56        }
57        // if it's not, it's even
58
59        // find the lowest set bit (eg. the max pow of 2 that divides $n)
60        for ($i = 0; $i < count($n->value); ++$i) {
61            if ($n->value[$i]) {
62                $temp = decbin($n->value[$i]);
63                $j = strlen($temp) - strrpos($temp, '1') - 1;
64                $j += $class::BASE * $i;
65                break;
66            }
67        }
68        // at this point, 2^$j * $n/(2^$j) == $n
69
70        $mod1 = clone $n;
71        $mod1->rshift($j);
72        $mod2 = new $class();
73        $mod2->value = [1];
74        $mod2->lshift($j);
75
76        $part1 = $mod1->value != [1] ? parent::slidingWindow($x, $e, $mod1, $class) : new $class();
77        $part2 = PowerOfTwo::slidingWindow($x, $e, $mod2, $class);
78
79        $y1 = $mod2->modInverse($mod1);
80        $y2 = $mod1->modInverse($mod2);
81
82        $result = $part1->multiply($mod2);
83        $result = $result->multiply($y1);
84
85        $temp = $part2->multiply($mod1);
86        $temp = $temp->multiply($y2);
87
88        $result = $result->add($temp);
89        list(, $result) = $result->divide($n);
90
91        return $result;
92    }
93}
94