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