1<?php
2
3/**
4 * PHP 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\PHP\Reductions;
17
18use phpseclib3\Math\BigInteger\Engines\PHP;
19use phpseclib3\Math\BigInteger\Engines\PHP\Base;
20
21/**
22 * PHP Barrett Modular Exponentiation Engine
23 *
24 * @package PHP
25 * @author  Jim Wigginton <terrafrost@php.net>
26 * @access  public
27 */
28abstract class Barrett extends Base
29{
30    /**
31     * Barrett Modular Reduction
32     *
33     * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
34     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information.  Modified slightly,
35     * so as not to require negative numbers (initially, this script didn't support negative numbers).
36     *
37     * Employs "folding", as described at
38     * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}.  To quote from
39     * 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."
40     *
41     * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that
42     * usable on account of (1) its not using reasonable radix points as discussed in
43     * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable
44     * radix points, it only works when there are an even number of digits in the denominator.  The reason for (2) is that
45     * (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
46     * comments for details.
47     *
48     * @param array $n
49     * @param array $m
50     * @param class-string<PHP> $class
51     * @return array
52     */
53    protected static function reduce(array $n, array $m, $class)
54    {
55        static $cache = [
56            self::VARIABLE => [],
57            self::DATA => []
58        ];
59
60        $m_length = count($m);
61
62        // if (self::compareHelper($n, $static::square($m)) >= 0) {
63        if (count($n) > 2 * $m_length) {
64            $lhs = new $class();
65            $rhs = new $class();
66            $lhs->value = $n;
67            $rhs->value = $m;
68            list(, $temp) = $lhs->divide($rhs);
69            return $temp->value;
70        }
71
72        // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced
73        if ($m_length < 5) {
74            return self::regularBarrett($n, $m, $class);
75        }
76        // n = 2 * m.length
77
78        if (($key = array_search($m, $cache[self::VARIABLE])) === false) {
79            $key = count($cache[self::VARIABLE]);
80            $cache[self::VARIABLE][] = $m;
81
82            $lhs = new $class();
83            $lhs_value = &$lhs->value;
84            $lhs_value = self::array_repeat(0, $m_length + ($m_length >> 1));
85            $lhs_value[] = 1;
86            $rhs = new $class();
87            $rhs->value = $m;
88
89            list($u, $m1) = $lhs->divide($rhs);
90            $u = $u->value;
91            $m1 = $m1->value;
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        $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1)
103        $msd = array_slice($n, $cutoff);    // m.length >> 1
104
105        $lsd = self::trim($lsd);
106        $temp = $class::multiplyHelper($msd, false, $m1, false); // m.length + (m.length >> 1)
107        $n = $class::addHelper($lsd, false, $temp[self::VALUE], false); // 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[self::VALUE], $m, $class);
110        //}
111
112        // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2
113        $temp = array_slice($n[self::VALUE], $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 = $class::multiplyHelper($temp, false, $u, false);
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 = array_slice($temp[self::VALUE], ($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 = $class::multiplyHelper($temp, false, $m, false);
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 = $class::subtractHelper($n[self::VALUE], false, $temp[self::VALUE], false);
129
130        while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $m, false) >= 0) {
131            $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $m, false);
132        }
133
134        return $result[self::VALUE];
135    }
136
137    /**
138     * (Regular) Barrett Modular Reduction
139     *
140     * For numbers with more than four digits BigInteger::_barrett() is faster.  The difference between that and this
141     * is that this function does not fold the denominator into a smaller form.
142     *
143     * @param array $x
144     * @param array $n
145     * @param string $class
146     * @return array
147     */
148    private static function regularBarrett(array $x, array $n, $class)
149    {
150        static $cache = [
151            self::VARIABLE => [],
152            self::DATA => []
153        ];
154
155        $n_length = count($n);
156
157        if (count($x) > 2 * $n_length) {
158            $lhs = new $class();
159            $rhs = new $class();
160            $lhs->value = $x;
161            $rhs->value = $n;
162            list(, $temp) = $lhs->divide($rhs);
163            return $temp->value;
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 = new $class();
170            $lhs_value = &$lhs->value;
171            $lhs_value = self::array_repeat(0, 2 * $n_length);
172            $lhs_value[] = 1;
173            $rhs = new $class();
174            $rhs->value = $n;
175            list($temp, ) = $lhs->divide($rhs); // m.length
176            $cache[self::DATA][] = $temp->value;
177        }
178
179        // 2 * m.length - (m.length - 1) = m.length + 1
180        $temp = array_slice($x, $n_length - 1);
181        // (m.length + 1) + m.length = 2 * m.length + 1
182        $temp = $class::multiplyHelper($temp, false, $cache[self::DATA][$key], false);
183        // (2 * m.length + 1) - (m.length - 1) = m.length + 2
184        $temp = array_slice($temp[self::VALUE], $n_length + 1);
185
186        // m.length + 1
187        $result = array_slice($x, 0, $n_length + 1);
188        // m.length + 1
189        $temp = self::multiplyLower($temp, false, $n, false, $n_length + 1, $class);
190        // $temp == array_slice($class::regularMultiply($temp, false, $n, false)->value, 0, $n_length + 1)
191
192        if (self::compareHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]) < 0) {
193            $corrector_value = self::array_repeat(0, $n_length + 1);
194            $corrector_value[count($corrector_value)] = 1;
195            $result = $class::addHelper($result, false, $corrector_value, false);
196            $result = $result[self::VALUE];
197        }
198
199        // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits
200        $result = $class::subtractHelper($result, false, $temp[self::VALUE], $temp[self::SIGN]);
201        while (self::compareHelper($result[self::VALUE], $result[self::SIGN], $n, false) > 0) {
202            $result = $class::subtractHelper($result[self::VALUE], $result[self::SIGN], $n, false);
203        }
204
205        return $result[self::VALUE];
206    }
207
208    /**
209     * Performs long multiplication up to $stop digits
210     *
211     * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
212     *
213     * @see self::regularBarrett()
214     * @param array $x_value
215     * @param bool $x_negative
216     * @param array $y_value
217     * @param bool $y_negative
218     * @param int $stop
219     * @param string $class
220     * @return array
221     */
222    private static function multiplyLower(array $x_value, $x_negative, array $y_value, $y_negative, $stop, $class)
223    {
224        $x_length = count($x_value);
225        $y_length = count($y_value);
226
227        if (!$x_length || !$y_length) { // a 0 is being multiplied
228            return [
229                self::VALUE => [],
230                self::SIGN => false
231            ];
232        }
233
234        if ($x_length < $y_length) {
235            $temp = $x_value;
236            $x_value = $y_value;
237            $y_value = $temp;
238
239            $x_length = count($x_value);
240            $y_length = count($y_value);
241        }
242
243        $product_value = self::array_repeat(0, $x_length + $y_length);
244
245        // the following for loop could be removed if the for loop following it
246        // (the one with nested for loops) initially set $i to 0, but
247        // doing so would also make the result in one set of unnecessary adds,
248        // since on the outermost loops first pass, $product->value[$k] is going
249        // to always be 0
250
251        $carry = 0;
252
253        for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i
254            $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0
255            $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
256            $product_value[$j] = (int) ($temp - $class::BASE_FULL * $carry);
257        }
258
259        if ($j < $stop) {
260            $product_value[$j] = $carry;
261        }
262
263        // the above for loop is what the previous comment was talking about.  the
264        // following for loop is the "one with nested for loops"
265
266        for ($i = 1; $i < $y_length; ++$i) {
267            $carry = 0;
268
269            for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) {
270                $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry;
271                $carry = $class::BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31);
272                $product_value[$k] = (int) ($temp - $class::BASE_FULL * $carry);
273            }
274
275            if ($k < $stop) {
276                $product_value[$k] = $carry;
277            }
278        }
279
280        return [
281            self::VALUE => self::trim($product_value),
282            self::SIGN => $x_negative != $y_negative
283        ];
284    }
285}
286