1<?php
2
3/**
4 * BCMath Barrett 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\BCMath\Reductions;
17
18use phpseclib3\Math\BigInteger\Engines\BCMath\Base;
19
20/**
21 * PHP Barrett Modular Exponentiation Engine
22 *
23 * @package PHP
24 * @author  Jim Wigginton <terrafrost@php.net>
25 * @access  public
26 */
27abstract class Barrett extends Base
28{
29    /**
30     * Cache constants
31     *
32     * $cache[self::VARIABLE] tells us whether or not the cached data is still valid.
33     *
34     * @access private
35     */
36    const VARIABLE = 0;
37    /**
38     * $cache[self::DATA] contains the cached data.
39     *
40     * @access private
41     */
42    const DATA = 1;
43
44    /**
45     * Barrett Modular Reduction
46     *
47     * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
48     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
49     * so as not to require negative numbers (initially, this script didn't support negative numbers).
50     *
51     * Employs "folding", as described at
52     * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
53     * it, "the idea [behind folding] is to find a value x' such that x (mod m) = x' (mod m), with x' being smaller than x."
54     *
55     * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
56     * usable on account of (1) its not using reasonable radix points as discussed in
57     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
58     * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
59     * (x >> 1) + (x >> 1) != x / 2 + x / 2.  If x is even, they're the same, but if x is odd, they're not.  See the in-line
60     * comments for details.
61     *
62     * @param string $n
63     * @param string $m
64     * @return string
65     */
66    protected static function reduce($n, $m)
67    {
68        static $cache = [
69            self::VARIABLE => [],
70            self::DATA => []
71        ];
72
73        $m_length = strlen($m);
74
75        if (strlen($n) > 2 * $m_length) {
76            return bcmod($n, $m);
77        }
78
79        // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
80        if ($m_length < 5) {
81            return self::regularBarrett($n, $m);
82        }
83        // n = 2 * m.length
84
85        if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
86            $key = count($cache[self::VARIABLE]);
87            $cache[self::VARIABLE][] = $m;
88
89            $lhs = '1' . str_repeat('0', $m_length + ($m_length >> 1));
90            $u = bcdiv($lhs, $m, 0);
91            $m1 = bcsub($lhs, bcmul($u, $m));
92
93            $cache[self::DATA][] = [
94                'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1)
95                'm1' => $m1 // m.length
96            ];
97        } else {
98            extract($cache[self::DATA][$key]);
99        }
100
101        $cutoff = $m_length + ($m_length >> 1);
102
103        $lsd = substr($n, -$cutoff);
104        $msd = substr($n, 0, -$cutoff);
105
106        $temp = bcmul($msd, $m1); // m.length + (m.length >> 1)
107        $n = bcadd($lsd, $temp); // m.length + (m.length >> 1) + 1 (so basically we're adding two same length numbers)
108        //if ($m_length & 1) {
109        //    return self::regularBarrett($n, $m);
110        //}
111
112        // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
113        $temp = substr($n, 0, -$m_length + 1);
114        // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2
115        // if odd:  ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1
116        $temp = bcmul($temp, $u);
117        // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1
118        // if odd:  (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1)
119        $temp = substr($temp, 0, -($m_length >> 1) - 1);
120        // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1
121        // if odd:  (m.length - (m.length >> 1)) + m.length     = 2 * m.length - (m.length >> 1)
122        $temp = bcmul($temp, $m);
123
124        // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit
125        // number from a m.length + (m.length >> 1) + 1 digit number.  ie. there'd be an extra digit and the while loop
126        // following this comment would loop a lot (hence our calling _regularBarrett() in that situation).
127
128        $result = bcsub($n, $temp);
129
130        //if (bccomp($result, '0') < 0) {
131        if ($result[0] == '-') {
132            $temp = '1' . str_repeat('0', $m_length + 1);
133            $result = bcadd($result, $temp);
134        }
135
136        while (bccomp($result, $m) >= 0) {
137            $result = bcsub($result, $m);
138        }
139
140        return $result;
141    }
142
143    /**
144     * (Regular) Barrett Modular Reduction
145     *
146     * For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
147     * is that this function does not fold the denominator into a smaller form.
148     *
149     * @param string $x
150     * @param string $n
151     * @return string
152     */
153    private static function regularBarrett($x, $n)
154    {
155        static $cache = [
156            self::VARIABLE => [],
157            self::DATA => []
158        ];
159
160        $n_length = strlen($n);
161
162        if (strlen($x) > 2 * $n_length) {
163            return bcmod($x, $n);
164        }
165
166        if (($key = array_search($n, $cache[self::VARIABLE])) === false) {
167            $key = count($cache[self::VARIABLE]);
168            $cache[self::VARIABLE][] = $n;
169            $lhs = '1' . str_repeat('0', 2 * $n_length);
170            $cache[self::DATA][] = bcdiv($lhs, $n, 0);
171        }
172
173        $temp = substr($x, 0, -$n_length + 1);
174        $temp = bcmul($temp, $cache[self::DATA][$key]);
175        $temp = substr($temp, 0, -$n_length - 1);
176
177        $r1 = substr($x, -$n_length - 1);
178        $r2 = substr(bcmul($temp, $n), -$n_length - 1);
179        $result = bcsub($r1, $r2);
180
181        //if (bccomp($result, '0') < 0) {
182        if ($result[0] == '-') {
183            $q = '1' . str_repeat('0', $n_length + 1);
184            $result = bcadd($result, $q);
185        }
186
187        while (bccomp($result, $n) >= 0) {
188            $result = bcsub($result, $n);
189        }
190
191        return $result;
192    }
193}
194