Commit | Line | Data |
---|---|---|
7f254ad8 AE |
1 | <?php |
2 | ||
3 | /** | |
4 | * Pure-PHP arbitrary precision integer arithmetic library. | |
5 | * | |
6 | * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available, | |
7 | * and an internal implementation, otherwise. | |
8 | * | |
9 | * PHP versions 4 and 5 | |
10 | * | |
11 | * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the | |
12 | * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode) | |
13 | * | |
14 | * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and | |
15 | * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible | |
16 | * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating | |
17 | * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are | |
18 | * used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %, | |
19 | * which only supports integers. Although this fact will slow this library down, the fact that such a high | |
20 | * base is being used should more than compensate. | |
21 | * | |
22 | * Numbers are stored in {@link http://en.wikipedia.org/wiki/Endianness little endian} format. ie. | |
23 | * (new Math_BigInteger(pow(2, 26)))->value = array(0, 1) | |
24 | * | |
25 | * Useful resources are as follows: | |
26 | * | |
27 | * - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)} | |
28 | * - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)} | |
29 | * - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip | |
30 | * | |
31 | * Here's an example of how to use this library: | |
32 | * <code> | |
33 | * <?php | |
34 | * include 'Math/BigInteger.php'; | |
35 | * | |
36 | * $a = new Math_BigInteger(2); | |
37 | * $b = new Math_BigInteger(3); | |
38 | * | |
39 | * $c = $a->add($b); | |
40 | * | |
41 | * echo $c->toString(); // outputs 5 | |
42 | * ?> | |
43 | * </code> | |
44 | * | |
45 | * LICENSE: Permission is hereby granted, free of charge, to any person obtaining a copy | |
46 | * of this software and associated documentation files (the "Software"), to deal | |
47 | * in the Software without restriction, including without limitation the rights | |
48 | * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
49 | * copies of the Software, and to permit persons to whom the Software is | |
50 | * furnished to do so, subject to the following conditions: | |
51 | * | |
52 | * The above copyright notice and this permission notice shall be included in | |
53 | * all copies or substantial portions of the Software. | |
54 | * | |
55 | * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
56 | * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
57 | * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
58 | * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
59 | * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
60 | * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN | |
61 | * THE SOFTWARE. | |
62 | * | |
63 | * @category Math | |
64 | * @package Math_BigInteger | |
65 | * @author Jim Wigginton <terrafrost@php.net> | |
66 | * @copyright 2006 Jim Wigginton | |
67 | * @license http://www.opensource.org/licenses/mit-license.html MIT License | |
68 | * @link http://pear.php.net/package/Math_BigInteger | |
69 | */ | |
70 | ||
71 | /**#@+ | |
72 | * Reduction constants | |
73 | * | |
74 | * @access private | |
75 | * @see Math_BigInteger::_reduce() | |
76 | */ | |
77 | /** | |
78 | * @see Math_BigInteger::_montgomery() | |
79 | * @see Math_BigInteger::_prepMontgomery() | |
80 | */ | |
81 | define('MATH_BIGINTEGER_MONTGOMERY', 0); | |
82 | /** | |
83 | * @see Math_BigInteger::_barrett() | |
84 | */ | |
85 | define('MATH_BIGINTEGER_BARRETT', 1); | |
86 | /** | |
87 | * @see Math_BigInteger::_mod2() | |
88 | */ | |
89 | define('MATH_BIGINTEGER_POWEROF2', 2); | |
90 | /** | |
91 | * @see Math_BigInteger::_remainder() | |
92 | */ | |
93 | define('MATH_BIGINTEGER_CLASSIC', 3); | |
94 | /** | |
95 | * @see Math_BigInteger::__clone() | |
96 | */ | |
97 | define('MATH_BIGINTEGER_NONE', 4); | |
98 | /**#@-*/ | |
99 | ||
100 | /**#@+ | |
101 | * Array constants | |
102 | * | |
103 | * Rather than create a thousands and thousands of new Math_BigInteger objects in repeated function calls to add() and | |
104 | * multiply() or whatever, we'll just work directly on arrays, taking them in as parameters and returning them. | |
105 | * | |
106 | * @access private | |
107 | */ | |
108 | /** | |
109 | * $result[MATH_BIGINTEGER_VALUE] contains the value. | |
110 | */ | |
111 | define('MATH_BIGINTEGER_VALUE', 0); | |
112 | /** | |
113 | * $result[MATH_BIGINTEGER_SIGN] contains the sign. | |
114 | */ | |
115 | define('MATH_BIGINTEGER_SIGN', 1); | |
116 | /**#@-*/ | |
117 | ||
118 | /**#@+ | |
119 | * @access private | |
120 | * @see Math_BigInteger::_montgomery() | |
121 | * @see Math_BigInteger::_barrett() | |
122 | */ | |
123 | /** | |
124 | * Cache constants | |
125 | * | |
126 | * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid. | |
127 | */ | |
128 | define('MATH_BIGINTEGER_VARIABLE', 0); | |
129 | /** | |
130 | * $cache[MATH_BIGINTEGER_DATA] contains the cached data. | |
131 | */ | |
132 | define('MATH_BIGINTEGER_DATA', 1); | |
133 | /**#@-*/ | |
134 | ||
135 | /**#@+ | |
136 | * Mode constants. | |
137 | * | |
138 | * @access private | |
139 | * @see Math_BigInteger::Math_BigInteger() | |
140 | */ | |
141 | /** | |
142 | * To use the pure-PHP implementation | |
143 | */ | |
144 | define('MATH_BIGINTEGER_MODE_INTERNAL', 1); | |
145 | /** | |
146 | * To use the BCMath library | |
147 | * | |
148 | * (if enabled; otherwise, the internal implementation will be used) | |
149 | */ | |
150 | define('MATH_BIGINTEGER_MODE_BCMATH', 2); | |
151 | /** | |
152 | * To use the GMP library | |
153 | * | |
154 | * (if present; otherwise, either the BCMath or the internal implementation will be used) | |
155 | */ | |
156 | define('MATH_BIGINTEGER_MODE_GMP', 3); | |
157 | /**#@-*/ | |
158 | ||
159 | /** | |
160 | * Karatsuba Cutoff | |
161 | * | |
162 | * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication? | |
163 | * | |
164 | * @access private | |
165 | */ | |
166 | define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 25); | |
167 | ||
168 | /** | |
169 | * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256 | |
170 | * numbers. | |
171 | * | |
172 | * @package Math_BigInteger | |
173 | * @author Jim Wigginton <terrafrost@php.net> | |
174 | * @access public | |
175 | */ | |
176 | class Math_BigInteger | |
177 | { | |
178 | /** | |
179 | * Holds the BigInteger's value. | |
180 | * | |
181 | * @var Array | |
182 | * @access private | |
183 | */ | |
184 | var $value; | |
185 | ||
186 | /** | |
187 | * Holds the BigInteger's magnitude. | |
188 | * | |
189 | * @var Boolean | |
190 | * @access private | |
191 | */ | |
192 | var $is_negative = false; | |
193 | ||
194 | /** | |
195 | * Random number generator function | |
196 | * | |
197 | * @see setRandomGenerator() | |
198 | * @access private | |
199 | */ | |
200 | var $generator = 'mt_rand'; | |
201 | ||
202 | /** | |
203 | * Precision | |
204 | * | |
205 | * @see setPrecision() | |
206 | * @access private | |
207 | */ | |
208 | var $precision = -1; | |
209 | ||
210 | /** | |
211 | * Precision Bitmask | |
212 | * | |
213 | * @see setPrecision() | |
214 | * @access private | |
215 | */ | |
216 | var $bitmask = false; | |
217 | ||
218 | /** | |
219 | * Mode independent value used for serialization. | |
220 | * | |
221 | * If the bcmath or gmp extensions are installed $this->value will be a non-serializable resource, hence the need for | |
222 | * a variable that'll be serializable regardless of whether or not extensions are being used. Unlike $this->value, | |
223 | * however, $this->hex is only calculated when $this->__sleep() is called. | |
224 | * | |
225 | * @see __sleep() | |
226 | * @see __wakeup() | |
227 | * @var String | |
228 | * @access private | |
229 | */ | |
230 | var $hex; | |
231 | ||
232 | /** | |
233 | * Converts base-2, base-10, base-16, and binary strings (base-256) to BigIntegers. | |
234 | * | |
235 | * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using | |
236 | * two's compliment. The sole exception to this is -10, which is treated the same as 10 is. | |
237 | * | |
238 | * Here's an example: | |
239 | * <code> | |
240 | * <?php | |
241 | * include 'Math/BigInteger.php'; | |
242 | * | |
243 | * $a = new Math_BigInteger('0x32', 16); // 50 in base-16 | |
244 | * | |
245 | * echo $a->toString(); // outputs 50 | |
246 | * ?> | |
247 | * </code> | |
248 | * | |
249 | * @param optional $x base-10 number or base-$base number if $base set. | |
250 | * @param optional integer $base | |
251 | * @return Math_BigInteger | |
252 | * @access public | |
253 | */ | |
254 | function Math_BigInteger($x = 0, $base = 10) | |
255 | { | |
256 | if ( !defined('MATH_BIGINTEGER_MODE') ) { | |
257 | switch (true) { | |
258 | case extension_loaded('gmp'): | |
259 | define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP); | |
260 | break; | |
261 | case extension_loaded('bcmath'): | |
262 | define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH); | |
263 | break; | |
264 | default: | |
265 | define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL); | |
266 | } | |
267 | } | |
268 | ||
269 | if (function_exists('openssl_public_encrypt') && !defined('MATH_BIGINTEGER_OPENSSL_DISABLE') && !defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { | |
270 | // some versions of XAMPP have mismatched versions of OpenSSL which causes it not to work | |
271 | ob_start(); | |
272 | @phpinfo(); | |
273 | $content = ob_get_contents(); | |
274 | ob_end_clean(); | |
275 | ||
276 | preg_match_all('#OpenSSL (Header|Library) Version(.*)#im', $content, $matches); | |
277 | ||
278 | $versions = array(); | |
279 | if (!empty($matches[1])) { | |
280 | for ($i = 0; $i < count($matches[1]); $i++) { | |
281 | $fullVersion = trim(str_replace('=>', '', strip_tags($matches[2][$i]))); | |
282 | ||
283 | // Remove letter part in OpenSSL version | |
284 | if (!preg_match('/(\d+\.\d+\.\d+)/i', $fullVersion, $m)) { | |
285 | $versions[$matches[1][$i]] = $fullVersion; | |
286 | } else { | |
287 | $versions[$matches[1][$i]] = $m[0]; | |
288 | } | |
289 | } | |
290 | } | |
291 | ||
292 | // it doesn't appear that OpenSSL versions were reported upon until PHP 5.3+ | |
293 | switch (true) { | |
294 | case !isset($versions['Header']): | |
295 | case !isset($versions['Library']): | |
296 | case $versions['Header'] == $versions['Library']: | |
297 | define('MATH_BIGINTEGER_OPENSSL_ENABLED', true); | |
298 | break; | |
299 | default: | |
300 | define('MATH_BIGINTEGER_OPENSSL_DISABLE', true); | |
301 | } | |
302 | } | |
303 | ||
304 | if (!defined('PHP_INT_SIZE')) { | |
305 | define('PHP_INT_SIZE', 4); | |
306 | } | |
307 | ||
308 | if (!defined('MATH_BIGINTEGER_BASE') && MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_INTERNAL) { | |
309 | switch (PHP_INT_SIZE) { | |
310 | case 8: // use 64-bit integers if int size is 8 bytes | |
311 | define('MATH_BIGINTEGER_BASE', 31); | |
312 | define('MATH_BIGINTEGER_BASE_FULL', 0x80000000); | |
313 | define('MATH_BIGINTEGER_MAX_DIGIT', 0x7FFFFFFF); | |
314 | define('MATH_BIGINTEGER_MSB', 0x40000000); | |
315 | // 10**9 is the closest we can get to 2**31 without passing it | |
316 | define('MATH_BIGINTEGER_MAX10', 1000000000); | |
317 | define('MATH_BIGINTEGER_MAX10_LEN', 9); | |
318 | // the largest digit that may be used in addition / subtraction | |
319 | define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 62)); | |
320 | break; | |
321 | //case 4: // use 64-bit floats if int size is 4 bytes | |
322 | default: | |
323 | define('MATH_BIGINTEGER_BASE', 26); | |
324 | define('MATH_BIGINTEGER_BASE_FULL', 0x4000000); | |
325 | define('MATH_BIGINTEGER_MAX_DIGIT', 0x3FFFFFF); | |
326 | define('MATH_BIGINTEGER_MSB', 0x2000000); | |
327 | // 10**7 is the closest to 2**26 without passing it | |
328 | define('MATH_BIGINTEGER_MAX10', 10000000); | |
329 | define('MATH_BIGINTEGER_MAX10_LEN', 7); | |
330 | // the largest digit that may be used in addition / subtraction | |
331 | // we do pow(2, 52) instead of using 4503599627370496 directly because some | |
332 | // PHP installations will truncate 4503599627370496. | |
333 | define('MATH_BIGINTEGER_MAX_DIGIT2', pow(2, 52)); | |
334 | } | |
335 | } | |
336 | ||
337 | switch ( MATH_BIGINTEGER_MODE ) { | |
338 | case MATH_BIGINTEGER_MODE_GMP: | |
339 | switch (true) { | |
340 | case is_resource($x) && get_resource_type($x) == 'GMP integer': | |
341 | // PHP 5.6 switched GMP from using resources to objects | |
342 | case is_object($x) && get_class($x) == 'GMP': | |
343 | $this->value = $x; | |
344 | return; | |
345 | } | |
346 | $this->value = gmp_init(0); | |
347 | break; | |
348 | case MATH_BIGINTEGER_MODE_BCMATH: | |
349 | $this->value = '0'; | |
350 | break; | |
351 | default: | |
352 | $this->value = array(); | |
353 | } | |
354 | ||
355 | // '0' counts as empty() but when the base is 256 '0' is equal to ord('0') or 48 | |
356 | // '0' is the only value like this per http://php.net/empty | |
357 | if (empty($x) && (abs($base) != 256 || $x !== '0')) { | |
358 | return; | |
359 | } | |
360 | ||
361 | switch ($base) { | |
362 | case -256: | |
363 | if (ord($x[0]) & 0x80) { | |
364 | $x = ~$x; | |
365 | $this->is_negative = true; | |
366 | } | |
367 | case 256: | |
368 | switch ( MATH_BIGINTEGER_MODE ) { | |
369 | case MATH_BIGINTEGER_MODE_GMP: | |
370 | $sign = $this->is_negative ? '-' : ''; | |
371 | $this->value = gmp_init($sign . '0x' . bin2hex($x)); | |
372 | break; | |
373 | case MATH_BIGINTEGER_MODE_BCMATH: | |
374 | // round $len to the nearest 4 (thanks, DavidMJ!) | |
375 | $len = (strlen($x) + 3) & 0xFFFFFFFC; | |
376 | ||
377 | $x = str_pad($x, $len, chr(0), STR_PAD_LEFT); | |
378 | ||
379 | for ($i = 0; $i < $len; $i+= 4) { | |
380 | $this->value = bcmul($this->value, '4294967296', 0); // 4294967296 == 2**32 | |
381 | $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])), 0); | |
382 | } | |
383 | ||
384 | if ($this->is_negative) { | |
385 | $this->value = '-' . $this->value; | |
386 | } | |
387 | ||
388 | break; | |
389 | // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb) | |
390 | default: | |
391 | while (strlen($x)) { | |
392 | $this->value[] = $this->_bytes2int($this->_base256_rshift($x, MATH_BIGINTEGER_BASE)); | |
393 | } | |
394 | } | |
395 | ||
396 | if ($this->is_negative) { | |
397 | if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) { | |
398 | $this->is_negative = false; | |
399 | } | |
400 | $temp = $this->add(new Math_BigInteger('-1')); | |
401 | $this->value = $temp->value; | |
402 | } | |
403 | break; | |
404 | case 16: | |
405 | case -16: | |
406 | if ($base > 0 && $x[0] == '-') { | |
407 | $this->is_negative = true; | |
408 | $x = substr($x, 1); | |
409 | } | |
410 | ||
411 | $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x); | |
412 | ||
413 | $is_negative = false; | |
414 | if ($base < 0 && hexdec($x[0]) >= 8) { | |
415 | $this->is_negative = $is_negative = true; | |
416 | $x = bin2hex(~pack('H*', $x)); | |
417 | } | |
418 | ||
419 | switch ( MATH_BIGINTEGER_MODE ) { | |
420 | case MATH_BIGINTEGER_MODE_GMP: | |
421 | $temp = $this->is_negative ? '-0x' . $x : '0x' . $x; | |
422 | $this->value = gmp_init($temp); | |
423 | $this->is_negative = false; | |
424 | break; | |
425 | case MATH_BIGINTEGER_MODE_BCMATH: | |
426 | $x = ( strlen($x) & 1 ) ? '0' . $x : $x; | |
427 | $temp = new Math_BigInteger(pack('H*', $x), 256); | |
428 | $this->value = $this->is_negative ? '-' . $temp->value : $temp->value; | |
429 | $this->is_negative = false; | |
430 | break; | |
431 | default: | |
432 | $x = ( strlen($x) & 1 ) ? '0' . $x : $x; | |
433 | $temp = new Math_BigInteger(pack('H*', $x), 256); | |
434 | $this->value = $temp->value; | |
435 | } | |
436 | ||
437 | if ($is_negative) { | |
438 | $temp = $this->add(new Math_BigInteger('-1')); | |
439 | $this->value = $temp->value; | |
440 | } | |
441 | break; | |
442 | case 10: | |
443 | case -10: | |
444 | // (?<!^)(?:-).*: find any -'s that aren't at the beginning and then any characters that follow that | |
445 | // (?<=^|-)0*: find any 0's that are preceded by the start of the string or by a - (ie. octals) | |
446 | // [^-0-9].*: find any non-numeric characters and then any characters that follow that | |
447 | $x = preg_replace('#(?<!^)(?:-).*|(?<=^|-)0*|[^-0-9].*#', '', $x); | |
448 | ||
449 | switch ( MATH_BIGINTEGER_MODE ) { | |
450 | case MATH_BIGINTEGER_MODE_GMP: | |
451 | $this->value = gmp_init($x); | |
452 | break; | |
453 | case MATH_BIGINTEGER_MODE_BCMATH: | |
454 | // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different | |
455 | // results then doing it on '-1' does (modInverse does $x[0]) | |
456 | $this->value = $x === '-' ? '0' : (string) $x; | |
457 | break; | |
458 | default: | |
459 | $temp = new Math_BigInteger(); | |
460 | ||
461 | $multiplier = new Math_BigInteger(); | |
462 | $multiplier->value = array(MATH_BIGINTEGER_MAX10); | |
463 | ||
464 | if ($x[0] == '-') { | |
465 | $this->is_negative = true; | |
466 | $x = substr($x, 1); | |
467 | } | |
468 | ||
469 | $x = str_pad($x, strlen($x) + ((MATH_BIGINTEGER_MAX10_LEN - 1) * strlen($x)) % MATH_BIGINTEGER_MAX10_LEN, 0, STR_PAD_LEFT); | |
470 | while (strlen($x)) { | |
471 | $temp = $temp->multiply($multiplier); | |
472 | $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, MATH_BIGINTEGER_MAX10_LEN)), 256)); | |
473 | $x = substr($x, MATH_BIGINTEGER_MAX10_LEN); | |
474 | } | |
475 | ||
476 | $this->value = $temp->value; | |
477 | } | |
478 | break; | |
479 | case 2: // base-2 support originally implemented by Lluis Pamies - thanks! | |
480 | case -2: | |
481 | if ($base > 0 && $x[0] == '-') { | |
482 | $this->is_negative = true; | |
483 | $x = substr($x, 1); | |
484 | } | |
485 | ||
486 | $x = preg_replace('#^([01]*).*#', '$1', $x); | |
487 | $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT); | |
488 | ||
489 | $str = '0x'; | |
490 | while (strlen($x)) { | |
491 | $part = substr($x, 0, 4); | |
492 | $str.= dechex(bindec($part)); | |
493 | $x = substr($x, 4); | |
494 | } | |
495 | ||
496 | if ($this->is_negative) { | |
497 | $str = '-' . $str; | |
498 | } | |
499 | ||
500 | $temp = new Math_BigInteger($str, 8 * $base); // ie. either -16 or +16 | |
501 | $this->value = $temp->value; | |
502 | $this->is_negative = $temp->is_negative; | |
503 | ||
504 | break; | |
505 | default: | |
506 | // base not supported, so we'll let $this == 0 | |
507 | } | |
508 | } | |
509 | ||
510 | /** | |
511 | * Converts a BigInteger to a byte string (eg. base-256). | |
512 | * | |
513 | * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're | |
514 | * saved as two's compliment. | |
515 | * | |
516 | * Here's an example: | |
517 | * <code> | |
518 | * <?php | |
519 | * include 'Math/BigInteger.php'; | |
520 | * | |
521 | * $a = new Math_BigInteger('65'); | |
522 | * | |
523 | * echo $a->toBytes(); // outputs chr(65) | |
524 | * ?> | |
525 | * </code> | |
526 | * | |
527 | * @param Boolean $twos_compliment | |
528 | * @return String | |
529 | * @access public | |
530 | * @internal Converts a base-2**26 number to base-2**8 | |
531 | */ | |
532 | function toBytes($twos_compliment = false) | |
533 | { | |
534 | if ($twos_compliment) { | |
535 | $comparison = $this->compare(new Math_BigInteger()); | |
536 | if ($comparison == 0) { | |
537 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; | |
538 | } | |
539 | ||
540 | $temp = $comparison < 0 ? $this->add(new Math_BigInteger(1)) : $this->copy(); | |
541 | $bytes = $temp->toBytes(); | |
542 | ||
543 | if (empty($bytes)) { // eg. if the number we're trying to convert is -1 | |
544 | $bytes = chr(0); | |
545 | } | |
546 | ||
547 | if (ord($bytes[0]) & 0x80) { | |
548 | $bytes = chr(0) . $bytes; | |
549 | } | |
550 | ||
551 | return $comparison < 0 ? ~$bytes : $bytes; | |
552 | } | |
553 | ||
554 | switch ( MATH_BIGINTEGER_MODE ) { | |
555 | case MATH_BIGINTEGER_MODE_GMP: | |
556 | if (gmp_cmp($this->value, gmp_init(0)) == 0) { | |
557 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; | |
558 | } | |
559 | ||
560 | $temp = gmp_strval(gmp_abs($this->value), 16); | |
561 | $temp = ( strlen($temp) & 1 ) ? '0' . $temp : $temp; | |
562 | $temp = pack('H*', $temp); | |
563 | ||
564 | return $this->precision > 0 ? | |
565 | substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : | |
566 | ltrim($temp, chr(0)); | |
567 | case MATH_BIGINTEGER_MODE_BCMATH: | |
568 | if ($this->value === '0') { | |
569 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; | |
570 | } | |
571 | ||
572 | $value = ''; | |
573 | $current = $this->value; | |
574 | ||
575 | if ($current[0] == '-') { | |
576 | $current = substr($current, 1); | |
577 | } | |
578 | ||
579 | while (bccomp($current, '0', 0) > 0) { | |
580 | $temp = bcmod($current, '16777216'); | |
581 | $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value; | |
582 | $current = bcdiv($current, '16777216', 0); | |
583 | } | |
584 | ||
585 | return $this->precision > 0 ? | |
586 | substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) : | |
587 | ltrim($value, chr(0)); | |
588 | } | |
589 | ||
590 | if (!count($this->value)) { | |
591 | return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : ''; | |
592 | } | |
593 | $result = $this->_int2bytes($this->value[count($this->value) - 1]); | |
594 | ||
595 | $temp = $this->copy(); | |
596 | ||
597 | for ($i = count($temp->value) - 2; $i >= 0; --$i) { | |
598 | $temp->_base256_lshift($result, MATH_BIGINTEGER_BASE); | |
599 | $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT); | |
600 | } | |
601 | ||
602 | return $this->precision > 0 ? | |
603 | str_pad(substr($result, -(($this->precision + 7) >> 3)), ($this->precision + 7) >> 3, chr(0), STR_PAD_LEFT) : | |
604 | $result; | |
605 | } | |
606 | ||
607 | /** | |
608 | * Converts a BigInteger to a hex string (eg. base-16)). | |
609 | * | |
610 | * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're | |
611 | * saved as two's compliment. | |
612 | * | |
613 | * Here's an example: | |
614 | * <code> | |
615 | * <?php | |
616 | * include 'Math/BigInteger.php'; | |
617 | * | |
618 | * $a = new Math_BigInteger('65'); | |
619 | * | |
620 | * echo $a->toHex(); // outputs '41' | |
621 | * ?> | |
622 | * </code> | |
623 | * | |
624 | * @param Boolean $twos_compliment | |
625 | * @return String | |
626 | * @access public | |
627 | * @internal Converts a base-2**26 number to base-2**8 | |
628 | */ | |
629 | function toHex($twos_compliment = false) | |
630 | { | |
631 | return bin2hex($this->toBytes($twos_compliment)); | |
632 | } | |
633 | ||
634 | /** | |
635 | * Converts a BigInteger to a bit string (eg. base-2). | |
636 | * | |
637 | * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're | |
638 | * saved as two's compliment. | |
639 | * | |
640 | * Here's an example: | |
641 | * <code> | |
642 | * <?php | |
643 | * include 'Math/BigInteger.php'; | |
644 | * | |
645 | * $a = new Math_BigInteger('65'); | |
646 | * | |
647 | * echo $a->toBits(); // outputs '1000001' | |
648 | * ?> | |
649 | * </code> | |
650 | * | |
651 | * @param Boolean $twos_compliment | |
652 | * @return String | |
653 | * @access public | |
654 | * @internal Converts a base-2**26 number to base-2**2 | |
655 | */ | |
656 | function toBits($twos_compliment = false) | |
657 | { | |
658 | $hex = $this->toHex($twos_compliment); | |
659 | $bits = ''; | |
660 | for ($i = strlen($hex) - 8, $start = strlen($hex) & 7; $i >= $start; $i-=8) { | |
661 | $bits = str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT) . $bits; | |
662 | } | |
663 | if ($start) { // hexdec('') == 0 | |
664 | $bits = str_pad(decbin(hexdec(substr($hex, 0, $start))), 8, '0', STR_PAD_LEFT) . $bits; | |
665 | } | |
666 | $result = $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0'); | |
667 | ||
668 | if ($twos_compliment && $this->compare(new Math_BigInteger()) > 0 && $this->precision <= 0) { | |
669 | return '0' . $result; | |
670 | } | |
671 | ||
672 | return $result; | |
673 | } | |
674 | ||
675 | /** | |
676 | * Converts a BigInteger to a base-10 number. | |
677 | * | |
678 | * Here's an example: | |
679 | * <code> | |
680 | * <?php | |
681 | * include 'Math/BigInteger.php'; | |
682 | * | |
683 | * $a = new Math_BigInteger('50'); | |
684 | * | |
685 | * echo $a->toString(); // outputs 50 | |
686 | * ?> | |
687 | * </code> | |
688 | * | |
689 | * @return String | |
690 | * @access public | |
691 | * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10) | |
692 | */ | |
693 | function toString() | |
694 | { | |
695 | switch ( MATH_BIGINTEGER_MODE ) { | |
696 | case MATH_BIGINTEGER_MODE_GMP: | |
697 | return gmp_strval($this->value); | |
698 | case MATH_BIGINTEGER_MODE_BCMATH: | |
699 | if ($this->value === '0') { | |
700 | return '0'; | |
701 | } | |
702 | ||
703 | return ltrim($this->value, '0'); | |
704 | } | |
705 | ||
706 | if (!count($this->value)) { | |
707 | return '0'; | |
708 | } | |
709 | ||
710 | $temp = $this->copy(); | |
711 | $temp->is_negative = false; | |
712 | ||
713 | $divisor = new Math_BigInteger(); | |
714 | $divisor->value = array(MATH_BIGINTEGER_MAX10); | |
715 | $result = ''; | |
716 | while (count($temp->value)) { | |
717 | list($temp, $mod) = $temp->divide($divisor); | |
718 | $result = str_pad(isset($mod->value[0]) ? $mod->value[0] : '', MATH_BIGINTEGER_MAX10_LEN, '0', STR_PAD_LEFT) . $result; | |
719 | } | |
720 | $result = ltrim($result, '0'); | |
721 | if (empty($result)) { | |
722 | $result = '0'; | |
723 | } | |
724 | ||
725 | if ($this->is_negative) { | |
726 | $result = '-' . $result; | |
727 | } | |
728 | ||
729 | return $result; | |
730 | } | |
731 | ||
732 | /** | |
733 | * Copy an object | |
734 | * | |
735 | * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee | |
736 | * that all objects are passed by value, when appropriate. More information can be found here: | |
737 | * | |
738 | * {@link http://php.net/language.oop5.basic#51624} | |
739 | * | |
740 | * @access public | |
741 | * @see __clone() | |
742 | * @return Math_BigInteger | |
743 | */ | |
744 | function copy() | |
745 | { | |
746 | $temp = new Math_BigInteger(); | |
747 | $temp->value = $this->value; | |
748 | $temp->is_negative = $this->is_negative; | |
749 | $temp->generator = $this->generator; | |
750 | $temp->precision = $this->precision; | |
751 | $temp->bitmask = $this->bitmask; | |
752 | return $temp; | |
753 | } | |
754 | ||
755 | /** | |
756 | * __toString() magic method | |
757 | * | |
758 | * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call | |
759 | * toString(). | |
760 | * | |
761 | * @access public | |
762 | * @internal Implemented per a suggestion by Techie-Michael - thanks! | |
763 | */ | |
764 | function __toString() | |
765 | { | |
766 | return $this->toString(); | |
767 | } | |
768 | ||
769 | /** | |
770 | * __clone() magic method | |
771 | * | |
772 | * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone() | |
773 | * directly in PHP5. You can in PHP4 since it's not a magic method, but in PHP5, you have to call it by using the PHP5 | |
774 | * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5, | |
775 | * call Math_BigInteger::copy(), instead. | |
776 | * | |
777 | * @access public | |
778 | * @see copy() | |
779 | * @return Math_BigInteger | |
780 | */ | |
781 | function __clone() | |
782 | { | |
783 | return $this->copy(); | |
784 | } | |
785 | ||
786 | /** | |
787 | * __sleep() magic method | |
788 | * | |
789 | * Will be called, automatically, when serialize() is called on a Math_BigInteger object. | |
790 | * | |
791 | * @see __wakeup() | |
792 | * @access public | |
793 | */ | |
794 | function __sleep() | |
795 | { | |
796 | $this->hex = $this->toHex(true); | |
797 | $vars = array('hex'); | |
798 | if ($this->generator != 'mt_rand') { | |
799 | $vars[] = 'generator'; | |
800 | } | |
801 | if ($this->precision > 0) { | |
802 | $vars[] = 'precision'; | |
803 | } | |
804 | return $vars; | |
805 | ||
806 | } | |
807 | ||
808 | /** | |
809 | * __wakeup() magic method | |
810 | * | |
811 | * Will be called, automatically, when unserialize() is called on a Math_BigInteger object. | |
812 | * | |
813 | * @see __sleep() | |
814 | * @access public | |
815 | */ | |
816 | function __wakeup() | |
817 | { | |
818 | $temp = new Math_BigInteger($this->hex, -16); | |
819 | $this->value = $temp->value; | |
820 | $this->is_negative = $temp->is_negative; | |
821 | $this->setRandomGenerator($this->generator); | |
822 | if ($this->precision > 0) { | |
823 | // recalculate $this->bitmask | |
824 | $this->setPrecision($this->precision); | |
825 | } | |
826 | } | |
827 | ||
828 | /** | |
829 | * Adds two BigIntegers. | |
830 | * | |
831 | * Here's an example: | |
832 | * <code> | |
833 | * <?php | |
834 | * include 'Math/BigInteger.php'; | |
835 | * | |
836 | * $a = new Math_BigInteger('10'); | |
837 | * $b = new Math_BigInteger('20'); | |
838 | * | |
839 | * $c = $a->add($b); | |
840 | * | |
841 | * echo $c->toString(); // outputs 30 | |
842 | * ?> | |
843 | * </code> | |
844 | * | |
845 | * @param Math_BigInteger $y | |
846 | * @return Math_BigInteger | |
847 | * @access public | |
848 | * @internal Performs base-2**52 addition | |
849 | */ | |
850 | function add($y) | |
851 | { | |
852 | switch ( MATH_BIGINTEGER_MODE ) { | |
853 | case MATH_BIGINTEGER_MODE_GMP: | |
854 | $temp = new Math_BigInteger(); | |
855 | $temp->value = gmp_add($this->value, $y->value); | |
856 | ||
857 | return $this->_normalize($temp); | |
858 | case MATH_BIGINTEGER_MODE_BCMATH: | |
859 | $temp = new Math_BigInteger(); | |
860 | $temp->value = bcadd($this->value, $y->value, 0); | |
861 | ||
862 | return $this->_normalize($temp); | |
863 | } | |
864 | ||
865 | $temp = $this->_add($this->value, $this->is_negative, $y->value, $y->is_negative); | |
866 | ||
867 | $result = new Math_BigInteger(); | |
868 | $result->value = $temp[MATH_BIGINTEGER_VALUE]; | |
869 | $result->is_negative = $temp[MATH_BIGINTEGER_SIGN]; | |
870 | ||
871 | return $this->_normalize($result); | |
872 | } | |
873 | ||
874 | /** | |
875 | * Performs addition. | |
876 | * | |
877 | * @param Array $x_value | |
878 | * @param Boolean $x_negative | |
879 | * @param Array $y_value | |
880 | * @param Boolean $y_negative | |
881 | * @return Array | |
882 | * @access private | |
883 | */ | |
884 | function _add($x_value, $x_negative, $y_value, $y_negative) | |
885 | { | |
886 | $x_size = count($x_value); | |
887 | $y_size = count($y_value); | |
888 | ||
889 | if ($x_size == 0) { | |
890 | return array( | |
891 | MATH_BIGINTEGER_VALUE => $y_value, | |
892 | MATH_BIGINTEGER_SIGN => $y_negative | |
893 | ); | |
894 | } else if ($y_size == 0) { | |
895 | return array( | |
896 | MATH_BIGINTEGER_VALUE => $x_value, | |
897 | MATH_BIGINTEGER_SIGN => $x_negative | |
898 | ); | |
899 | } | |
900 | ||
901 | // subtract, if appropriate | |
902 | if ( $x_negative != $y_negative ) { | |
903 | if ( $x_value == $y_value ) { | |
904 | return array( | |
905 | MATH_BIGINTEGER_VALUE => array(), | |
906 | MATH_BIGINTEGER_SIGN => false | |
907 | ); | |
908 | } | |
909 | ||
910 | $temp = $this->_subtract($x_value, false, $y_value, false); | |
911 | $temp[MATH_BIGINTEGER_SIGN] = $this->_compare($x_value, false, $y_value, false) > 0 ? | |
912 | $x_negative : $y_negative; | |
913 | ||
914 | return $temp; | |
915 | } | |
916 | ||
917 | if ($x_size < $y_size) { | |
918 | $size = $x_size; | |
919 | $value = $y_value; | |
920 | } else { | |
921 | $size = $y_size; | |
922 | $value = $x_value; | |
923 | } | |
924 | ||
925 | $value[count($value)] = 0; // just in case the carry adds an extra digit | |
926 | ||
927 | $carry = 0; | |
928 | for ($i = 0, $j = 1; $j < $size; $i+=2, $j+=2) { | |
929 | $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] + $y_value[$j] * MATH_BIGINTEGER_BASE_FULL + $y_value[$i] + $carry; | |
930 | $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT2; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 | |
931 | $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT2 : $sum; | |
932 | ||
933 | $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); | |
934 | ||
935 | $value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp); // eg. a faster alternative to fmod($sum, 0x4000000) | |
936 | $value[$j] = $temp; | |
937 | } | |
938 | ||
939 | if ($j == $size) { // ie. if $y_size is odd | |
940 | $sum = $x_value[$i] + $y_value[$i] + $carry; | |
941 | $carry = $sum >= MATH_BIGINTEGER_BASE_FULL; | |
942 | $value[$i] = $carry ? $sum - MATH_BIGINTEGER_BASE_FULL : $sum; | |
943 | ++$i; // ie. let $i = $j since we've just done $value[$i] | |
944 | } | |
945 | ||
946 | if ($carry) { | |
947 | for (; $value[$i] == MATH_BIGINTEGER_MAX_DIGIT; ++$i) { | |
948 | $value[$i] = 0; | |
949 | } | |
950 | ++$value[$i]; | |
951 | } | |
952 | ||
953 | return array( | |
954 | MATH_BIGINTEGER_VALUE => $this->_trim($value), | |
955 | MATH_BIGINTEGER_SIGN => $x_negative | |
956 | ); | |
957 | } | |
958 | ||
959 | /** | |
960 | * Subtracts two BigIntegers. | |
961 | * | |
962 | * Here's an example: | |
963 | * <code> | |
964 | * <?php | |
965 | * include 'Math/BigInteger.php'; | |
966 | * | |
967 | * $a = new Math_BigInteger('10'); | |
968 | * $b = new Math_BigInteger('20'); | |
969 | * | |
970 | * $c = $a->subtract($b); | |
971 | * | |
972 | * echo $c->toString(); // outputs -10 | |
973 | * ?> | |
974 | * </code> | |
975 | * | |
976 | * @param Math_BigInteger $y | |
977 | * @return Math_BigInteger | |
978 | * @access public | |
979 | * @internal Performs base-2**52 subtraction | |
980 | */ | |
981 | function subtract($y) | |
982 | { | |
983 | switch ( MATH_BIGINTEGER_MODE ) { | |
984 | case MATH_BIGINTEGER_MODE_GMP: | |
985 | $temp = new Math_BigInteger(); | |
986 | $temp->value = gmp_sub($this->value, $y->value); | |
987 | ||
988 | return $this->_normalize($temp); | |
989 | case MATH_BIGINTEGER_MODE_BCMATH: | |
990 | $temp = new Math_BigInteger(); | |
991 | $temp->value = bcsub($this->value, $y->value, 0); | |
992 | ||
993 | return $this->_normalize($temp); | |
994 | } | |
995 | ||
996 | $temp = $this->_subtract($this->value, $this->is_negative, $y->value, $y->is_negative); | |
997 | ||
998 | $result = new Math_BigInteger(); | |
999 | $result->value = $temp[MATH_BIGINTEGER_VALUE]; | |
1000 | $result->is_negative = $temp[MATH_BIGINTEGER_SIGN]; | |
1001 | ||
1002 | return $this->_normalize($result); | |
1003 | } | |
1004 | ||
1005 | /** | |
1006 | * Performs subtraction. | |
1007 | * | |
1008 | * @param Array $x_value | |
1009 | * @param Boolean $x_negative | |
1010 | * @param Array $y_value | |
1011 | * @param Boolean $y_negative | |
1012 | * @return Array | |
1013 | * @access private | |
1014 | */ | |
1015 | function _subtract($x_value, $x_negative, $y_value, $y_negative) | |
1016 | { | |
1017 | $x_size = count($x_value); | |
1018 | $y_size = count($y_value); | |
1019 | ||
1020 | if ($x_size == 0) { | |
1021 | return array( | |
1022 | MATH_BIGINTEGER_VALUE => $y_value, | |
1023 | MATH_BIGINTEGER_SIGN => !$y_negative | |
1024 | ); | |
1025 | } else if ($y_size == 0) { | |
1026 | return array( | |
1027 | MATH_BIGINTEGER_VALUE => $x_value, | |
1028 | MATH_BIGINTEGER_SIGN => $x_negative | |
1029 | ); | |
1030 | } | |
1031 | ||
1032 | // add, if appropriate (ie. -$x - +$y or +$x - -$y) | |
1033 | if ( $x_negative != $y_negative ) { | |
1034 | $temp = $this->_add($x_value, false, $y_value, false); | |
1035 | $temp[MATH_BIGINTEGER_SIGN] = $x_negative; | |
1036 | ||
1037 | return $temp; | |
1038 | } | |
1039 | ||
1040 | $diff = $this->_compare($x_value, $x_negative, $y_value, $y_negative); | |
1041 | ||
1042 | if ( !$diff ) { | |
1043 | return array( | |
1044 | MATH_BIGINTEGER_VALUE => array(), | |
1045 | MATH_BIGINTEGER_SIGN => false | |
1046 | ); | |
1047 | } | |
1048 | ||
1049 | // switch $x and $y around, if appropriate. | |
1050 | if ( (!$x_negative && $diff < 0) || ($x_negative && $diff > 0) ) { | |
1051 | $temp = $x_value; | |
1052 | $x_value = $y_value; | |
1053 | $y_value = $temp; | |
1054 | ||
1055 | $x_negative = !$x_negative; | |
1056 | ||
1057 | $x_size = count($x_value); | |
1058 | $y_size = count($y_value); | |
1059 | } | |
1060 | ||
1061 | // at this point, $x_value should be at least as big as - if not bigger than - $y_value | |
1062 | ||
1063 | $carry = 0; | |
1064 | for ($i = 0, $j = 1; $j < $y_size; $i+=2, $j+=2) { | |
1065 | $sum = $x_value[$j] * MATH_BIGINTEGER_BASE_FULL + $x_value[$i] - $y_value[$j] * MATH_BIGINTEGER_BASE_FULL - $y_value[$i] - $carry; | |
1066 | $carry = $sum < 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1 | |
1067 | $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT2 : $sum; | |
1068 | ||
1069 | $temp = MATH_BIGINTEGER_BASE === 26 ? intval($sum / 0x4000000) : ($sum >> 31); | |
1070 | ||
1071 | $x_value[$i] = (int) ($sum - MATH_BIGINTEGER_BASE_FULL * $temp); | |
1072 | $x_value[$j] = $temp; | |
1073 | } | |
1074 | ||
1075 | if ($j == $y_size) { // ie. if $y_size is odd | |
1076 | $sum = $x_value[$i] - $y_value[$i] - $carry; | |
1077 | $carry = $sum < 0; | |
1078 | $x_value[$i] = $carry ? $sum + MATH_BIGINTEGER_BASE_FULL : $sum; | |
1079 | ++$i; | |
1080 | } | |
1081 | ||
1082 | if ($carry) { | |
1083 | for (; !$x_value[$i]; ++$i) { | |
1084 | $x_value[$i] = MATH_BIGINTEGER_MAX_DIGIT; | |
1085 | } | |
1086 | --$x_value[$i]; | |
1087 | } | |
1088 | ||
1089 | return array( | |
1090 | MATH_BIGINTEGER_VALUE => $this->_trim($x_value), | |
1091 | MATH_BIGINTEGER_SIGN => $x_negative | |
1092 | ); | |
1093 | } | |
1094 | ||
1095 | /** | |
1096 | * Multiplies two BigIntegers | |
1097 | * | |
1098 | * Here's an example: | |
1099 | * <code> | |
1100 | * <?php | |
1101 | * include 'Math/BigInteger.php'; | |
1102 | * | |
1103 | * $a = new Math_BigInteger('10'); | |
1104 | * $b = new Math_BigInteger('20'); | |
1105 | * | |
1106 | * $c = $a->multiply($b); | |
1107 | * | |
1108 | * echo $c->toString(); // outputs 200 | |
1109 | * ?> | |
1110 | * </code> | |
1111 | * | |
1112 | * @param Math_BigInteger $x | |
1113 | * @return Math_BigInteger | |
1114 | * @access public | |
1115 | */ | |
1116 | function multiply($x) | |
1117 | { | |
1118 | switch ( MATH_BIGINTEGER_MODE ) { | |
1119 | case MATH_BIGINTEGER_MODE_GMP: | |
1120 | $temp = new Math_BigInteger(); | |
1121 | $temp->value = gmp_mul($this->value, $x->value); | |
1122 | ||
1123 | return $this->_normalize($temp); | |
1124 | case MATH_BIGINTEGER_MODE_BCMATH: | |
1125 | $temp = new Math_BigInteger(); | |
1126 | $temp->value = bcmul($this->value, $x->value, 0); | |
1127 | ||
1128 | return $this->_normalize($temp); | |
1129 | } | |
1130 | ||
1131 | $temp = $this->_multiply($this->value, $this->is_negative, $x->value, $x->is_negative); | |
1132 | ||
1133 | $product = new Math_BigInteger(); | |
1134 | $product->value = $temp[MATH_BIGINTEGER_VALUE]; | |
1135 | $product->is_negative = $temp[MATH_BIGINTEGER_SIGN]; | |
1136 | ||
1137 | return $this->_normalize($product); | |
1138 | } | |
1139 | ||
1140 | /** | |
1141 | * Performs multiplication. | |
1142 | * | |
1143 | * @param Array $x_value | |
1144 | * @param Boolean $x_negative | |
1145 | * @param Array $y_value | |
1146 | * @param Boolean $y_negative | |
1147 | * @return Array | |
1148 | * @access private | |
1149 | */ | |
1150 | function _multiply($x_value, $x_negative, $y_value, $y_negative) | |
1151 | { | |
1152 | //if ( $x_value == $y_value ) { | |
1153 | // return array( | |
1154 | // MATH_BIGINTEGER_VALUE => $this->_square($x_value), | |
1155 | // MATH_BIGINTEGER_SIGN => $x_sign != $y_value | |
1156 | // ); | |
1157 | //} | |
1158 | ||
1159 | $x_length = count($x_value); | |
1160 | $y_length = count($y_value); | |
1161 | ||
1162 | if ( !$x_length || !$y_length ) { // a 0 is being multiplied | |
1163 | return array( | |
1164 | MATH_BIGINTEGER_VALUE => array(), | |
1165 | MATH_BIGINTEGER_SIGN => false | |
1166 | ); | |
1167 | } | |
1168 | ||
1169 | return array( | |
1170 | MATH_BIGINTEGER_VALUE => min($x_length, $y_length) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ? | |
1171 | $this->_trim($this->_regularMultiply($x_value, $y_value)) : | |
1172 | $this->_trim($this->_karatsuba($x_value, $y_value)), | |
1173 | MATH_BIGINTEGER_SIGN => $x_negative != $y_negative | |
1174 | ); | |
1175 | } | |
1176 | ||
1177 | /** | |
1178 | * Performs long multiplication on two BigIntegers | |
1179 | * | |
1180 | * Modeled after 'multiply' in MutableBigInteger.java. | |
1181 | * | |
1182 | * @param Array $x_value | |
1183 | * @param Array $y_value | |
1184 | * @return Array | |
1185 | * @access private | |
1186 | */ | |
1187 | function _regularMultiply($x_value, $y_value) | |
1188 | { | |
1189 | $x_length = count($x_value); | |
1190 | $y_length = count($y_value); | |
1191 | ||
1192 | if ( !$x_length || !$y_length ) { // a 0 is being multiplied | |
1193 | return array(); | |
1194 | } | |
1195 | ||
1196 | if ( $x_length < $y_length ) { | |
1197 | $temp = $x_value; | |
1198 | $x_value = $y_value; | |
1199 | $y_value = $temp; | |
1200 | ||
1201 | $x_length = count($x_value); | |
1202 | $y_length = count($y_value); | |
1203 | } | |
1204 | ||
1205 | $product_value = $this->_array_repeat(0, $x_length + $y_length); | |
1206 | ||
1207 | // the following for loop could be removed if the for loop following it | |
1208 | // (the one with nested for loops) initially set $i to 0, but | |
1209 | // doing so would also make the result in one set of unnecessary adds, | |
1210 | // since on the outermost loops first pass, $product->value[$k] is going | |
1211 | // to always be 0 | |
1212 | ||
1213 | $carry = 0; | |
1214 | ||
1215 | for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0 | |
1216 | $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 | |
1217 | $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); | |
1218 | $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry); | |
1219 | } | |
1220 | ||
1221 | $product_value[$j] = $carry; | |
1222 | ||
1223 | // the above for loop is what the previous comment was talking about. the | |
1224 | // following for loop is the "one with nested for loops" | |
1225 | for ($i = 1; $i < $y_length; ++$i) { | |
1226 | $carry = 0; | |
1227 | ||
1228 | for ($j = 0, $k = $i; $j < $x_length; ++$j, ++$k) { | |
1229 | $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; | |
1230 | $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); | |
1231 | $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry); | |
1232 | } | |
1233 | ||
1234 | $product_value[$k] = $carry; | |
1235 | } | |
1236 | ||
1237 | return $product_value; | |
1238 | } | |
1239 | ||
1240 | /** | |
1241 | * Performs Karatsuba multiplication on two BigIntegers | |
1242 | * | |
1243 | * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and | |
1244 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}. | |
1245 | * | |
1246 | * @param Array $x_value | |
1247 | * @param Array $y_value | |
1248 | * @return Array | |
1249 | * @access private | |
1250 | */ | |
1251 | function _karatsuba($x_value, $y_value) | |
1252 | { | |
1253 | $m = min(count($x_value) >> 1, count($y_value) >> 1); | |
1254 | ||
1255 | if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) { | |
1256 | return $this->_regularMultiply($x_value, $y_value); | |
1257 | } | |
1258 | ||
1259 | $x1 = array_slice($x_value, $m); | |
1260 | $x0 = array_slice($x_value, 0, $m); | |
1261 | $y1 = array_slice($y_value, $m); | |
1262 | $y0 = array_slice($y_value, 0, $m); | |
1263 | ||
1264 | $z2 = $this->_karatsuba($x1, $y1); | |
1265 | $z0 = $this->_karatsuba($x0, $y0); | |
1266 | ||
1267 | $z1 = $this->_add($x1, false, $x0, false); | |
1268 | $temp = $this->_add($y1, false, $y0, false); | |
1269 | $z1 = $this->_karatsuba($z1[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_VALUE]); | |
1270 | $temp = $this->_add($z2, false, $z0, false); | |
1271 | $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false); | |
1272 | ||
1273 | $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); | |
1274 | $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]); | |
1275 | ||
1276 | $xy = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]); | |
1277 | $xy = $this->_add($xy[MATH_BIGINTEGER_VALUE], $xy[MATH_BIGINTEGER_SIGN], $z0, false); | |
1278 | ||
1279 | return $xy[MATH_BIGINTEGER_VALUE]; | |
1280 | } | |
1281 | ||
1282 | /** | |
1283 | * Performs squaring | |
1284 | * | |
1285 | * @param Array $x | |
1286 | * @return Array | |
1287 | * @access private | |
1288 | */ | |
1289 | function _square($x = false) | |
1290 | { | |
1291 | return count($x) < 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF ? | |
1292 | $this->_trim($this->_baseSquare($x)) : | |
1293 | $this->_trim($this->_karatsubaSquare($x)); | |
1294 | } | |
1295 | ||
1296 | /** | |
1297 | * Performs traditional squaring on two BigIntegers | |
1298 | * | |
1299 | * Squaring can be done faster than multiplying a number by itself can be. See | |
1300 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} / | |
1301 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information. | |
1302 | * | |
1303 | * @param Array $value | |
1304 | * @return Array | |
1305 | * @access private | |
1306 | */ | |
1307 | function _baseSquare($value) | |
1308 | { | |
1309 | if ( empty($value) ) { | |
1310 | return array(); | |
1311 | } | |
1312 | $square_value = $this->_array_repeat(0, 2 * count($value)); | |
1313 | ||
1314 | for ($i = 0, $max_index = count($value) - 1; $i <= $max_index; ++$i) { | |
1315 | $i2 = $i << 1; | |
1316 | ||
1317 | $temp = $square_value[$i2] + $value[$i] * $value[$i]; | |
1318 | $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); | |
1319 | $square_value[$i2] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry); | |
1320 | ||
1321 | // note how we start from $i+1 instead of 0 as we do in multiplication. | |
1322 | for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; ++$j, ++$k) { | |
1323 | $temp = $square_value[$k] + 2 * $value[$j] * $value[$i] + $carry; | |
1324 | $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); | |
1325 | $square_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry); | |
1326 | } | |
1327 | ||
1328 | // the following line can yield values larger 2**15. at this point, PHP should switch | |
1329 | // over to floats. | |
1330 | $square_value[$i + $max_index + 1] = $carry; | |
1331 | } | |
1332 | ||
1333 | return $square_value; | |
1334 | } | |
1335 | ||
1336 | /** | |
1337 | * Performs Karatsuba "squaring" on two BigIntegers | |
1338 | * | |
1339 | * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and | |
1340 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}. | |
1341 | * | |
1342 | * @param Array $value | |
1343 | * @return Array | |
1344 | * @access private | |
1345 | */ | |
1346 | function _karatsubaSquare($value) | |
1347 | { | |
1348 | $m = count($value) >> 1; | |
1349 | ||
1350 | if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) { | |
1351 | return $this->_baseSquare($value); | |
1352 | } | |
1353 | ||
1354 | $x1 = array_slice($value, $m); | |
1355 | $x0 = array_slice($value, 0, $m); | |
1356 | ||
1357 | $z2 = $this->_karatsubaSquare($x1); | |
1358 | $z0 = $this->_karatsubaSquare($x0); | |
1359 | ||
1360 | $z1 = $this->_add($x1, false, $x0, false); | |
1361 | $z1 = $this->_karatsubaSquare($z1[MATH_BIGINTEGER_VALUE]); | |
1362 | $temp = $this->_add($z2, false, $z0, false); | |
1363 | $z1 = $this->_subtract($z1, false, $temp[MATH_BIGINTEGER_VALUE], false); | |
1364 | ||
1365 | $z2 = array_merge(array_fill(0, 2 * $m, 0), $z2); | |
1366 | $z1[MATH_BIGINTEGER_VALUE] = array_merge(array_fill(0, $m, 0), $z1[MATH_BIGINTEGER_VALUE]); | |
1367 | ||
1368 | $xx = $this->_add($z2, false, $z1[MATH_BIGINTEGER_VALUE], $z1[MATH_BIGINTEGER_SIGN]); | |
1369 | $xx = $this->_add($xx[MATH_BIGINTEGER_VALUE], $xx[MATH_BIGINTEGER_SIGN], $z0, false); | |
1370 | ||
1371 | return $xx[MATH_BIGINTEGER_VALUE]; | |
1372 | } | |
1373 | ||
1374 | /** | |
1375 | * Divides two BigIntegers. | |
1376 | * | |
1377 | * Returns an array whose first element contains the quotient and whose second element contains the | |
1378 | * "common residue". If the remainder would be positive, the "common residue" and the remainder are the | |
1379 | * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder | |
1380 | * and the divisor (basically, the "common residue" is the first positive modulo). | |
1381 | * | |
1382 | * Here's an example: | |
1383 | * <code> | |
1384 | * <?php | |
1385 | * include 'Math/BigInteger.php'; | |
1386 | * | |
1387 | * $a = new Math_BigInteger('10'); | |
1388 | * $b = new Math_BigInteger('20'); | |
1389 | * | |
1390 | * list($quotient, $remainder) = $a->divide($b); | |
1391 | * | |
1392 | * echo $quotient->toString(); // outputs 0 | |
1393 | * echo "\r\n"; | |
1394 | * echo $remainder->toString(); // outputs 10 | |
1395 | * ?> | |
1396 | * </code> | |
1397 | * | |
1398 | * @param Math_BigInteger $y | |
1399 | * @return Array | |
1400 | * @access public | |
1401 | * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}. | |
1402 | */ | |
1403 | function divide($y) | |
1404 | { | |
1405 | switch ( MATH_BIGINTEGER_MODE ) { | |
1406 | case MATH_BIGINTEGER_MODE_GMP: | |
1407 | $quotient = new Math_BigInteger(); | |
1408 | $remainder = new Math_BigInteger(); | |
1409 | ||
1410 | list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value); | |
1411 | ||
1412 | if (gmp_sign($remainder->value) < 0) { | |
1413 | $remainder->value = gmp_add($remainder->value, gmp_abs($y->value)); | |
1414 | } | |
1415 | ||
1416 | return array($this->_normalize($quotient), $this->_normalize($remainder)); | |
1417 | case MATH_BIGINTEGER_MODE_BCMATH: | |
1418 | $quotient = new Math_BigInteger(); | |
1419 | $remainder = new Math_BigInteger(); | |
1420 | ||
1421 | $quotient->value = bcdiv($this->value, $y->value, 0); | |
1422 | $remainder->value = bcmod($this->value, $y->value); | |
1423 | ||
1424 | if ($remainder->value[0] == '-') { | |
1425 | $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value, 0); | |
1426 | } | |
1427 | ||
1428 | return array($this->_normalize($quotient), $this->_normalize($remainder)); | |
1429 | } | |
1430 | ||
1431 | if (count($y->value) == 1) { | |
1432 | list($q, $r) = $this->_divide_digit($this->value, $y->value[0]); | |
1433 | $quotient = new Math_BigInteger(); | |
1434 | $remainder = new Math_BigInteger(); | |
1435 | $quotient->value = $q; | |
1436 | $remainder->value = array($r); | |
1437 | $quotient->is_negative = $this->is_negative != $y->is_negative; | |
1438 | return array($this->_normalize($quotient), $this->_normalize($remainder)); | |
1439 | } | |
1440 | ||
1441 | static $zero; | |
1442 | if ( !isset($zero) ) { | |
1443 | $zero = new Math_BigInteger(); | |
1444 | } | |
1445 | ||
1446 | $x = $this->copy(); | |
1447 | $y = $y->copy(); | |
1448 | ||
1449 | $x_sign = $x->is_negative; | |
1450 | $y_sign = $y->is_negative; | |
1451 | ||
1452 | $x->is_negative = $y->is_negative = false; | |
1453 | ||
1454 | $diff = $x->compare($y); | |
1455 | ||
1456 | if ( !$diff ) { | |
1457 | $temp = new Math_BigInteger(); | |
1458 | $temp->value = array(1); | |
1459 | $temp->is_negative = $x_sign != $y_sign; | |
1460 | return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger())); | |
1461 | } | |
1462 | ||
1463 | if ( $diff < 0 ) { | |
1464 | // if $x is negative, "add" $y. | |
1465 | if ( $x_sign ) { | |
1466 | $x = $y->subtract($x); | |
1467 | } | |
1468 | return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x)); | |
1469 | } | |
1470 | ||
1471 | // normalize $x and $y as described in HAC 14.23 / 14.24 | |
1472 | $msb = $y->value[count($y->value) - 1]; | |
1473 | for ($shift = 0; !($msb & MATH_BIGINTEGER_MSB); ++$shift) { | |
1474 | $msb <<= 1; | |
1475 | } | |
1476 | $x->_lshift($shift); | |
1477 | $y->_lshift($shift); | |
1478 | $y_value = &$y->value; | |
1479 | ||
1480 | $x_max = count($x->value) - 1; | |
1481 | $y_max = count($y->value) - 1; | |
1482 | ||
1483 | $quotient = new Math_BigInteger(); | |
1484 | $quotient_value = &$quotient->value; | |
1485 | $quotient_value = $this->_array_repeat(0, $x_max - $y_max + 1); | |
1486 | ||
1487 | static $temp, $lhs, $rhs; | |
1488 | if (!isset($temp)) { | |
1489 | $temp = new Math_BigInteger(); | |
1490 | $lhs = new Math_BigInteger(); | |
1491 | $rhs = new Math_BigInteger(); | |
1492 | } | |
1493 | $temp_value = &$temp->value; | |
1494 | $rhs_value = &$rhs->value; | |
1495 | ||
1496 | // $temp = $y << ($x_max - $y_max-1) in base 2**26 | |
1497 | $temp_value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y_value); | |
1498 | ||
1499 | while ( $x->compare($temp) >= 0 ) { | |
1500 | // calculate the "common residue" | |
1501 | ++$quotient_value[$x_max - $y_max]; | |
1502 | $x = $x->subtract($temp); | |
1503 | $x_max = count($x->value) - 1; | |
1504 | } | |
1505 | ||
1506 | for ($i = $x_max; $i >= $y_max + 1; --$i) { | |
1507 | $x_value = &$x->value; | |
1508 | $x_window = array( | |
1509 | isset($x_value[$i]) ? $x_value[$i] : 0, | |
1510 | isset($x_value[$i - 1]) ? $x_value[$i - 1] : 0, | |
1511 | isset($x_value[$i - 2]) ? $x_value[$i - 2] : 0 | |
1512 | ); | |
1513 | $y_window = array( | |
1514 | $y_value[$y_max], | |
1515 | ( $y_max > 0 ) ? $y_value[$y_max - 1] : 0 | |
1516 | ); | |
1517 | ||
1518 | $q_index = $i - $y_max - 1; | |
1519 | if ($x_window[0] == $y_window[0]) { | |
1520 | $quotient_value[$q_index] = MATH_BIGINTEGER_MAX_DIGIT; | |
1521 | } else { | |
1522 | $quotient_value[$q_index] = $this->_safe_divide( | |
1523 | $x_window[0] * MATH_BIGINTEGER_BASE_FULL + $x_window[1], | |
1524 | $y_window[0] | |
1525 | ); | |
1526 | } | |
1527 | ||
1528 | $temp_value = array($y_window[1], $y_window[0]); | |
1529 | ||
1530 | $lhs->value = array($quotient_value[$q_index]); | |
1531 | $lhs = $lhs->multiply($temp); | |
1532 | ||
1533 | $rhs_value = array($x_window[2], $x_window[1], $x_window[0]); | |
1534 | ||
1535 | while ( $lhs->compare($rhs) > 0 ) { | |
1536 | --$quotient_value[$q_index]; | |
1537 | ||
1538 | $lhs->value = array($quotient_value[$q_index]); | |
1539 | $lhs = $lhs->multiply($temp); | |
1540 | } | |
1541 | ||
1542 | $adjust = $this->_array_repeat(0, $q_index); | |
1543 | $temp_value = array($quotient_value[$q_index]); | |
1544 | $temp = $temp->multiply($y); | |
1545 | $temp_value = &$temp->value; | |
1546 | $temp_value = array_merge($adjust, $temp_value); | |
1547 | ||
1548 | $x = $x->subtract($temp); | |
1549 | ||
1550 | if ($x->compare($zero) < 0) { | |
1551 | $temp_value = array_merge($adjust, $y_value); | |
1552 | $x = $x->add($temp); | |
1553 | ||
1554 | --$quotient_value[$q_index]; | |
1555 | } | |
1556 | ||
1557 | $x_max = count($x_value) - 1; | |
1558 | } | |
1559 | ||
1560 | // unnormalize the remainder | |
1561 | $x->_rshift($shift); | |
1562 | ||
1563 | $quotient->is_negative = $x_sign != $y_sign; | |
1564 | ||
1565 | // calculate the "common residue", if appropriate | |
1566 | if ( $x_sign ) { | |
1567 | $y->_rshift($shift); | |
1568 | $x = $y->subtract($x); | |
1569 | } | |
1570 | ||
1571 | return array($this->_normalize($quotient), $this->_normalize($x)); | |
1572 | } | |
1573 | ||
1574 | /** | |
1575 | * Divides a BigInteger by a regular integer | |
1576 | * | |
1577 | * abc / x = a00 / x + b0 / x + c / x | |
1578 | * | |
1579 | * @param Array $dividend | |
1580 | * @param Array $divisor | |
1581 | * @return Array | |
1582 | * @access private | |
1583 | */ | |
1584 | function _divide_digit($dividend, $divisor) | |
1585 | { | |
1586 | $carry = 0; | |
1587 | $result = array(); | |
1588 | ||
1589 | for ($i = count($dividend) - 1; $i >= 0; --$i) { | |
1590 | $temp = MATH_BIGINTEGER_BASE_FULL * $carry + $dividend[$i]; | |
1591 | $result[$i] = $this->_safe_divide($temp, $divisor); | |
1592 | $carry = (int) ($temp - $divisor * $result[$i]); | |
1593 | } | |
1594 | ||
1595 | return array($result, $carry); | |
1596 | } | |
1597 | ||
1598 | /** | |
1599 | * Performs modular exponentiation. | |
1600 | * | |
1601 | * Here's an example: | |
1602 | * <code> | |
1603 | * <?php | |
1604 | * include 'Math/BigInteger.php'; | |
1605 | * | |
1606 | * $a = new Math_BigInteger('10'); | |
1607 | * $b = new Math_BigInteger('20'); | |
1608 | * $c = new Math_BigInteger('30'); | |
1609 | * | |
1610 | * $c = $a->modPow($b, $c); | |
1611 | * | |
1612 | * echo $c->toString(); // outputs 10 | |
1613 | * ?> | |
1614 | * </code> | |
1615 | * | |
1616 | * @param Math_BigInteger $e | |
1617 | * @param Math_BigInteger $n | |
1618 | * @return Math_BigInteger | |
1619 | * @access public | |
1620 | * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and | |
1621 | * and although the approach involving repeated squaring does vastly better, it, too, is impractical | |
1622 | * for our purposes. The reason being that division - by far the most complicated and time-consuming | |
1623 | * of the basic operations (eg. +,-,*,/) - occurs multiple times within it. | |
1624 | * | |
1625 | * Modular reductions resolve this issue. Although an individual modular reduction takes more time | |
1626 | * then an individual division, when performed in succession (with the same modulo), they're a lot faster. | |
1627 | * | |
1628 | * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction, | |
1629 | * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the | |
1630 | * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because | |
1631 | * the product of two odd numbers is odd), but what about when RSA isn't used? | |
1632 | * | |
1633 | * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a | |
1634 | * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the | |
1635 | * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however, | |
1636 | * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and | |
1637 | * the other, a power of two - and recombine them, later. This is the method that this modPow function uses. | |
1638 | * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates. | |
1639 | */ | |
1640 | function modPow($e, $n) | |
1641 | { | |
1642 | $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs(); | |
1643 | ||
1644 | if ($e->compare(new Math_BigInteger()) < 0) { | |
1645 | $e = $e->abs(); | |
1646 | ||
1647 | $temp = $this->modInverse($n); | |
1648 | if ($temp === false) { | |
1649 | return false; | |
1650 | } | |
1651 | ||
1652 | return $this->_normalize($temp->modPow($e, $n)); | |
1653 | } | |
1654 | ||
1655 | if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP ) { | |
1656 | $temp = new Math_BigInteger(); | |
1657 | $temp->value = gmp_powm($this->value, $e->value, $n->value); | |
1658 | ||
1659 | return $this->_normalize($temp); | |
1660 | } | |
1661 | ||
1662 | if ($this->compare(new Math_BigInteger()) < 0 || $this->compare($n) > 0) { | |
1663 | list(, $temp) = $this->divide($n); | |
1664 | return $temp->modPow($e, $n); | |
1665 | } | |
1666 | ||
1667 | if (defined('MATH_BIGINTEGER_OPENSSL_ENABLED')) { | |
1668 | $components = array( | |
1669 | 'modulus' => $n->toBytes(true), | |
1670 | 'publicExponent' => $e->toBytes(true) | |
1671 | ); | |
1672 | ||
1673 | $components = array( | |
1674 | 'modulus' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['modulus'])), $components['modulus']), | |
1675 | 'publicExponent' => pack('Ca*a*', 2, $this->_encodeASN1Length(strlen($components['publicExponent'])), $components['publicExponent']) | |
1676 | ); | |
1677 | ||
1678 | $RSAPublicKey = pack('Ca*a*a*', | |
1679 | 48, $this->_encodeASN1Length(strlen($components['modulus']) + strlen($components['publicExponent'])), | |
1680 | $components['modulus'], $components['publicExponent'] | |
1681 | ); | |
1682 | ||
1683 | $rsaOID = pack('H*', '300d06092a864886f70d0101010500'); // hex version of MA0GCSqGSIb3DQEBAQUA | |
1684 | $RSAPublicKey = chr(0) . $RSAPublicKey; | |
1685 | $RSAPublicKey = chr(3) . $this->_encodeASN1Length(strlen($RSAPublicKey)) . $RSAPublicKey; | |
1686 | ||
1687 | $encapsulated = pack('Ca*a*', | |
1688 | 48, $this->_encodeASN1Length(strlen($rsaOID . $RSAPublicKey)), $rsaOID . $RSAPublicKey | |
1689 | ); | |
1690 | ||
1691 | $RSAPublicKey = "-----BEGIN PUBLIC KEY-----\r\n" . | |
1692 | chunk_split(base64_encode($encapsulated)) . | |
1693 | '-----END PUBLIC KEY-----'; | |
1694 | ||
1695 | $plaintext = str_pad($this->toBytes(), strlen($n->toBytes(true)) - 1, "\0", STR_PAD_LEFT); | |
1696 | ||
1697 | if (openssl_public_encrypt($plaintext, $result, $RSAPublicKey, OPENSSL_NO_PADDING)) { | |
1698 | return new Math_BigInteger($result, 256); | |
1699 | } | |
1700 | } | |
1701 | ||
1702 | if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) { | |
1703 | $temp = new Math_BigInteger(); | |
1704 | $temp->value = bcpowmod($this->value, $e->value, $n->value, 0); | |
1705 | ||
1706 | return $this->_normalize($temp); | |
1707 | } | |
1708 | ||
1709 | if ( empty($e->value) ) { | |
1710 | $temp = new Math_BigInteger(); | |
1711 | $temp->value = array(1); | |
1712 | return $this->_normalize($temp); | |
1713 | } | |
1714 | ||
1715 | if ( $e->value == array(1) ) { | |
1716 | list(, $temp) = $this->divide($n); | |
1717 | return $this->_normalize($temp); | |
1718 | } | |
1719 | ||
1720 | if ( $e->value == array(2) ) { | |
1721 | $temp = new Math_BigInteger(); | |
1722 | $temp->value = $this->_square($this->value); | |
1723 | list(, $temp) = $temp->divide($n); | |
1724 | return $this->_normalize($temp); | |
1725 | } | |
1726 | ||
1727 | return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT)); | |
1728 | ||
1729 | // the following code, although not callable, can be run independently of the above code | |
1730 | // although the above code performed better in my benchmarks the following could might | |
1731 | // perform better under different circumstances. in lieu of deleting it it's just been | |
1732 | // made uncallable | |
1733 | ||
1734 | // is the modulo odd? | |
1735 | if ( $n->value[0] & 1 ) { | |
1736 | return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY)); | |
1737 | } | |
1738 | // if it's not, it's even | |
1739 | ||
1740 | // find the lowest set bit (eg. the max pow of 2 that divides $n) | |
1741 | for ($i = 0; $i < count($n->value); ++$i) { | |
1742 | if ( $n->value[$i] ) { | |
1743 | $temp = decbin($n->value[$i]); | |
1744 | $j = strlen($temp) - strrpos($temp, '1') - 1; | |
1745 | $j+= 26 * $i; | |
1746 | break; | |
1747 | } | |
1748 | } | |
1749 | // at this point, 2^$j * $n/(2^$j) == $n | |
1750 | ||
1751 | $mod1 = $n->copy(); | |
1752 | $mod1->_rshift($j); | |
1753 | $mod2 = new Math_BigInteger(); | |
1754 | $mod2->value = array(1); | |
1755 | $mod2->_lshift($j); | |
1756 | ||
1757 | $part1 = ( $mod1->value != array(1) ) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger(); | |
1758 | $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2); | |
1759 | ||
1760 | $y1 = $mod2->modInverse($mod1); | |
1761 | $y2 = $mod1->modInverse($mod2); | |
1762 | ||
1763 | $result = $part1->multiply($mod2); | |
1764 | $result = $result->multiply($y1); | |
1765 | ||
1766 | $temp = $part2->multiply($mod1); | |
1767 | $temp = $temp->multiply($y2); | |
1768 | ||
1769 | $result = $result->add($temp); | |
1770 | list(, $result) = $result->divide($n); | |
1771 | ||
1772 | return $this->_normalize($result); | |
1773 | } | |
1774 | ||
1775 | /** | |
1776 | * Performs modular exponentiation. | |
1777 | * | |
1778 | * Alias for Math_BigInteger::modPow() | |
1779 | * | |
1780 | * @param Math_BigInteger $e | |
1781 | * @param Math_BigInteger $n | |
1782 | * @return Math_BigInteger | |
1783 | * @access public | |
1784 | */ | |
1785 | function powMod($e, $n) | |
1786 | { | |
1787 | return $this->modPow($e, $n); | |
1788 | } | |
1789 | ||
1790 | /** | |
1791 | * Sliding Window k-ary Modular Exponentiation | |
1792 | * | |
1793 | * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} / | |
1794 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims, | |
1795 | * however, this function performs a modular reduction after every multiplication and squaring operation. | |
1796 | * As such, this function has the same preconditions that the reductions being used do. | |
1797 | * | |
1798 | * @param Math_BigInteger $e | |
1799 | * @param Math_BigInteger $n | |
1800 | * @param Integer $mode | |
1801 | * @return Math_BigInteger | |
1802 | * @access private | |
1803 | */ | |
1804 | function _slidingWindow($e, $n, $mode) | |
1805 | { | |
1806 | static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function | |
1807 | //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1 | |
1808 | ||
1809 | $e_value = $e->value; | |
1810 | $e_length = count($e_value) - 1; | |
1811 | $e_bits = decbin($e_value[$e_length]); | |
1812 | for ($i = $e_length - 1; $i >= 0; --$i) { | |
1813 | $e_bits.= str_pad(decbin($e_value[$i]), MATH_BIGINTEGER_BASE, '0', STR_PAD_LEFT); | |
1814 | } | |
1815 | ||
1816 | $e_length = strlen($e_bits); | |
1817 | ||
1818 | // calculate the appropriate window size. | |
1819 | // $window_size == 3 if $window_ranges is between 25 and 81, for example. | |
1820 | for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); ++$window_size, ++$i); | |
1821 | ||
1822 | $n_value = $n->value; | |
1823 | ||
1824 | // precompute $this^0 through $this^$window_size | |
1825 | $powers = array(); | |
1826 | $powers[1] = $this->_prepareReduce($this->value, $n_value, $mode); | |
1827 | $powers[2] = $this->_squareReduce($powers[1], $n_value, $mode); | |
1828 | ||
1829 | // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end | |
1830 | // in a 1. ie. it's supposed to be odd. | |
1831 | $temp = 1 << ($window_size - 1); | |
1832 | for ($i = 1; $i < $temp; ++$i) { | |
1833 | $i2 = $i << 1; | |
1834 | $powers[$i2 + 1] = $this->_multiplyReduce($powers[$i2 - 1], $powers[2], $n_value, $mode); | |
1835 | } | |
1836 | ||
1837 | $result = array(1); | |
1838 | $result = $this->_prepareReduce($result, $n_value, $mode); | |
1839 | ||
1840 | for ($i = 0; $i < $e_length; ) { | |
1841 | if ( !$e_bits[$i] ) { | |
1842 | $result = $this->_squareReduce($result, $n_value, $mode); | |
1843 | ++$i; | |
1844 | } else { | |
1845 | for ($j = $window_size - 1; $j > 0; --$j) { | |
1846 | if ( !empty($e_bits[$i + $j]) ) { | |
1847 | break; | |
1848 | } | |
1849 | } | |
1850 | ||
1851 | for ($k = 0; $k <= $j; ++$k) {// eg. the length of substr($e_bits, $i, $j+1) | |
1852 | $result = $this->_squareReduce($result, $n_value, $mode); | |
1853 | } | |
1854 | ||
1855 | $result = $this->_multiplyReduce($result, $powers[bindec(substr($e_bits, $i, $j + 1))], $n_value, $mode); | |
1856 | ||
1857 | $i+=$j + 1; | |
1858 | } | |
1859 | } | |
1860 | ||
1861 | $temp = new Math_BigInteger(); | |
1862 | $temp->value = $this->_reduce($result, $n_value, $mode); | |
1863 | ||
1864 | return $temp; | |
1865 | } | |
1866 | ||
1867 | /** | |
1868 | * Modular reduction | |
1869 | * | |
1870 | * For most $modes this will return the remainder. | |
1871 | * | |
1872 | * @see _slidingWindow() | |
1873 | * @access private | |
1874 | * @param Array $x | |
1875 | * @param Array $n | |
1876 | * @param Integer $mode | |
1877 | * @return Array | |
1878 | */ | |
1879 | function _reduce($x, $n, $mode) | |
1880 | { | |
1881 | switch ($mode) { | |
1882 | case MATH_BIGINTEGER_MONTGOMERY: | |
1883 | return $this->_montgomery($x, $n); | |
1884 | case MATH_BIGINTEGER_BARRETT: | |
1885 | return $this->_barrett($x, $n); | |
1886 | case MATH_BIGINTEGER_POWEROF2: | |
1887 | $lhs = new Math_BigInteger(); | |
1888 | $lhs->value = $x; | |
1889 | $rhs = new Math_BigInteger(); | |
1890 | $rhs->value = $n; | |
1891 | return $x->_mod2($n); | |
1892 | case MATH_BIGINTEGER_CLASSIC: | |
1893 | $lhs = new Math_BigInteger(); | |
1894 | $lhs->value = $x; | |
1895 | $rhs = new Math_BigInteger(); | |
1896 | $rhs->value = $n; | |
1897 | list(, $temp) = $lhs->divide($rhs); | |
1898 | return $temp->value; | |
1899 | case MATH_BIGINTEGER_NONE: | |
1900 | return $x; | |
1901 | default: | |
1902 | // an invalid $mode was provided | |
1903 | } | |
1904 | } | |
1905 | ||
1906 | /** | |
1907 | * Modular reduction preperation | |
1908 | * | |
1909 | * @see _slidingWindow() | |
1910 | * @access private | |
1911 | * @param Array $x | |
1912 | * @param Array $n | |
1913 | * @param Integer $mode | |
1914 | * @return Array | |
1915 | */ | |
1916 | function _prepareReduce($x, $n, $mode) | |
1917 | { | |
1918 | if ($mode == MATH_BIGINTEGER_MONTGOMERY) { | |
1919 | return $this->_prepMontgomery($x, $n); | |
1920 | } | |
1921 | return $this->_reduce($x, $n, $mode); | |
1922 | } | |
1923 | ||
1924 | /** | |
1925 | * Modular multiply | |
1926 | * | |
1927 | * @see _slidingWindow() | |
1928 | * @access private | |
1929 | * @param Array $x | |
1930 | * @param Array $y | |
1931 | * @param Array $n | |
1932 | * @param Integer $mode | |
1933 | * @return Array | |
1934 | */ | |
1935 | function _multiplyReduce($x, $y, $n, $mode) | |
1936 | { | |
1937 | if ($mode == MATH_BIGINTEGER_MONTGOMERY) { | |
1938 | return $this->_montgomeryMultiply($x, $y, $n); | |
1939 | } | |
1940 | $temp = $this->_multiply($x, false, $y, false); | |
1941 | return $this->_reduce($temp[MATH_BIGINTEGER_VALUE], $n, $mode); | |
1942 | } | |
1943 | ||
1944 | /** | |
1945 | * Modular square | |
1946 | * | |
1947 | * @see _slidingWindow() | |
1948 | * @access private | |
1949 | * @param Array $x | |
1950 | * @param Array $n | |
1951 | * @param Integer $mode | |
1952 | * @return Array | |
1953 | */ | |
1954 | function _squareReduce($x, $n, $mode) | |
1955 | { | |
1956 | if ($mode == MATH_BIGINTEGER_MONTGOMERY) { | |
1957 | return $this->_montgomeryMultiply($x, $x, $n); | |
1958 | } | |
1959 | return $this->_reduce($this->_square($x), $n, $mode); | |
1960 | } | |
1961 | ||
1962 | /** | |
1963 | * Modulos for Powers of Two | |
1964 | * | |
1965 | * Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1), | |
1966 | * we'll just use this function as a wrapper for doing that. | |
1967 | * | |
1968 | * @see _slidingWindow() | |
1969 | * @access private | |
1970 | * @param Math_BigInteger | |
1971 | * @return Math_BigInteger | |
1972 | */ | |
1973 | function _mod2($n) | |
1974 | { | |
1975 | $temp = new Math_BigInteger(); | |
1976 | $temp->value = array(1); | |
1977 | return $this->bitwise_and($n->subtract($temp)); | |
1978 | } | |
1979 | ||
1980 | /** | |
1981 | * Barrett Modular Reduction | |
1982 | * | |
1983 | * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} / | |
1984 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly, | |
1985 | * so as not to require negative numbers (initially, this script didn't support negative numbers). | |
1986 | * | |
1987 | * Employs "folding", as described at | |
1988 | * {@link http://www.cosic.esat.kuleuven.be/publications/thesis-149.pdf#page=66 thesis-149.pdf#page=66}. To quote from | |
1989 | * 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." | |
1990 | * | |
1991 | * Unfortunately, the "Barrett Reduction with Folding" algorithm described in thesis-149.pdf is not, as written, all that | |
1992 | * usable on account of (1) its not using reasonable radix points as discussed in | |
1993 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=162 MPM 6.2.2} and (2) the fact that, even with reasonable | |
1994 | * radix points, it only works when there are an even number of digits in the denominator. The reason for (2) is that | |
1995 | * (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 | |
1996 | * comments for details. | |
1997 | * | |
1998 | * @see _slidingWindow() | |
1999 | * @access private | |
2000 | * @param Array $n | |
2001 | * @param Array $m | |
2002 | * @return Array | |
2003 | */ | |
2004 | function _barrett($n, $m) | |
2005 | { | |
2006 | static $cache = array( | |
2007 | MATH_BIGINTEGER_VARIABLE => array(), | |
2008 | MATH_BIGINTEGER_DATA => array() | |
2009 | ); | |
2010 | ||
2011 | $m_length = count($m); | |
2012 | ||
2013 | // if ($this->_compare($n, $this->_square($m)) >= 0) { | |
2014 | if (count($n) > 2 * $m_length) { | |
2015 | $lhs = new Math_BigInteger(); | |
2016 | $rhs = new Math_BigInteger(); | |
2017 | $lhs->value = $n; | |
2018 | $rhs->value = $m; | |
2019 | list(, $temp) = $lhs->divide($rhs); | |
2020 | return $temp->value; | |
2021 | } | |
2022 | ||
2023 | // if (m.length >> 1) + 2 <= m.length then m is too small and n can't be reduced | |
2024 | if ($m_length < 5) { | |
2025 | return $this->_regularBarrett($n, $m); | |
2026 | } | |
2027 | ||
2028 | // n = 2 * m.length | |
2029 | ||
2030 | if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) { | |
2031 | $key = count($cache[MATH_BIGINTEGER_VARIABLE]); | |
2032 | $cache[MATH_BIGINTEGER_VARIABLE][] = $m; | |
2033 | ||
2034 | $lhs = new Math_BigInteger(); | |
2035 | $lhs_value = &$lhs->value; | |
2036 | $lhs_value = $this->_array_repeat(0, $m_length + ($m_length >> 1)); | |
2037 | $lhs_value[] = 1; | |
2038 | $rhs = new Math_BigInteger(); | |
2039 | $rhs->value = $m; | |
2040 | ||
2041 | list($u, $m1) = $lhs->divide($rhs); | |
2042 | $u = $u->value; | |
2043 | $m1 = $m1->value; | |
2044 | ||
2045 | $cache[MATH_BIGINTEGER_DATA][] = array( | |
2046 | 'u' => $u, // m.length >> 1 (technically (m.length >> 1) + 1) | |
2047 | 'm1'=> $m1 // m.length | |
2048 | ); | |
2049 | } else { | |
2050 | extract($cache[MATH_BIGINTEGER_DATA][$key]); | |
2051 | } | |
2052 | ||
2053 | $cutoff = $m_length + ($m_length >> 1); | |
2054 | $lsd = array_slice($n, 0, $cutoff); // m.length + (m.length >> 1) | |
2055 | $msd = array_slice($n, $cutoff); // m.length >> 1 | |
2056 | $lsd = $this->_trim($lsd); | |
2057 | $temp = $this->_multiply($msd, false, $m1, false); | |
2058 | $n = $this->_add($lsd, false, $temp[MATH_BIGINTEGER_VALUE], false); // m.length + (m.length >> 1) + 1 | |
2059 | ||
2060 | if ($m_length & 1) { | |
2061 | return $this->_regularBarrett($n[MATH_BIGINTEGER_VALUE], $m); | |
2062 | } | |
2063 | ||
2064 | // (m.length + (m.length >> 1) + 1) - (m.length - 1) == (m.length >> 1) + 2 | |
2065 | $temp = array_slice($n[MATH_BIGINTEGER_VALUE], $m_length - 1); | |
2066 | // if even: ((m.length >> 1) + 2) + (m.length >> 1) == m.length + 2 | |
2067 | // if odd: ((m.length >> 1) + 2) + (m.length >> 1) == (m.length - 1) + 2 == m.length + 1 | |
2068 | $temp = $this->_multiply($temp, false, $u, false); | |
2069 | // if even: (m.length + 2) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) + 1 | |
2070 | // if odd: (m.length + 1) - ((m.length >> 1) + 1) = m.length - (m.length >> 1) | |
2071 | $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], ($m_length >> 1) + 1); | |
2072 | // if even: (m.length - (m.length >> 1) + 1) + m.length = 2 * m.length - (m.length >> 1) + 1 | |
2073 | // if odd: (m.length - (m.length >> 1)) + m.length = 2 * m.length - (m.length >> 1) | |
2074 | $temp = $this->_multiply($temp, false, $m, false); | |
2075 | ||
2076 | // at this point, if m had an odd number of digits, we'd be subtracting a 2 * m.length - (m.length >> 1) digit | |
2077 | // number from a m.length + (m.length >> 1) + 1 digit number. ie. there'd be an extra digit and the while loop | |
2078 | // following this comment would loop a lot (hence our calling _regularBarrett() in that situation). | |
2079 | ||
2080 | $result = $this->_subtract($n[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false); | |
2081 | ||
2082 | while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false) >= 0) { | |
2083 | $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $m, false); | |
2084 | } | |
2085 | ||
2086 | return $result[MATH_BIGINTEGER_VALUE]; | |
2087 | } | |
2088 | ||
2089 | /** | |
2090 | * (Regular) Barrett Modular Reduction | |
2091 | * | |
2092 | * For numbers with more than four digits Math_BigInteger::_barrett() is faster. The difference between that and this | |
2093 | * is that this function does not fold the denominator into a smaller form. | |
2094 | * | |
2095 | * @see _slidingWindow() | |
2096 | * @access private | |
2097 | * @param Array $x | |
2098 | * @param Array $n | |
2099 | * @return Array | |
2100 | */ | |
2101 | function _regularBarrett($x, $n) | |
2102 | { | |
2103 | static $cache = array( | |
2104 | MATH_BIGINTEGER_VARIABLE => array(), | |
2105 | MATH_BIGINTEGER_DATA => array() | |
2106 | ); | |
2107 | ||
2108 | $n_length = count($n); | |
2109 | ||
2110 | if (count($x) > 2 * $n_length) { | |
2111 | $lhs = new Math_BigInteger(); | |
2112 | $rhs = new Math_BigInteger(); | |
2113 | $lhs->value = $x; | |
2114 | $rhs->value = $n; | |
2115 | list(, $temp) = $lhs->divide($rhs); | |
2116 | return $temp->value; | |
2117 | } | |
2118 | ||
2119 | if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) { | |
2120 | $key = count($cache[MATH_BIGINTEGER_VARIABLE]); | |
2121 | $cache[MATH_BIGINTEGER_VARIABLE][] = $n; | |
2122 | $lhs = new Math_BigInteger(); | |
2123 | $lhs_value = &$lhs->value; | |
2124 | $lhs_value = $this->_array_repeat(0, 2 * $n_length); | |
2125 | $lhs_value[] = 1; | |
2126 | $rhs = new Math_BigInteger(); | |
2127 | $rhs->value = $n; | |
2128 | list($temp, ) = $lhs->divide($rhs); // m.length | |
2129 | $cache[MATH_BIGINTEGER_DATA][] = $temp->value; | |
2130 | } | |
2131 | ||
2132 | // 2 * m.length - (m.length - 1) = m.length + 1 | |
2133 | $temp = array_slice($x, $n_length - 1); | |
2134 | // (m.length + 1) + m.length = 2 * m.length + 1 | |
2135 | $temp = $this->_multiply($temp, false, $cache[MATH_BIGINTEGER_DATA][$key], false); | |
2136 | // (2 * m.length + 1) - (m.length - 1) = m.length + 2 | |
2137 | $temp = array_slice($temp[MATH_BIGINTEGER_VALUE], $n_length + 1); | |
2138 | ||
2139 | // m.length + 1 | |
2140 | $result = array_slice($x, 0, $n_length + 1); | |
2141 | // m.length + 1 | |
2142 | $temp = $this->_multiplyLower($temp, false, $n, false, $n_length + 1); | |
2143 | // $temp == array_slice($temp->_multiply($temp, false, $n, false)->value, 0, $n_length + 1) | |
2144 | ||
2145 | if ($this->_compare($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]) < 0) { | |
2146 | $corrector_value = $this->_array_repeat(0, $n_length + 1); | |
2147 | $corrector_value[count($corrector_value)] = 1; | |
2148 | $result = $this->_add($result, false, $corrector_value, false); | |
2149 | $result = $result[MATH_BIGINTEGER_VALUE]; | |
2150 | } | |
2151 | ||
2152 | // at this point, we're subtracting a number with m.length + 1 digits from another number with m.length + 1 digits | |
2153 | $result = $this->_subtract($result, false, $temp[MATH_BIGINTEGER_VALUE], $temp[MATH_BIGINTEGER_SIGN]); | |
2154 | while ($this->_compare($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false) > 0) { | |
2155 | $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], $result[MATH_BIGINTEGER_SIGN], $n, false); | |
2156 | } | |
2157 | ||
2158 | return $result[MATH_BIGINTEGER_VALUE]; | |
2159 | } | |
2160 | ||
2161 | /** | |
2162 | * Performs long multiplication up to $stop digits | |
2163 | * | |
2164 | * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved. | |
2165 | * | |
2166 | * @see _regularBarrett() | |
2167 | * @param Array $x_value | |
2168 | * @param Boolean $x_negative | |
2169 | * @param Array $y_value | |
2170 | * @param Boolean $y_negative | |
2171 | * @param Integer $stop | |
2172 | * @return Array | |
2173 | * @access private | |
2174 | */ | |
2175 | function _multiplyLower($x_value, $x_negative, $y_value, $y_negative, $stop) | |
2176 | { | |
2177 | $x_length = count($x_value); | |
2178 | $y_length = count($y_value); | |
2179 | ||
2180 | if ( !$x_length || !$y_length ) { // a 0 is being multiplied | |
2181 | return array( | |
2182 | MATH_BIGINTEGER_VALUE => array(), | |
2183 | MATH_BIGINTEGER_SIGN => false | |
2184 | ); | |
2185 | } | |
2186 | ||
2187 | if ( $x_length < $y_length ) { | |
2188 | $temp = $x_value; | |
2189 | $x_value = $y_value; | |
2190 | $y_value = $temp; | |
2191 | ||
2192 | $x_length = count($x_value); | |
2193 | $y_length = count($y_value); | |
2194 | } | |
2195 | ||
2196 | $product_value = $this->_array_repeat(0, $x_length + $y_length); | |
2197 | ||
2198 | // the following for loop could be removed if the for loop following it | |
2199 | // (the one with nested for loops) initially set $i to 0, but | |
2200 | // doing so would also make the result in one set of unnecessary adds, | |
2201 | // since on the outermost loops first pass, $product->value[$k] is going | |
2202 | // to always be 0 | |
2203 | ||
2204 | $carry = 0; | |
2205 | ||
2206 | for ($j = 0; $j < $x_length; ++$j) { // ie. $i = 0, $k = $i | |
2207 | $temp = $x_value[$j] * $y_value[0] + $carry; // $product_value[$k] == 0 | |
2208 | $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); | |
2209 | $product_value[$j] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry); | |
2210 | } | |
2211 | ||
2212 | if ($j < $stop) { | |
2213 | $product_value[$j] = $carry; | |
2214 | } | |
2215 | ||
2216 | // the above for loop is what the previous comment was talking about. the | |
2217 | // following for loop is the "one with nested for loops" | |
2218 | ||
2219 | for ($i = 1; $i < $y_length; ++$i) { | |
2220 | $carry = 0; | |
2221 | ||
2222 | for ($j = 0, $k = $i; $j < $x_length && $k < $stop; ++$j, ++$k) { | |
2223 | $temp = $product_value[$k] + $x_value[$j] * $y_value[$i] + $carry; | |
2224 | $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); | |
2225 | $product_value[$k] = (int) ($temp - MATH_BIGINTEGER_BASE_FULL * $carry); | |
2226 | } | |
2227 | ||
2228 | if ($k < $stop) { | |
2229 | $product_value[$k] = $carry; | |
2230 | } | |
2231 | } | |
2232 | ||
2233 | return array( | |
2234 | MATH_BIGINTEGER_VALUE => $this->_trim($product_value), | |
2235 | MATH_BIGINTEGER_SIGN => $x_negative != $y_negative | |
2236 | ); | |
2237 | } | |
2238 | ||
2239 | /** | |
2240 | * Montgomery Modular Reduction | |
2241 | * | |
2242 | * ($x->_prepMontgomery($n))->_montgomery($n) yields $x % $n. | |
2243 | * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be | |
2244 | * improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function | |
2245 | * to work correctly. | |
2246 | * | |
2247 | * @see _prepMontgomery() | |
2248 | * @see _slidingWindow() | |
2249 | * @access private | |
2250 | * @param Array $x | |
2251 | * @param Array $n | |
2252 | * @return Array | |
2253 | */ | |
2254 | function _montgomery($x, $n) | |
2255 | { | |
2256 | static $cache = array( | |
2257 | MATH_BIGINTEGER_VARIABLE => array(), | |
2258 | MATH_BIGINTEGER_DATA => array() | |
2259 | ); | |
2260 | ||
2261 | if ( ($key = array_search($n, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) { | |
2262 | $key = count($cache[MATH_BIGINTEGER_VARIABLE]); | |
2263 | $cache[MATH_BIGINTEGER_VARIABLE][] = $x; | |
2264 | $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($n); | |
2265 | } | |
2266 | ||
2267 | $k = count($n); | |
2268 | ||
2269 | $result = array(MATH_BIGINTEGER_VALUE => $x); | |
2270 | ||
2271 | for ($i = 0; $i < $k; ++$i) { | |
2272 | $temp = $result[MATH_BIGINTEGER_VALUE][$i] * $cache[MATH_BIGINTEGER_DATA][$key]; | |
2273 | $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); | |
2274 | $temp = $this->_regularMultiply(array($temp), $n); | |
2275 | $temp = array_merge($this->_array_repeat(0, $i), $temp); | |
2276 | $result = $this->_add($result[MATH_BIGINTEGER_VALUE], false, $temp, false); | |
2277 | } | |
2278 | ||
2279 | $result[MATH_BIGINTEGER_VALUE] = array_slice($result[MATH_BIGINTEGER_VALUE], $k); | |
2280 | ||
2281 | if ($this->_compare($result, false, $n, false) >= 0) { | |
2282 | $result = $this->_subtract($result[MATH_BIGINTEGER_VALUE], false, $n, false); | |
2283 | } | |
2284 | ||
2285 | return $result[MATH_BIGINTEGER_VALUE]; | |
2286 | } | |
2287 | ||
2288 | /** | |
2289 | * Montgomery Multiply | |
2290 | * | |
2291 | * Interleaves the montgomery reduction and long multiplication algorithms together as described in | |
2292 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=13 HAC 14.36} | |
2293 | * | |
2294 | * @see _prepMontgomery() | |
2295 | * @see _montgomery() | |
2296 | * @access private | |
2297 | * @param Array $x | |
2298 | * @param Array $y | |
2299 | * @param Array $m | |
2300 | * @return Array | |
2301 | */ | |
2302 | function _montgomeryMultiply($x, $y, $m) | |
2303 | { | |
2304 | $temp = $this->_multiply($x, false, $y, false); | |
2305 | return $this->_montgomery($temp[MATH_BIGINTEGER_VALUE], $m); | |
2306 | ||
2307 | // the following code, although not callable, can be run independently of the above code | |
2308 | // although the above code performed better in my benchmarks the following could might | |
2309 | // perform better under different circumstances. in lieu of deleting it it's just been | |
2310 | // made uncallable | |
2311 | ||
2312 | static $cache = array( | |
2313 | MATH_BIGINTEGER_VARIABLE => array(), | |
2314 | MATH_BIGINTEGER_DATA => array() | |
2315 | ); | |
2316 | ||
2317 | if ( ($key = array_search($m, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) { | |
2318 | $key = count($cache[MATH_BIGINTEGER_VARIABLE]); | |
2319 | $cache[MATH_BIGINTEGER_VARIABLE][] = $m; | |
2320 | $cache[MATH_BIGINTEGER_DATA][] = $this->_modInverse67108864($m); | |
2321 | } | |
2322 | ||
2323 | $n = max(count($x), count($y), count($m)); | |
2324 | $x = array_pad($x, $n, 0); | |
2325 | $y = array_pad($y, $n, 0); | |
2326 | $m = array_pad($m, $n, 0); | |
2327 | $a = array(MATH_BIGINTEGER_VALUE => $this->_array_repeat(0, $n + 1)); | |
2328 | for ($i = 0; $i < $n; ++$i) { | |
2329 | $temp = $a[MATH_BIGINTEGER_VALUE][0] + $x[$i] * $y[0]; | |
2330 | $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); | |
2331 | $temp = $temp * $cache[MATH_BIGINTEGER_DATA][$key]; | |
2332 | $temp = $temp - MATH_BIGINTEGER_BASE_FULL * (MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31)); | |
2333 | $temp = $this->_add($this->_regularMultiply(array($x[$i]), $y), false, $this->_regularMultiply(array($temp), $m), false); | |
2334 | $a = $this->_add($a[MATH_BIGINTEGER_VALUE], false, $temp[MATH_BIGINTEGER_VALUE], false); | |
2335 | $a[MATH_BIGINTEGER_VALUE] = array_slice($a[MATH_BIGINTEGER_VALUE], 1); | |
2336 | } | |
2337 | if ($this->_compare($a[MATH_BIGINTEGER_VALUE], false, $m, false) >= 0) { | |
2338 | $a = $this->_subtract($a[MATH_BIGINTEGER_VALUE], false, $m, false); | |
2339 | } | |
2340 | return $a[MATH_BIGINTEGER_VALUE]; | |
2341 | } | |
2342 | ||
2343 | /** | |
2344 | * Prepare a number for use in Montgomery Modular Reductions | |
2345 | * | |
2346 | * @see _montgomery() | |
2347 | * @see _slidingWindow() | |
2348 | * @access private | |
2349 | * @param Array $x | |
2350 | * @param Array $n | |
2351 | * @return Array | |
2352 | */ | |
2353 | function _prepMontgomery($x, $n) | |
2354 | { | |
2355 | $lhs = new Math_BigInteger(); | |
2356 | $lhs->value = array_merge($this->_array_repeat(0, count($n)), $x); | |
2357 | $rhs = new Math_BigInteger(); | |
2358 | $rhs->value = $n; | |
2359 | ||
2360 | list(, $temp) = $lhs->divide($rhs); | |
2361 | return $temp->value; | |
2362 | } | |
2363 | ||
2364 | /** | |
2365 | * Modular Inverse of a number mod 2**26 (eg. 67108864) | |
2366 | * | |
2367 | * Based off of the bnpInvDigit function implemented and justified in the following URL: | |
2368 | * | |
2369 | * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js} | |
2370 | * | |
2371 | * The following URL provides more info: | |
2372 | * | |
2373 | * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85} | |
2374 | * | |
2375 | * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For | |
2376 | * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields | |
2377 | * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't | |
2378 | * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that | |
2379 | * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the | |
2380 | * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to | |
2381 | * 40 bits, which only 64-bit floating points will support. | |
2382 | * | |
2383 | * Thanks to Pedro Gimeno Fortea for input! | |
2384 | * | |
2385 | * @see _montgomery() | |
2386 | * @access private | |
2387 | * @param Array $x | |
2388 | * @return Integer | |
2389 | */ | |
2390 | function _modInverse67108864($x) // 2**26 == 67,108,864 | |
2391 | { | |
2392 | $x = -$x[0]; | |
2393 | $result = $x & 0x3; // x**-1 mod 2**2 | |
2394 | $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4 | |
2395 | $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8 | |
2396 | $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16 | |
2397 | $result = fmod($result * (2 - fmod($x * $result, MATH_BIGINTEGER_BASE_FULL)), MATH_BIGINTEGER_BASE_FULL); // x**-1 mod 2**26 | |
2398 | return $result & MATH_BIGINTEGER_MAX_DIGIT; | |
2399 | } | |
2400 | ||
2401 | /** | |
2402 | * Calculates modular inverses. | |
2403 | * | |
2404 | * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses. | |
2405 | * | |
2406 | * Here's an example: | |
2407 | * <code> | |
2408 | * <?php | |
2409 | * include 'Math/BigInteger.php'; | |
2410 | * | |
2411 | * $a = new Math_BigInteger(30); | |
2412 | * $b = new Math_BigInteger(17); | |
2413 | * | |
2414 | * $c = $a->modInverse($b); | |
2415 | * echo $c->toString(); // outputs 4 | |
2416 | * | |
2417 | * echo "\r\n"; | |
2418 | * | |
2419 | * $d = $a->multiply($c); | |
2420 | * list(, $d) = $d->divide($b); | |
2421 | * echo $d; // outputs 1 (as per the definition of modular inverse) | |
2422 | * ?> | |
2423 | * </code> | |
2424 | * | |
2425 | * @param Math_BigInteger $n | |
2426 | * @return mixed false, if no modular inverse exists, Math_BigInteger, otherwise. | |
2427 | * @access public | |
2428 | * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information. | |
2429 | */ | |
2430 | function modInverse($n) | |
2431 | { | |
2432 | switch ( MATH_BIGINTEGER_MODE ) { | |
2433 | case MATH_BIGINTEGER_MODE_GMP: | |
2434 | $temp = new Math_BigInteger(); | |
2435 | $temp->value = gmp_invert($this->value, $n->value); | |
2436 | ||
2437 | return ( $temp->value === false ) ? false : $this->_normalize($temp); | |
2438 | } | |
2439 | ||
2440 | static $zero, $one; | |
2441 | if (!isset($zero)) { | |
2442 | $zero = new Math_BigInteger(); | |
2443 | $one = new Math_BigInteger(1); | |
2444 | } | |
2445 | ||
2446 | // $x mod -$n == $x mod $n. | |
2447 | $n = $n->abs(); | |
2448 | ||
2449 | if ($this->compare($zero) < 0) { | |
2450 | $temp = $this->abs(); | |
2451 | $temp = $temp->modInverse($n); | |
2452 | return $this->_normalize($n->subtract($temp)); | |
2453 | } | |
2454 | ||
2455 | extract($this->extendedGCD($n)); | |
2456 | ||
2457 | if (!$gcd->equals($one)) { | |
2458 | return false; | |
2459 | } | |
2460 | ||
2461 | $x = $x->compare($zero) < 0 ? $x->add($n) : $x; | |
2462 | ||
2463 | return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x); | |
2464 | } | |
2465 | ||
2466 | /** | |
2467 | * Calculates the greatest common divisor and Bezout's identity. | |
2468 | * | |
2469 | * Say you have 693 and 609. The GCD is 21. Bezout's identity states that there exist integers x and y such that | |
2470 | * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which | |
2471 | * combination is returned is dependant upon which mode is in use. See | |
2472 | * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bezout's identity - Wikipedia} for more information. | |
2473 | * | |
2474 | * Here's an example: | |
2475 | * <code> | |
2476 | * <?php | |
2477 | * include 'Math/BigInteger.php'; | |
2478 | * | |
2479 | * $a = new Math_BigInteger(693); | |
2480 | * $b = new Math_BigInteger(609); | |
2481 | * | |
2482 | * extract($a->extendedGCD($b)); | |
2483 | * | |
2484 | * echo $gcd->toString() . "\r\n"; // outputs 21 | |
2485 | * echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21 | |
2486 | * ?> | |
2487 | * </code> | |
2488 | * | |
2489 | * @param Math_BigInteger $n | |
2490 | * @return Math_BigInteger | |
2491 | * @access public | |
2492 | * @internal Calculates the GCD using the binary xGCD algorithim described in | |
2493 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}. As the text above 14.61 notes, | |
2494 | * the more traditional algorithim requires "relatively costly multiple-precision divisions". | |
2495 | */ | |
2496 | function extendedGCD($n) | |
2497 | { | |
2498 | switch ( MATH_BIGINTEGER_MODE ) { | |
2499 | case MATH_BIGINTEGER_MODE_GMP: | |
2500 | extract(gmp_gcdext($this->value, $n->value)); | |
2501 | ||
2502 | return array( | |
2503 | 'gcd' => $this->_normalize(new Math_BigInteger($g)), | |
2504 | 'x' => $this->_normalize(new Math_BigInteger($s)), | |
2505 | 'y' => $this->_normalize(new Math_BigInteger($t)) | |
2506 | ); | |
2507 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2508 | // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works | |
2509 | // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is, | |
2510 | // the basic extended euclidean algorithim is what we're using. | |
2511 | ||
2512 | $u = $this->value; | |
2513 | $v = $n->value; | |
2514 | ||
2515 | $a = '1'; | |
2516 | $b = '0'; | |
2517 | $c = '0'; | |
2518 | $d = '1'; | |
2519 | ||
2520 | while (bccomp($v, '0', 0) != 0) { | |
2521 | $q = bcdiv($u, $v, 0); | |
2522 | ||
2523 | $temp = $u; | |
2524 | $u = $v; | |
2525 | $v = bcsub($temp, bcmul($v, $q, 0), 0); | |
2526 | ||
2527 | $temp = $a; | |
2528 | $a = $c; | |
2529 | $c = bcsub($temp, bcmul($a, $q, 0), 0); | |
2530 | ||
2531 | $temp = $b; | |
2532 | $b = $d; | |
2533 | $d = bcsub($temp, bcmul($b, $q, 0), 0); | |
2534 | } | |
2535 | ||
2536 | return array( | |
2537 | 'gcd' => $this->_normalize(new Math_BigInteger($u)), | |
2538 | 'x' => $this->_normalize(new Math_BigInteger($a)), | |
2539 | 'y' => $this->_normalize(new Math_BigInteger($b)) | |
2540 | ); | |
2541 | } | |
2542 | ||
2543 | $y = $n->copy(); | |
2544 | $x = $this->copy(); | |
2545 | $g = new Math_BigInteger(); | |
2546 | $g->value = array(1); | |
2547 | ||
2548 | while ( !(($x->value[0] & 1)|| ($y->value[0] & 1)) ) { | |
2549 | $x->_rshift(1); | |
2550 | $y->_rshift(1); | |
2551 | $g->_lshift(1); | |
2552 | } | |
2553 | ||
2554 | $u = $x->copy(); | |
2555 | $v = $y->copy(); | |
2556 | ||
2557 | $a = new Math_BigInteger(); | |
2558 | $b = new Math_BigInteger(); | |
2559 | $c = new Math_BigInteger(); | |
2560 | $d = new Math_BigInteger(); | |
2561 | ||
2562 | $a->value = $d->value = $g->value = array(1); | |
2563 | $b->value = $c->value = array(); | |
2564 | ||
2565 | while ( !empty($u->value) ) { | |
2566 | while ( !($u->value[0] & 1) ) { | |
2567 | $u->_rshift(1); | |
2568 | if ( (!empty($a->value) && ($a->value[0] & 1)) || (!empty($b->value) && ($b->value[0] & 1)) ) { | |
2569 | $a = $a->add($y); | |
2570 | $b = $b->subtract($x); | |
2571 | } | |
2572 | $a->_rshift(1); | |
2573 | $b->_rshift(1); | |
2574 | } | |
2575 | ||
2576 | while ( !($v->value[0] & 1) ) { | |
2577 | $v->_rshift(1); | |
2578 | if ( (!empty($d->value) && ($d->value[0] & 1)) || (!empty($c->value) && ($c->value[0] & 1)) ) { | |
2579 | $c = $c->add($y); | |
2580 | $d = $d->subtract($x); | |
2581 | } | |
2582 | $c->_rshift(1); | |
2583 | $d->_rshift(1); | |
2584 | } | |
2585 | ||
2586 | if ($u->compare($v) >= 0) { | |
2587 | $u = $u->subtract($v); | |
2588 | $a = $a->subtract($c); | |
2589 | $b = $b->subtract($d); | |
2590 | } else { | |
2591 | $v = $v->subtract($u); | |
2592 | $c = $c->subtract($a); | |
2593 | $d = $d->subtract($b); | |
2594 | } | |
2595 | } | |
2596 | ||
2597 | return array( | |
2598 | 'gcd' => $this->_normalize($g->multiply($v)), | |
2599 | 'x' => $this->_normalize($c), | |
2600 | 'y' => $this->_normalize($d) | |
2601 | ); | |
2602 | } | |
2603 | ||
2604 | /** | |
2605 | * Calculates the greatest common divisor | |
2606 | * | |
2607 | * Say you have 693 and 609. The GCD is 21. | |
2608 | * | |
2609 | * Here's an example: | |
2610 | * <code> | |
2611 | * <?php | |
2612 | * include 'Math/BigInteger.php'; | |
2613 | * | |
2614 | * $a = new Math_BigInteger(693); | |
2615 | * $b = new Math_BigInteger(609); | |
2616 | * | |
2617 | * $gcd = a->extendedGCD($b); | |
2618 | * | |
2619 | * echo $gcd->toString() . "\r\n"; // outputs 21 | |
2620 | * ?> | |
2621 | * </code> | |
2622 | * | |
2623 | * @param Math_BigInteger $n | |
2624 | * @return Math_BigInteger | |
2625 | * @access public | |
2626 | */ | |
2627 | function gcd($n) | |
2628 | { | |
2629 | extract($this->extendedGCD($n)); | |
2630 | return $gcd; | |
2631 | } | |
2632 | ||
2633 | /** | |
2634 | * Absolute value. | |
2635 | * | |
2636 | * @return Math_BigInteger | |
2637 | * @access public | |
2638 | */ | |
2639 | function abs() | |
2640 | { | |
2641 | $temp = new Math_BigInteger(); | |
2642 | ||
2643 | switch ( MATH_BIGINTEGER_MODE ) { | |
2644 | case MATH_BIGINTEGER_MODE_GMP: | |
2645 | $temp->value = gmp_abs($this->value); | |
2646 | break; | |
2647 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2648 | $temp->value = (bccomp($this->value, '0', 0) < 0) ? substr($this->value, 1) : $this->value; | |
2649 | break; | |
2650 | default: | |
2651 | $temp->value = $this->value; | |
2652 | } | |
2653 | ||
2654 | return $temp; | |
2655 | } | |
2656 | ||
2657 | /** | |
2658 | * Compares two numbers. | |
2659 | * | |
2660 | * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is | |
2661 | * demonstrated thusly: | |
2662 | * | |
2663 | * $x > $y: $x->compare($y) > 0 | |
2664 | * $x < $y: $x->compare($y) < 0 | |
2665 | * $x == $y: $x->compare($y) == 0 | |
2666 | * | |
2667 | * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y). | |
2668 | * | |
2669 | * @param Math_BigInteger $y | |
2670 | * @return Integer < 0 if $this is less than $y; > 0 if $this is greater than $y, and 0 if they are equal. | |
2671 | * @access public | |
2672 | * @see equals() | |
2673 | * @internal Could return $this->subtract($x), but that's not as fast as what we do do. | |
2674 | */ | |
2675 | function compare($y) | |
2676 | { | |
2677 | switch ( MATH_BIGINTEGER_MODE ) { | |
2678 | case MATH_BIGINTEGER_MODE_GMP: | |
2679 | return gmp_cmp($this->value, $y->value); | |
2680 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2681 | return bccomp($this->value, $y->value, 0); | |
2682 | } | |
2683 | ||
2684 | return $this->_compare($this->value, $this->is_negative, $y->value, $y->is_negative); | |
2685 | } | |
2686 | ||
2687 | /** | |
2688 | * Compares two numbers. | |
2689 | * | |
2690 | * @param Array $x_value | |
2691 | * @param Boolean $x_negative | |
2692 | * @param Array $y_value | |
2693 | * @param Boolean $y_negative | |
2694 | * @return Integer | |
2695 | * @see compare() | |
2696 | * @access private | |
2697 | */ | |
2698 | function _compare($x_value, $x_negative, $y_value, $y_negative) | |
2699 | { | |
2700 | if ( $x_negative != $y_negative ) { | |
2701 | return ( !$x_negative && $y_negative ) ? 1 : -1; | |
2702 | } | |
2703 | ||
2704 | $result = $x_negative ? -1 : 1; | |
2705 | ||
2706 | if ( count($x_value) != count($y_value) ) { | |
2707 | return ( count($x_value) > count($y_value) ) ? $result : -$result; | |
2708 | } | |
2709 | $size = max(count($x_value), count($y_value)); | |
2710 | ||
2711 | $x_value = array_pad($x_value, $size, 0); | |
2712 | $y_value = array_pad($y_value, $size, 0); | |
2713 | ||
2714 | for ($i = count($x_value) - 1; $i >= 0; --$i) { | |
2715 | if ($x_value[$i] != $y_value[$i]) { | |
2716 | return ( $x_value[$i] > $y_value[$i] ) ? $result : -$result; | |
2717 | } | |
2718 | } | |
2719 | ||
2720 | return 0; | |
2721 | } | |
2722 | ||
2723 | /** | |
2724 | * Tests the equality of two numbers. | |
2725 | * | |
2726 | * If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare() | |
2727 | * | |
2728 | * @param Math_BigInteger $x | |
2729 | * @return Boolean | |
2730 | * @access public | |
2731 | * @see compare() | |
2732 | */ | |
2733 | function equals($x) | |
2734 | { | |
2735 | switch ( MATH_BIGINTEGER_MODE ) { | |
2736 | case MATH_BIGINTEGER_MODE_GMP: | |
2737 | return gmp_cmp($this->value, $x->value) == 0; | |
2738 | default: | |
2739 | return $this->value === $x->value && $this->is_negative == $x->is_negative; | |
2740 | } | |
2741 | } | |
2742 | ||
2743 | /** | |
2744 | * Set Precision | |
2745 | * | |
2746 | * Some bitwise operations give different results depending on the precision being used. Examples include left | |
2747 | * shift, not, and rotates. | |
2748 | * | |
2749 | * @param Integer $bits | |
2750 | * @access public | |
2751 | */ | |
2752 | function setPrecision($bits) | |
2753 | { | |
2754 | $this->precision = $bits; | |
2755 | if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ) { | |
2756 | $this->bitmask = new Math_BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256); | |
2757 | } else { | |
2758 | $this->bitmask = new Math_BigInteger(bcpow('2', $bits, 0)); | |
2759 | } | |
2760 | ||
2761 | $temp = $this->_normalize($this); | |
2762 | $this->value = $temp->value; | |
2763 | } | |
2764 | ||
2765 | /** | |
2766 | * Logical And | |
2767 | * | |
2768 | * @param Math_BigInteger $x | |
2769 | * @access public | |
2770 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> | |
2771 | * @return Math_BigInteger | |
2772 | */ | |
2773 | function bitwise_and($x) | |
2774 | { | |
2775 | switch ( MATH_BIGINTEGER_MODE ) { | |
2776 | case MATH_BIGINTEGER_MODE_GMP: | |
2777 | $temp = new Math_BigInteger(); | |
2778 | $temp->value = gmp_and($this->value, $x->value); | |
2779 | ||
2780 | return $this->_normalize($temp); | |
2781 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2782 | $left = $this->toBytes(); | |
2783 | $right = $x->toBytes(); | |
2784 | ||
2785 | $length = max(strlen($left), strlen($right)); | |
2786 | ||
2787 | $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); | |
2788 | $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); | |
2789 | ||
2790 | return $this->_normalize(new Math_BigInteger($left & $right, 256)); | |
2791 | } | |
2792 | ||
2793 | $result = $this->copy(); | |
2794 | ||
2795 | $length = min(count($x->value), count($this->value)); | |
2796 | ||
2797 | $result->value = array_slice($result->value, 0, $length); | |
2798 | ||
2799 | for ($i = 0; $i < $length; ++$i) { | |
2800 | $result->value[$i]&= $x->value[$i]; | |
2801 | } | |
2802 | ||
2803 | return $this->_normalize($result); | |
2804 | } | |
2805 | ||
2806 | /** | |
2807 | * Logical Or | |
2808 | * | |
2809 | * @param Math_BigInteger $x | |
2810 | * @access public | |
2811 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> | |
2812 | * @return Math_BigInteger | |
2813 | */ | |
2814 | function bitwise_or($x) | |
2815 | { | |
2816 | switch ( MATH_BIGINTEGER_MODE ) { | |
2817 | case MATH_BIGINTEGER_MODE_GMP: | |
2818 | $temp = new Math_BigInteger(); | |
2819 | $temp->value = gmp_or($this->value, $x->value); | |
2820 | ||
2821 | return $this->_normalize($temp); | |
2822 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2823 | $left = $this->toBytes(); | |
2824 | $right = $x->toBytes(); | |
2825 | ||
2826 | $length = max(strlen($left), strlen($right)); | |
2827 | ||
2828 | $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); | |
2829 | $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); | |
2830 | ||
2831 | return $this->_normalize(new Math_BigInteger($left | $right, 256)); | |
2832 | } | |
2833 | ||
2834 | $length = max(count($this->value), count($x->value)); | |
2835 | $result = $this->copy(); | |
2836 | $result->value = array_pad($result->value, $length, 0); | |
2837 | $x->value = array_pad($x->value, $length, 0); | |
2838 | ||
2839 | for ($i = 0; $i < $length; ++$i) { | |
2840 | $result->value[$i]|= $x->value[$i]; | |
2841 | } | |
2842 | ||
2843 | return $this->_normalize($result); | |
2844 | } | |
2845 | ||
2846 | /** | |
2847 | * Logical Exclusive-Or | |
2848 | * | |
2849 | * @param Math_BigInteger $x | |
2850 | * @access public | |
2851 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> | |
2852 | * @return Math_BigInteger | |
2853 | */ | |
2854 | function bitwise_xor($x) | |
2855 | { | |
2856 | switch ( MATH_BIGINTEGER_MODE ) { | |
2857 | case MATH_BIGINTEGER_MODE_GMP: | |
2858 | $temp = new Math_BigInteger(); | |
2859 | $temp->value = gmp_xor($this->value, $x->value); | |
2860 | ||
2861 | return $this->_normalize($temp); | |
2862 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2863 | $left = $this->toBytes(); | |
2864 | $right = $x->toBytes(); | |
2865 | ||
2866 | $length = max(strlen($left), strlen($right)); | |
2867 | ||
2868 | $left = str_pad($left, $length, chr(0), STR_PAD_LEFT); | |
2869 | $right = str_pad($right, $length, chr(0), STR_PAD_LEFT); | |
2870 | ||
2871 | return $this->_normalize(new Math_BigInteger($left ^ $right, 256)); | |
2872 | } | |
2873 | ||
2874 | $length = max(count($this->value), count($x->value)); | |
2875 | $result = $this->copy(); | |
2876 | $result->value = array_pad($result->value, $length, 0); | |
2877 | $x->value = array_pad($x->value, $length, 0); | |
2878 | ||
2879 | for ($i = 0; $i < $length; ++$i) { | |
2880 | $result->value[$i]^= $x->value[$i]; | |
2881 | } | |
2882 | ||
2883 | return $this->_normalize($result); | |
2884 | } | |
2885 | ||
2886 | /** | |
2887 | * Logical Not | |
2888 | * | |
2889 | * @access public | |
2890 | * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat> | |
2891 | * @return Math_BigInteger | |
2892 | */ | |
2893 | function bitwise_not() | |
2894 | { | |
2895 | // calculuate "not" without regard to $this->precision | |
2896 | // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0) | |
2897 | $temp = $this->toBytes(); | |
2898 | $pre_msb = decbin(ord($temp[0])); | |
2899 | $temp = ~$temp; | |
2900 | $msb = decbin(ord($temp[0])); | |
2901 | if (strlen($msb) == 8) { | |
2902 | $msb = substr($msb, strpos($msb, '0')); | |
2903 | } | |
2904 | $temp[0] = chr(bindec($msb)); | |
2905 | ||
2906 | // see if we need to add extra leading 1's | |
2907 | $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8; | |
2908 | $new_bits = $this->precision - $current_bits; | |
2909 | if ($new_bits <= 0) { | |
2910 | return $this->_normalize(new Math_BigInteger($temp, 256)); | |
2911 | } | |
2912 | ||
2913 | // generate as many leading 1's as we need to. | |
2914 | $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3); | |
2915 | $this->_base256_lshift($leading_ones, $current_bits); | |
2916 | ||
2917 | $temp = str_pad($temp, strlen($leading_ones), chr(0), STR_PAD_LEFT); | |
2918 | ||
2919 | return $this->_normalize(new Math_BigInteger($leading_ones | $temp, 256)); | |
2920 | } | |
2921 | ||
2922 | /** | |
2923 | * Logical Right Shift | |
2924 | * | |
2925 | * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift. | |
2926 | * | |
2927 | * @param Integer $shift | |
2928 | * @return Math_BigInteger | |
2929 | * @access public | |
2930 | * @internal The only version that yields any speed increases is the internal version. | |
2931 | */ | |
2932 | function bitwise_rightShift($shift) | |
2933 | { | |
2934 | $temp = new Math_BigInteger(); | |
2935 | ||
2936 | switch ( MATH_BIGINTEGER_MODE ) { | |
2937 | case MATH_BIGINTEGER_MODE_GMP: | |
2938 | static $two; | |
2939 | ||
2940 | if (!isset($two)) { | |
2941 | $two = gmp_init('2'); | |
2942 | } | |
2943 | ||
2944 | $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift)); | |
2945 | ||
2946 | break; | |
2947 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2948 | $temp->value = bcdiv($this->value, bcpow('2', $shift, 0), 0); | |
2949 | ||
2950 | break; | |
2951 | default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten | |
2952 | // and I don't want to do that... | |
2953 | $temp->value = $this->value; | |
2954 | $temp->_rshift($shift); | |
2955 | } | |
2956 | ||
2957 | return $this->_normalize($temp); | |
2958 | } | |
2959 | ||
2960 | /** | |
2961 | * Logical Left Shift | |
2962 | * | |
2963 | * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift. | |
2964 | * | |
2965 | * @param Integer $shift | |
2966 | * @return Math_BigInteger | |
2967 | * @access public | |
2968 | * @internal The only version that yields any speed increases is the internal version. | |
2969 | */ | |
2970 | function bitwise_leftShift($shift) | |
2971 | { | |
2972 | $temp = new Math_BigInteger(); | |
2973 | ||
2974 | switch ( MATH_BIGINTEGER_MODE ) { | |
2975 | case MATH_BIGINTEGER_MODE_GMP: | |
2976 | static $two; | |
2977 | ||
2978 | if (!isset($two)) { | |
2979 | $two = gmp_init('2'); | |
2980 | } | |
2981 | ||
2982 | $temp->value = gmp_mul($this->value, gmp_pow($two, $shift)); | |
2983 | ||
2984 | break; | |
2985 | case MATH_BIGINTEGER_MODE_BCMATH: | |
2986 | $temp->value = bcmul($this->value, bcpow('2', $shift, 0), 0); | |
2987 | ||
2988 | break; | |
2989 | default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten | |
2990 | // and I don't want to do that... | |
2991 | $temp->value = $this->value; | |
2992 | $temp->_lshift($shift); | |
2993 | } | |
2994 | ||
2995 | return $this->_normalize($temp); | |
2996 | } | |
2997 | ||
2998 | /** | |
2999 | * Logical Left Rotate | |
3000 | * | |
3001 | * Instead of the top x bits being dropped they're appended to the shifted bit string. | |
3002 | * | |
3003 | * @param Integer $shift | |
3004 | * @return Math_BigInteger | |
3005 | * @access public | |
3006 | */ | |
3007 | function bitwise_leftRotate($shift) | |
3008 | { | |
3009 | $bits = $this->toBytes(); | |
3010 | ||
3011 | if ($this->precision > 0) { | |
3012 | $precision = $this->precision; | |
3013 | if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) { | |
3014 | $mask = $this->bitmask->subtract(new Math_BigInteger(1)); | |
3015 | $mask = $mask->toBytes(); | |
3016 | } else { | |
3017 | $mask = $this->bitmask->toBytes(); | |
3018 | } | |
3019 | } else { | |
3020 | $temp = ord($bits[0]); | |
3021 | for ($i = 0; $temp >> $i; ++$i); | |
3022 | $precision = 8 * strlen($bits) - 8 + $i; | |
3023 | $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3); | |
3024 | } | |
3025 | ||
3026 | if ($shift < 0) { | |
3027 | $shift+= $precision; | |
3028 | } | |
3029 | $shift%= $precision; | |
3030 | ||
3031 | if (!$shift) { | |
3032 | return $this->copy(); | |
3033 | } | |
3034 | ||
3035 | $left = $this->bitwise_leftShift($shift); | |
3036 | $left = $left->bitwise_and(new Math_BigInteger($mask, 256)); | |
3037 | $right = $this->bitwise_rightShift($precision - $shift); | |
3038 | $result = MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right); | |
3039 | return $this->_normalize($result); | |
3040 | } | |
3041 | ||
3042 | /** | |
3043 | * Logical Right Rotate | |
3044 | * | |
3045 | * Instead of the bottom x bits being dropped they're prepended to the shifted bit string. | |
3046 | * | |
3047 | * @param Integer $shift | |
3048 | * @return Math_BigInteger | |
3049 | * @access public | |
3050 | */ | |
3051 | function bitwise_rightRotate($shift) | |
3052 | { | |
3053 | return $this->bitwise_leftRotate(-$shift); | |
3054 | } | |
3055 | ||
3056 | /** | |
3057 | * Set random number generator function | |
3058 | * | |
3059 | * This function is deprecated. | |
3060 | * | |
3061 | * @param String $generator | |
3062 | * @access public | |
3063 | */ | |
3064 | function setRandomGenerator($generator) | |
3065 | { | |
3066 | } | |
3067 | ||
3068 | /** | |
3069 | * Generates a random BigInteger | |
3070 | * | |
3071 | * Byte length is equal to $length. Uses crypt_random if it's loaded and mt_rand if it's not. | |
3072 | * | |
3073 | * @param Integer $length | |
3074 | * @return Math_BigInteger | |
3075 | * @access private | |
3076 | */ | |
3077 | function _random_number_helper($size) | |
3078 | { | |
3079 | if (function_exists('crypt_random_string')) { | |
3080 | $random = crypt_random_string($size); | |
3081 | } else { | |
3082 | $random = ''; | |
3083 | ||
3084 | if ($size & 1) { | |
3085 | $random.= chr(mt_rand(0, 255)); | |
3086 | } | |
3087 | ||
3088 | $blocks = $size >> 1; | |
3089 | for ($i = 0; $i < $blocks; ++$i) { | |
3090 | // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems | |
3091 | $random.= pack('n', mt_rand(0, 0xFFFF)); | |
3092 | } | |
3093 | } | |
3094 | ||
3095 | return new Math_BigInteger($random, 256); | |
3096 | } | |
3097 | ||
3098 | /** | |
3099 | * Generate a random number | |
3100 | * | |
3101 | * Returns a random number between $min and $max where $min and $max | |
3102 | * can be defined using one of the two methods: | |
3103 | * | |
3104 | * $min->random($max) | |
3105 | * $max->random($min) | |
3106 | * | |
3107 | * @param Math_BigInteger $arg1 | |
3108 | * @param optional Math_BigInteger $arg2 | |
3109 | * @return Math_BigInteger | |
3110 | * @access public | |
3111 | * @internal The API for creating random numbers used to be $a->random($min, $max), where $a was a Math_BigInteger object. | |
3112 | * That method is still supported for BC purposes. | |
3113 | */ | |
3114 | function random($arg1, $arg2 = false) | |
3115 | { | |
3116 | if ($arg1 === false) { | |
3117 | return false; | |
3118 | } | |
3119 | ||
3120 | if ($arg2 === false) { | |
3121 | $max = $arg1; | |
3122 | $min = $this; | |
3123 | } else { | |
3124 | $min = $arg1; | |
3125 | $max = $arg2; | |
3126 | } | |
3127 | ||
3128 | $compare = $max->compare($min); | |
3129 | ||
3130 | if (!$compare) { | |
3131 | return $this->_normalize($min); | |
3132 | } else if ($compare < 0) { | |
3133 | // if $min is bigger then $max, swap $min and $max | |
3134 | $temp = $max; | |
3135 | $max = $min; | |
3136 | $min = $temp; | |
3137 | } | |
3138 | ||
3139 | static $one; | |
3140 | if (!isset($one)) { | |
3141 | $one = new Math_BigInteger(1); | |
3142 | } | |
3143 | ||
3144 | $max = $max->subtract($min->subtract($one)); | |
3145 | $size = strlen(ltrim($max->toBytes(), chr(0))); | |
3146 | ||
3147 | /* | |
3148 | doing $random % $max doesn't work because some numbers will be more likely to occur than others. | |
3149 | eg. if $max is 140 and $random's max is 255 then that'd mean both $random = 5 and $random = 145 | |
3150 | would produce 5 whereas the only value of random that could produce 139 would be 139. ie. | |
3151 | not all numbers would be equally likely. some would be more likely than others. | |
3152 | ||
3153 | creating a whole new random number until you find one that is within the range doesn't work | |
3154 | because, for sufficiently small ranges, the likelihood that you'd get a number within that range | |
3155 | would be pretty small. eg. with $random's max being 255 and if your $max being 1 the probability | |
3156 | would be pretty high that $random would be greater than $max. | |
3157 | ||
3158 | phpseclib works around this using the technique described here: | |
3159 | ||
3160 | http://crypto.stackexchange.com/questions/5708/creating-a-small-number-from-a-cryptographically-secure-random-string | |
3161 | */ | |
3162 | $random_max = new Math_BigInteger(chr(1) . str_repeat("\0", $size), 256); | |
3163 | $random = $this->_random_number_helper($size); | |
3164 | ||
3165 | list($max_multiple) = $random_max->divide($max); | |
3166 | $max_multiple = $max_multiple->multiply($max); | |
3167 | ||
3168 | while ($random->compare($max_multiple) >= 0) { | |
3169 | $random = $random->subtract($max_multiple); | |
3170 | $random_max = $random_max->subtract($max_multiple); | |
3171 | $random = $random->bitwise_leftShift(8); | |
3172 | $random = $random->add($this->_random_number_helper(1)); | |
3173 | $random_max = $random_max->bitwise_leftShift(8); | |
3174 | list($max_multiple) = $random_max->divide($max); | |
3175 | $max_multiple = $max_multiple->multiply($max); | |
3176 | } | |
3177 | list(, $random) = $random->divide($max); | |
3178 | ||
3179 | return $this->_normalize($random->add($min)); | |
3180 | } | |
3181 | ||
3182 | /** | |
3183 | * Generate a random prime number. | |
3184 | * | |
3185 | * If there's not a prime within the given range, false will be returned. If more than $timeout seconds have elapsed, | |
3186 | * give up and return false. | |
3187 | * | |
3188 | * @param Math_BigInteger $arg1 | |
3189 | * @param optional Math_BigInteger $arg2 | |
3190 | * @param optional Integer $timeout | |
3191 | * @return Mixed | |
3192 | * @access public | |
3193 | * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}. | |
3194 | */ | |
3195 | function randomPrime($arg1, $arg2 = false, $timeout = false) | |
3196 | { | |
3197 | if ($arg1 === false) { | |
3198 | return false; | |
3199 | } | |
3200 | ||
3201 | if ($arg2 === false) { | |
3202 | $max = $arg1; | |
3203 | $min = $this; | |
3204 | } else { | |
3205 | $min = $arg1; | |
3206 | $max = $arg2; | |
3207 | } | |
3208 | ||
3209 | $compare = $max->compare($min); | |
3210 | ||
3211 | if (!$compare) { | |
3212 | return $min->isPrime() ? $min : false; | |
3213 | } else if ($compare < 0) { | |
3214 | // if $min is bigger then $max, swap $min and $max | |
3215 | $temp = $max; | |
3216 | $max = $min; | |
3217 | $min = $temp; | |
3218 | } | |
3219 | ||
3220 | static $one, $two; | |
3221 | if (!isset($one)) { | |
3222 | $one = new Math_BigInteger(1); | |
3223 | $two = new Math_BigInteger(2); | |
3224 | } | |
3225 | ||
3226 | $start = time(); | |
3227 | ||
3228 | $x = $this->random($min, $max); | |
3229 | ||
3230 | // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>. | |
3231 | if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && function_exists('gmp_nextprime') ) { | |
3232 | $p = new Math_BigInteger(); | |
3233 | $p->value = gmp_nextprime($x->value); | |
3234 | ||
3235 | if ($p->compare($max) <= 0) { | |
3236 | return $p; | |
3237 | } | |
3238 | ||
3239 | if (!$min->equals($x)) { | |
3240 | $x = $x->subtract($one); | |
3241 | } | |
3242 | ||
3243 | return $x->randomPrime($min, $x); | |
3244 | } | |
3245 | ||
3246 | if ($x->equals($two)) { | |
3247 | return $x; | |
3248 | } | |
3249 | ||
3250 | $x->_make_odd(); | |
3251 | if ($x->compare($max) > 0) { | |
3252 | // if $x > $max then $max is even and if $min == $max then no prime number exists between the specified range | |
3253 | if ($min->equals($max)) { | |
3254 | return false; | |
3255 | } | |
3256 | $x = $min->copy(); | |
3257 | $x->_make_odd(); | |
3258 | } | |
3259 | ||
3260 | $initial_x = $x->copy(); | |
3261 | ||
3262 | while (true) { | |
3263 | if ($timeout !== false && time() - $start > $timeout) { | |
3264 | return false; | |
3265 | } | |
3266 | ||
3267 | if ($x->isPrime()) { | |
3268 | return $x; | |
3269 | } | |
3270 | ||
3271 | $x = $x->add($two); | |
3272 | ||
3273 | if ($x->compare($max) > 0) { | |
3274 | $x = $min->copy(); | |
3275 | if ($x->equals($two)) { | |
3276 | return $x; | |
3277 | } | |
3278 | $x->_make_odd(); | |
3279 | } | |
3280 | ||
3281 | if ($x->equals($initial_x)) { | |
3282 | return false; | |
3283 | } | |
3284 | } | |
3285 | } | |
3286 | ||
3287 | /** | |
3288 | * Make the current number odd | |
3289 | * | |
3290 | * If the current number is odd it'll be unchanged. If it's even, one will be added to it. | |
3291 | * | |
3292 | * @see randomPrime() | |
3293 | * @access private | |
3294 | */ | |
3295 | function _make_odd() | |
3296 | { | |
3297 | switch ( MATH_BIGINTEGER_MODE ) { | |
3298 | case MATH_BIGINTEGER_MODE_GMP: | |
3299 | gmp_setbit($this->value, 0); | |
3300 | break; | |
3301 | case MATH_BIGINTEGER_MODE_BCMATH: | |
3302 | if ($this->value[strlen($this->value) - 1] % 2 == 0) { | |
3303 | $this->value = bcadd($this->value, '1'); | |
3304 | } | |
3305 | break; | |
3306 | default: | |
3307 | $this->value[0] |= 1; | |
3308 | } | |
3309 | } | |
3310 | ||
3311 | /** | |
3312 | * Checks a numer to see if it's prime | |
3313 | * | |
3314 | * Assuming the $t parameter is not set, this function has an error rate of 2**-80. The main motivation for the | |
3315 | * $t parameter is distributability. Math_BigInteger::randomPrime() can be distributed across multiple pageloads | |
3316 | * on a website instead of just one. | |
3317 | * | |
3318 | * @param optional Math_BigInteger $t | |
3319 | * @return Boolean | |
3320 | * @access public | |
3321 | * @internal Uses the | |
3322 | * {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller-Rabin primality test}. See | |
3323 | * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}. | |
3324 | */ | |
3325 | function isPrime($t = false) | |
3326 | { | |
3327 | $length = strlen($this->toBytes()); | |
3328 | ||
3329 | if (!$t) { | |
3330 | // see HAC 4.49 "Note (controlling the error probability)" | |
3331 | // @codingStandardsIgnoreStart | |
3332 | if ($length >= 163) { $t = 2; } // floor(1300 / 8) | |
3333 | else if ($length >= 106) { $t = 3; } // floor( 850 / 8) | |
3334 | else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8) | |
3335 | else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8) | |
3336 | else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8) | |
3337 | else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8) | |
3338 | else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8) | |
3339 | else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8) | |
3340 | else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8) | |
3341 | else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8) | |
3342 | else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8) | |
3343 | else { $t = 27; } | |
3344 | // @codingStandardsIgnoreEnd | |
3345 | } | |
3346 | ||
3347 | // ie. gmp_testbit($this, 0) | |
3348 | // ie. isEven() or !isOdd() | |
3349 | switch ( MATH_BIGINTEGER_MODE ) { | |
3350 | case MATH_BIGINTEGER_MODE_GMP: | |
3351 | return gmp_prob_prime($this->value, $t) != 0; | |
3352 | case MATH_BIGINTEGER_MODE_BCMATH: | |
3353 | if ($this->value === '2') { | |
3354 | return true; | |
3355 | } | |
3356 | if ($this->value[strlen($this->value) - 1] % 2 == 0) { | |
3357 | return false; | |
3358 | } | |
3359 | break; | |
3360 | default: | |
3361 | if ($this->value == array(2)) { | |
3362 | return true; | |
3363 | } | |
3364 | if (~$this->value[0] & 1) { | |
3365 | return false; | |
3366 | } | |
3367 | } | |
3368 | ||
3369 | static $primes, $zero, $one, $two; | |
3370 | ||
3371 | if (!isset($primes)) { | |
3372 | $primes = array( | |
3373 | 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, | |
3374 | 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, | |
3375 | 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, | |
3376 | 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, | |
3377 | 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, | |
3378 | 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, | |
3379 | 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, | |
3380 | 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, | |
3381 | 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, | |
3382 | 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, | |
3383 | 953, 967, 971, 977, 983, 991, 997 | |
3384 | ); | |
3385 | ||
3386 | if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) { | |
3387 | for ($i = 0; $i < count($primes); ++$i) { | |
3388 | $primes[$i] = new Math_BigInteger($primes[$i]); | |
3389 | } | |
3390 | } | |
3391 | ||
3392 | $zero = new Math_BigInteger(); | |
3393 | $one = new Math_BigInteger(1); | |
3394 | $two = new Math_BigInteger(2); | |
3395 | } | |
3396 | ||
3397 | if ($this->equals($one)) { | |
3398 | return false; | |
3399 | } | |
3400 | ||
3401 | // see HAC 4.4.1 "Random search for probable primes" | |
3402 | if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL ) { | |
3403 | foreach ($primes as $prime) { | |
3404 | list(, $r) = $this->divide($prime); | |
3405 | if ($r->equals($zero)) { | |
3406 | return $this->equals($prime); | |
3407 | } | |
3408 | } | |
3409 | } else { | |
3410 | $value = $this->value; | |
3411 | foreach ($primes as $prime) { | |
3412 | list(, $r) = $this->_divide_digit($value, $prime); | |
3413 | if (!$r) { | |
3414 | return count($value) == 1 && $value[0] == $prime; | |
3415 | } | |
3416 | } | |
3417 | } | |
3418 | ||
3419 | $n = $this->copy(); | |
3420 | $n_1 = $n->subtract($one); | |
3421 | $n_2 = $n->subtract($two); | |
3422 | ||
3423 | $r = $n_1->copy(); | |
3424 | $r_value = $r->value; | |
3425 | // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s)); | |
3426 | if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) { | |
3427 | $s = 0; | |
3428 | // if $n was 1, $r would be 0 and this would be an infinite loop, hence our $this->equals($one) check earlier | |
3429 | while ($r->value[strlen($r->value) - 1] % 2 == 0) { | |
3430 | $r->value = bcdiv($r->value, '2', 0); | |
3431 | ++$s; | |
3432 | } | |
3433 | } else { | |
3434 | for ($i = 0, $r_length = count($r_value); $i < $r_length; ++$i) { | |
3435 | $temp = ~$r_value[$i] & 0xFFFFFF; | |
3436 | for ($j = 1; ($temp >> $j) & 1; ++$j); | |
3437 | if ($j != 25) { | |
3438 | break; | |
3439 | } | |
3440 | } | |
3441 | $s = 26 * $i + $j - 1; | |
3442 | $r->_rshift($s); | |
3443 | } | |
3444 | ||
3445 | for ($i = 0; $i < $t; ++$i) { | |
3446 | $a = $this->random($two, $n_2); | |
3447 | $y = $a->modPow($r, $n); | |
3448 | ||
3449 | if (!$y->equals($one) && !$y->equals($n_1)) { | |
3450 | for ($j = 1; $j < $s && !$y->equals($n_1); ++$j) { | |
3451 | $y = $y->modPow($two, $n); | |
3452 | if ($y->equals($one)) { | |
3453 | return false; | |
3454 | } | |
3455 | } | |
3456 | ||
3457 | if (!$y->equals($n_1)) { | |
3458 | return false; | |
3459 | } | |
3460 | } | |
3461 | } | |
3462 | return true; | |
3463 | } | |
3464 | ||
3465 | /** | |
3466 | * Logical Left Shift | |
3467 | * | |
3468 | * Shifts BigInteger's by $shift bits. | |
3469 | * | |
3470 | * @param Integer $shift | |
3471 | * @access private | |
3472 | */ | |
3473 | function _lshift($shift) | |
3474 | { | |
3475 | if ( $shift == 0 ) { | |
3476 | return; | |
3477 | } | |
3478 | ||
3479 | $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE); | |
3480 | $shift %= MATH_BIGINTEGER_BASE; | |
3481 | $shift = 1 << $shift; | |
3482 | ||
3483 | $carry = 0; | |
3484 | ||
3485 | for ($i = 0; $i < count($this->value); ++$i) { | |
3486 | $temp = $this->value[$i] * $shift + $carry; | |
3487 | $carry = MATH_BIGINTEGER_BASE === 26 ? intval($temp / 0x4000000) : ($temp >> 31); | |
3488 | $this->value[$i] = (int) ($temp - $carry * MATH_BIGINTEGER_BASE_FULL); | |
3489 | } | |
3490 | ||
3491 | if ( $carry ) { | |
3492 | $this->value[count($this->value)] = $carry; | |
3493 | } | |
3494 | ||
3495 | while ($num_digits--) { | |
3496 | array_unshift($this->value, 0); | |
3497 | } | |
3498 | } | |
3499 | ||
3500 | /** | |
3501 | * Logical Right Shift | |
3502 | * | |
3503 | * Shifts BigInteger's by $shift bits. | |
3504 | * | |
3505 | * @param Integer $shift | |
3506 | * @access private | |
3507 | */ | |
3508 | function _rshift($shift) | |
3509 | { | |
3510 | if ($shift == 0) { | |
3511 | return; | |
3512 | } | |
3513 | ||
3514 | $num_digits = (int) ($shift / MATH_BIGINTEGER_BASE); | |
3515 | $shift %= MATH_BIGINTEGER_BASE; | |
3516 | $carry_shift = MATH_BIGINTEGER_BASE - $shift; | |
3517 | $carry_mask = (1 << $shift) - 1; | |
3518 | ||
3519 | if ( $num_digits ) { | |
3520 | $this->value = array_slice($this->value, $num_digits); | |
3521 | } | |
3522 | ||
3523 | $carry = 0; | |
3524 | ||
3525 | for ($i = count($this->value) - 1; $i >= 0; --$i) { | |
3526 | $temp = $this->value[$i] >> $shift | $carry; | |
3527 | $carry = ($this->value[$i] & $carry_mask) << $carry_shift; | |
3528 | $this->value[$i] = $temp; | |
3529 | } | |
3530 | ||
3531 | $this->value = $this->_trim($this->value); | |
3532 | } | |
3533 | ||
3534 | /** | |
3535 | * Normalize | |
3536 | * | |
3537 | * Removes leading zeros and truncates (if necessary) to maintain the appropriate precision | |
3538 | * | |
3539 | * @param Math_BigInteger | |
3540 | * @return Math_BigInteger | |
3541 | * @see _trim() | |
3542 | * @access private | |
3543 | */ | |
3544 | function _normalize($result) | |
3545 | { | |
3546 | $result->precision = $this->precision; | |
3547 | $result->bitmask = $this->bitmask; | |
3548 | ||
3549 | switch ( MATH_BIGINTEGER_MODE ) { | |
3550 | case MATH_BIGINTEGER_MODE_GMP: | |
3551 | if (!empty($result->bitmask->value)) { | |
3552 | $result->value = gmp_and($result->value, $result->bitmask->value); | |
3553 | } | |
3554 | ||
3555 | return $result; | |
3556 | case MATH_BIGINTEGER_MODE_BCMATH: | |
3557 | if (!empty($result->bitmask->value)) { | |
3558 | $result->value = bcmod($result->value, $result->bitmask->value); | |
3559 | } | |
3560 | ||
3561 | return $result; | |
3562 | } | |
3563 | ||
3564 | $value = &$result->value; | |
3565 | ||
3566 | if ( !count($value) ) { | |
3567 | return $result; | |
3568 | } | |
3569 | ||
3570 | $value = $this->_trim($value); | |
3571 | ||
3572 | if (!empty($result->bitmask->value)) { | |
3573 | $length = min(count($value), count($this->bitmask->value)); | |
3574 | $value = array_slice($value, 0, $length); | |
3575 | ||
3576 | for ($i = 0; $i < $length; ++$i) { | |
3577 | $value[$i] = $value[$i] & $this->bitmask->value[$i]; | |
3578 | } | |
3579 | } | |
3580 | ||
3581 | return $result; | |
3582 | } | |
3583 | ||
3584 | /** | |
3585 | * Trim | |
3586 | * | |
3587 | * Removes leading zeros | |
3588 | * | |
3589 | * @param Array $value | |
3590 | * @return Math_BigInteger | |
3591 | * @access private | |
3592 | */ | |
3593 | function _trim($value) | |
3594 | { | |
3595 | for ($i = count($value) - 1; $i >= 0; --$i) { | |
3596 | if ( $value[$i] ) { | |
3597 | break; | |
3598 | } | |
3599 | unset($value[$i]); | |
3600 | } | |
3601 | ||
3602 | return $value; | |
3603 | } | |
3604 | ||
3605 | /** | |
3606 | * Array Repeat | |
3607 | * | |
3608 | * @param $input Array | |
3609 | * @param $multiplier mixed | |
3610 | * @return Array | |
3611 | * @access private | |
3612 | */ | |
3613 | function _array_repeat($input, $multiplier) | |
3614 | { | |
3615 | return ($multiplier) ? array_fill(0, $multiplier, $input) : array(); | |
3616 | } | |
3617 | ||
3618 | /** | |
3619 | * Logical Left Shift | |
3620 | * | |
3621 | * Shifts binary strings $shift bits, essentially multiplying by 2**$shift. | |
3622 | * | |
3623 | * @param $x String | |
3624 | * @param $shift Integer | |
3625 | * @return String | |
3626 | * @access private | |
3627 | */ | |
3628 | function _base256_lshift(&$x, $shift) | |
3629 | { | |
3630 | if ($shift == 0) { | |
3631 | return; | |
3632 | } | |
3633 | ||
3634 | $num_bytes = $shift >> 3; // eg. floor($shift/8) | |
3635 | $shift &= 7; // eg. $shift % 8 | |
3636 | ||
3637 | $carry = 0; | |
3638 | for ($i = strlen($x) - 1; $i >= 0; --$i) { | |
3639 | $temp = ord($x[$i]) << $shift | $carry; | |
3640 | $x[$i] = chr($temp); | |
3641 | $carry = $temp >> 8; | |
3642 | } | |
3643 | $carry = ($carry != 0) ? chr($carry) : ''; | |
3644 | $x = $carry . $x . str_repeat(chr(0), $num_bytes); | |
3645 | } | |
3646 | ||
3647 | /** | |
3648 | * Logical Right Shift | |
3649 | * | |
3650 | * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder. | |
3651 | * | |
3652 | * @param $x String | |
3653 | * @param $shift Integer | |
3654 | * @return String | |
3655 | * @access private | |
3656 | */ | |
3657 | function _base256_rshift(&$x, $shift) | |
3658 | { | |
3659 | if ($shift == 0) { | |
3660 | $x = ltrim($x, chr(0)); | |
3661 | return ''; | |
3662 | } | |
3663 | ||
3664 | $num_bytes = $shift >> 3; // eg. floor($shift/8) | |
3665 | $shift &= 7; // eg. $shift % 8 | |
3666 | ||
3667 | $remainder = ''; | |
3668 | if ($num_bytes) { | |
3669 | $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes; | |
3670 | $remainder = substr($x, $start); | |
3671 | $x = substr($x, 0, -$num_bytes); | |
3672 | } | |
3673 | ||
3674 | $carry = 0; | |
3675 | $carry_shift = 8 - $shift; | |
3676 | for ($i = 0; $i < strlen($x); ++$i) { | |
3677 | $temp = (ord($x[$i]) >> $shift) | $carry; | |
3678 | $carry = (ord($x[$i]) << $carry_shift) & 0xFF; | |
3679 | $x[$i] = chr($temp); | |
3680 | } | |
3681 | $x = ltrim($x, chr(0)); | |
3682 | ||
3683 | $remainder = chr($carry >> $carry_shift) . $remainder; | |
3684 | ||
3685 | return ltrim($remainder, chr(0)); | |
3686 | } | |
3687 | ||
3688 | // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long | |
3689 | // at 32-bits, while java's longs are 64-bits. | |
3690 | ||
3691 | /** | |
3692 | * Converts 32-bit integers to bytes. | |
3693 | * | |
3694 | * @param Integer $x | |
3695 | * @return String | |
3696 | * @access private | |
3697 | */ | |
3698 | function _int2bytes($x) | |
3699 | { | |
3700 | return ltrim(pack('N', $x), chr(0)); | |
3701 | } | |
3702 | ||
3703 | /** | |
3704 | * Converts bytes to 32-bit integers | |
3705 | * | |
3706 | * @param String $x | |
3707 | * @return Integer | |
3708 | * @access private | |
3709 | */ | |
3710 | function _bytes2int($x) | |
3711 | { | |
3712 | $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT)); | |
3713 | return $temp['int']; | |
3714 | } | |
3715 | ||
3716 | /** | |
3717 | * DER-encode an integer | |
3718 | * | |
3719 | * The ability to DER-encode integers is needed to create RSA public keys for use with OpenSSL | |
3720 | * | |
3721 | * @see modPow() | |
3722 | * @access private | |
3723 | * @param Integer $length | |
3724 | * @return String | |
3725 | */ | |
3726 | function _encodeASN1Length($length) | |
3727 | { | |
3728 | if ($length <= 0x7F) { | |
3729 | return chr($length); | |
3730 | } | |
3731 | ||
3732 | $temp = ltrim(pack('N', $length), chr(0)); | |
3733 | return pack('Ca*', 0x80 | strlen($temp), $temp); | |
3734 | } | |
3735 | ||
3736 | /** | |
3737 | * Single digit division | |
3738 | * | |
3739 | * Even if int64 is being used the division operator will return a float64 value | |
3740 | * if the dividend is not evenly divisible by the divisor. Since a float64 doesn't | |
3741 | * have the precision of int64 this is a problem so, when int64 is being used, | |
3742 | * we'll guarantee that the dividend is divisible by first subtracting the remainder. | |
3743 | * | |
3744 | * @access private | |
3745 | * @param Integer $x | |
3746 | * @param Integer $y | |
3747 | * @return Integer | |
3748 | */ | |
3749 | function _safe_divide($x, $y) | |
3750 | { | |
3751 | if (MATH_BIGINTEGER_BASE === 26) { | |
3752 | return (int) ($x / $y); | |
3753 | } | |
3754 | ||
3755 | // MATH_BIGINTEGER_BASE === 31 | |
3756 | return ($x - ($x % $y)) / $y; | |
3757 | } | |
3758 | } |