Rev 846 | Go to most recent revision | Details | Compare with Previous | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
827 | daniel-mar | 1 | <?php |
2 | |||
3 | /** |
||
4 | * PHP Barrett Modular Exponentiation Engine |
||
5 | * |
||
6 | * PHP version 5 and 7 |
||
7 | * |
||
874 | daniel-mar | 8 | * @category Math |
9 | * @package BigInteger |
||
827 | daniel-mar | 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 | |||
16 | namespace phpseclib3\Math\BigInteger\Engines\PHP\Reductions; |
||
17 | |||
18 | use phpseclib3\Math\BigInteger\Engines\PHP; |
||
19 | use phpseclib3\Math\BigInteger\Engines\PHP\Base; |
||
20 | |||
21 | /** |
||
22 | * PHP Barrett Modular Exponentiation Engine |
||
23 | * |
||
874 | daniel-mar | 24 | * @package PHP |
827 | daniel-mar | 25 | * @author Jim Wigginton <terrafrost@php.net> |
874 | daniel-mar | 26 | * @access public |
827 | daniel-mar | 27 | */ |
28 | abstract 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 | } |