projects / weblabels.fsf.org.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
commiting uncommited changes on live site
[weblabels.fsf.org.git] / crm.fsf.org / 20131203 / files / sites / all / modules-old / civicrm / vendor / phpseclib / phpseclib / phpseclib / Math / BigInteger.php
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 }