2 /* vim: set expandtab tabstop=4 shiftwidth=4 softtabstop=4: */
\r
5 * Pure-PHP arbitrary precision integer arithmetic library.
\r
7 * Supports base-2, base-10, base-16, and base-256 numbers. Uses the GMP or BCMath extensions, if available,
\r
8 * and an internal implementation, otherwise.
\r
10 * PHP versions 4 and 5
\r
12 * {@internal (all DocBlock comments regarding implementation - such as the one that follows - refer to the
\r
13 * {@link MATH_BIGINTEGER_MODE_INTERNAL MATH_BIGINTEGER_MODE_INTERNAL} mode)
\r
15 * Math_BigInteger uses base-2**26 to perform operations such as multiplication and division and
\r
16 * base-2**52 (ie. two base 2**26 digits) to perform addition and subtraction. Because the largest possible
\r
17 * value when multiplying two base-2**26 numbers together is a base-2**52 number, double precision floating
\r
18 * point numbers - numbers that should be supported on most hardware and whose significand is 53 bits - are
\r
19 * used. As a consequence, bitwise operators such as >> and << cannot be used, nor can the modulo operator %,
\r
20 * which only supports integers. Although this fact will slow this library down, the fact that such a high
\r
21 * base is being used should more than compensate.
\r
23 * When PHP version 6 is officially released, we'll be able to use 64-bit integers. This should, once again,
\r
24 * allow bitwise operators, and will increase the maximum possible base to 2**31 (or 2**62 for addition /
\r
27 * Useful resources are as follows:
\r
29 * - {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf Handbook of Applied Cryptography (HAC)}
\r
30 * - {@link http://math.libtomcrypt.com/files/tommath.pdf Multi-Precision Math (MPM)}
\r
31 * - Java's BigInteger classes. See /j2se/src/share/classes/java/math in jdk-1_5_0-src-jrl.zip
\r
33 * One idea for optimization is to use the comba method to reduce the number of operations performed.
\r
34 * MPM uses this quite extensively. The following URL elaborates:
\r
36 * {@link http://www.everything2.com/index.pl?node_id=1736418}}}
\r
38 * Here's an example of how to use this library:
\r
41 * include('Math/BigInteger.php');
\r
43 * $a = new Math_BigInteger(2);
\r
44 * $b = new Math_BigInteger(3);
\r
48 * echo $c->toString(); // outputs 5
\r
52 * LICENSE: This library is free software; you can redistribute it and/or
\r
53 * modify it under the terms of the GNU Lesser General Public
\r
54 * License as published by the Free Software Foundation; either
\r
55 * version 2.1 of the License, or (at your option) any later version.
\r
57 * This library is distributed in the hope that it will be useful,
\r
58 * but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
59 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
\r
60 * Lesser General Public License for more details.
\r
62 * You should have received a copy of the GNU Lesser General Public
\r
63 * License along with this library; if not, write to the Free Software
\r
64 * Foundation, Inc., 59 Temple Place, Suite 330, Boston,
\r
68 * @package Math_BigInteger
\r
69 * @author Jim Wigginton <terrafrost@php.net>
\r
70 * @copyright MMVI Jim Wigginton
\r
71 * @license http://www.gnu.org/licenses/lgpl.txt
\r
72 * @version $Id: BigInteger.php,v 1.18 2009/12/04 19:12:18 terrafrost Exp $
\r
73 * @link http://pear.php.net/package/Math_BigInteger
\r
78 * @see Math_BigInteger::_slidingWindow()
\r
81 * @see Math_BigInteger::_montgomery()
\r
82 * @see Math_BigInteger::_prepMontgomery()
\r
84 define('MATH_BIGINTEGER_MONTGOMERY', 0);
\r
86 * @see Math_BigInteger::_barrett()
\r
88 define('MATH_BIGINTEGER_BARRETT', 1);
\r
90 * @see Math_BigInteger::_mod2()
\r
92 define('MATH_BIGINTEGER_POWEROF2', 2);
\r
94 * @see Math_BigInteger::_remainder()
\r
96 define('MATH_BIGINTEGER_CLASSIC', 3);
\r
98 * @see Math_BigInteger::__clone()
\r
100 define('MATH_BIGINTEGER_NONE', 4);
\r
105 * @see Math_BigInteger::_montgomery()
\r
106 * @see Math_BigInteger::_barrett()
\r
109 * $cache[MATH_BIGINTEGER_VARIABLE] tells us whether or not the cached data is still valid.
\r
111 define('MATH_BIGINTEGER_VARIABLE', 0);
\r
113 * $cache[MATH_BIGINTEGER_DATA] contains the cached data.
\r
115 define('MATH_BIGINTEGER_DATA', 1);
\r
120 * @see Math_BigInteger::Math_BigInteger()
\r
123 * To use the pure-PHP implementation
\r
125 define('MATH_BIGINTEGER_MODE_INTERNAL', 1);
\r
127 * To use the BCMath library
\r
129 * (if enabled; otherwise, the internal implementation will be used)
\r
131 define('MATH_BIGINTEGER_MODE_BCMATH', 2);
\r
133 * To use the GMP library
\r
135 * (if present; otherwise, either the BCMath or the internal implementation will be used)
\r
137 define('MATH_BIGINTEGER_MODE_GMP', 3);
\r
141 * The largest digit that may be used in addition / subtraction
\r
143 * (we do pow(2, 52) instead of using 4503599627370496, directly, because some PHP installations
\r
144 * will truncate 4503599627370496)
\r
148 define('MATH_BIGINTEGER_MAX_DIGIT52', pow(2, 52));
\r
153 * At what point do we switch between Karatsuba multiplication and schoolbook long multiplication?
\r
157 define('MATH_BIGINTEGER_KARATSUBA_CUTOFF', 15);
\r
160 * Pure-PHP arbitrary precision integer arithmetic library. Supports base-2, base-10, base-16, and base-256
\r
163 * @author Jim Wigginton <terrafrost@php.net>
\r
164 * @version 1.0.0RC3
\r
166 * @package Math_BigInteger
\r
168 class Math_BigInteger {
\r
170 * Holds the BigInteger's value.
\r
178 * Holds the BigInteger's magnitude.
\r
183 var $is_negative = false;
\r
186 * Random number generator function
\r
188 * @see setRandomGenerator()
\r
191 var $generator = 'mt_rand';
\r
196 * @see setPrecision()
\r
199 var $precision = -1;
\r
202 * Precision Bitmask
\r
204 * @see setPrecision()
\r
207 var $bitmask = false;
\r
210 * Converts base-2, base-10, base-16, and binary strings (eg. base-256) to BigIntegers.
\r
212 * If the second parameter - $base - is negative, then it will be assumed that the number's are encoded using
\r
213 * two's compliment. The sole exception to this is -10, which is treated the same as 10 is.
\r
215 * Here's an example:
\r
218 * include('Math/BigInteger.php');
\r
220 * $a = new Math_BigInteger('0x32', 16); // 50 in base-16
\r
222 * echo $a->toString(); // outputs 50
\r
226 * @param optional $x base-10 number or base-$base number if $base set.
\r
227 * @param optional integer $base
\r
228 * @return Math_BigInteger
\r
231 function Math_BigInteger($x = 0, $base = 10)
\r
233 if ( !defined('MATH_BIGINTEGER_MODE') ) {
\r
235 case extension_loaded('gmp'):
\r
236 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_GMP);
\r
238 case extension_loaded('bcmath'):
\r
239 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_BCMATH);
\r
242 define('MATH_BIGINTEGER_MODE', MATH_BIGINTEGER_MODE_INTERNAL);
\r
246 switch ( MATH_BIGINTEGER_MODE ) {
\r
247 case MATH_BIGINTEGER_MODE_GMP:
\r
248 if (is_resource($x) && get_resource_type($x) == 'GMP integer') {
\r
252 $this->value = gmp_init(0);
\r
254 case MATH_BIGINTEGER_MODE_BCMATH:
\r
255 $this->value = '0';
\r
258 $this->value = array();
\r
267 if (ord($x[0]) & 0x80) {
\r
269 $this->is_negative = true;
\r
272 switch ( MATH_BIGINTEGER_MODE ) {
\r
273 case MATH_BIGINTEGER_MODE_GMP:
\r
274 $sign = $this->is_negative ? '-' : '';
\r
275 $this->value = gmp_init($sign . '0x' . bin2hex($x));
\r
277 case MATH_BIGINTEGER_MODE_BCMATH:
\r
278 // round $len to the nearest 4 (thanks, DavidMJ!)
\r
279 $len = (strlen($x) + 3) & 0xFFFFFFFC;
\r
281 $x = str_pad($x, $len, chr(0), STR_PAD_LEFT);
\r
283 for ($i = 0; $i < $len; $i+= 4) {
\r
284 $this->value = bcmul($this->value, '4294967296'); // 4294967296 == 2**32
\r
285 $this->value = bcadd($this->value, 0x1000000 * ord($x[$i]) + ((ord($x[$i + 1]) << 16) | (ord($x[$i + 2]) << 8) | ord($x[$i + 3])));
\r
288 if ($this->is_negative) {
\r
289 $this->value = '-' . $this->value;
\r
293 // converts a base-2**8 (big endian / msb) number to base-2**26 (little endian / lsb)
\r
295 while (strlen($x)) {
\r
296 $this->value[] = $this->_bytes2int($this->_base256_rshift($x, 26));
\r
300 if ($this->is_negative) {
\r
301 if (MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_INTERNAL) {
\r
302 $this->is_negative = false;
\r
304 $temp = $this->add(new Math_BigInteger('-1'));
\r
305 $this->value = $temp->value;
\r
310 if ($base > 0 && $x[0] == '-') {
\r
311 $this->is_negative = true;
\r
312 $x = substr($x, 1);
\r
315 $x = preg_replace('#^(?:0x)?([A-Fa-f0-9]*).*#', '$1', $x);
\r
317 $is_negative = false;
\r
318 if ($base < 0 && hexdec($x[0]) >= 8) {
\r
319 $this->is_negative = $is_negative = true;
\r
320 $x = bin2hex(~pack('H*', $x));
\r
323 switch ( MATH_BIGINTEGER_MODE ) {
\r
324 case MATH_BIGINTEGER_MODE_GMP:
\r
325 $temp = $this->is_negative ? '-0x' . $x : '0x' . $x;
\r
326 $this->value = gmp_init($temp);
\r
327 $this->is_negative = false;
\r
329 case MATH_BIGINTEGER_MODE_BCMATH:
\r
330 $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
\r
331 $temp = new Math_BigInteger(pack('H*', $x), 256);
\r
332 $this->value = $this->is_negative ? '-' . $temp->value : $temp->value;
\r
333 $this->is_negative = false;
\r
336 $x = ( strlen($x) & 1 ) ? '0' . $x : $x;
\r
337 $temp = new Math_BigInteger(pack('H*', $x), 256);
\r
338 $this->value = $temp->value;
\r
341 if ($is_negative) {
\r
342 $temp = $this->add(new Math_BigInteger('-1'));
\r
343 $this->value = $temp->value;
\r
348 $x = preg_replace('#^(-?[0-9]*).*#', '$1', $x);
\r
350 switch ( MATH_BIGINTEGER_MODE ) {
\r
351 case MATH_BIGINTEGER_MODE_GMP:
\r
352 $this->value = gmp_init($x);
\r
354 case MATH_BIGINTEGER_MODE_BCMATH:
\r
355 // explicitly casting $x to a string is necessary, here, since doing $x[0] on -1 yields different
\r
356 // results then doing it on '-1' does (modInverse does $x[0])
\r
357 $this->value = (string) $x;
\r
360 $temp = new Math_BigInteger();
\r
362 // array(10000000) is 10**7 in base-2**26. 10**7 is the closest to 2**26 we can get without passing it.
\r
363 $multiplier = new Math_BigInteger();
\r
364 $multiplier->value = array(10000000);
\r
366 if ($x[0] == '-') {
\r
367 $this->is_negative = true;
\r
368 $x = substr($x, 1);
\r
371 $x = str_pad($x, strlen($x) + (6 * strlen($x)) % 7, 0, STR_PAD_LEFT);
\r
373 while (strlen($x)) {
\r
374 $temp = $temp->multiply($multiplier);
\r
375 $temp = $temp->add(new Math_BigInteger($this->_int2bytes(substr($x, 0, 7)), 256));
\r
376 $x = substr($x, 7);
\r
379 $this->value = $temp->value;
\r
382 case 2: // base-2 support originally implemented by Lluis Pamies - thanks!
\r
384 if ($base > 0 && $x[0] == '-') {
\r
385 $this->is_negative = true;
\r
386 $x = substr($x, 1);
\r
389 $x = preg_replace('#^([01]*).*#', '$1', $x);
\r
390 $x = str_pad($x, strlen($x) + (3 * strlen($x)) % 4, 0, STR_PAD_LEFT);
\r
393 while (strlen($x)) {
\r
394 $part = substr($x, 0, 4);
\r
395 $str.= dechex(bindec($part));
\r
396 $x = substr($x, 4);
\r
399 if ($this->is_negative) {
\r
403 $temp = new Math_BigInteger($str, 8 * $base); // ie. either -16 or +16
\r
404 $this->value = $temp->value;
\r
405 $this->is_negative = $temp->is_negative;
\r
409 // base not supported, so we'll let $this == 0
\r
414 * Converts a BigInteger to a byte string (eg. base-256).
\r
416 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
\r
417 * saved as two's compliment.
\r
419 * Here's an example:
\r
422 * include('Math/BigInteger.php');
\r
424 * $a = new Math_BigInteger('65');
\r
426 * echo $a->toBytes(); // outputs chr(65)
\r
430 * @param Boolean $twos_compliment
\r
433 * @internal Converts a base-2**26 number to base-2**8
\r
435 function toBytes($twos_compliment = false)
\r
437 if ($twos_compliment) {
\r
438 $comparison = $this->compare(new Math_BigInteger());
\r
439 if ($comparison == 0) {
\r
440 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
443 $temp = $comparison < 0 ? $this->add(new Math_BigInteger(1)) : $this->copy();
\r
444 $bytes = $temp->toBytes();
\r
446 if (empty($bytes)) { // eg. if the number we're trying to convert is -1
\r
450 if (ord($bytes[0]) & 0x80) {
\r
451 $bytes = chr(0) . $bytes;
\r
454 return $comparison < 0 ? ~$bytes : $bytes;
\r
457 switch ( MATH_BIGINTEGER_MODE ) {
\r
458 case MATH_BIGINTEGER_MODE_GMP:
\r
459 if (gmp_cmp($this->value, gmp_init(0)) == 0) {
\r
460 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
463 $temp = gmp_strval(gmp_abs($this->value), 16);
\r
464 $temp = ( strlen($temp) & 1 ) ? '0' . $temp : $temp;
\r
465 $temp = pack('H*', $temp);
\r
467 return $this->precision > 0 ?
\r
468 substr(str_pad($temp, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
\r
469 ltrim($temp, chr(0));
\r
470 case MATH_BIGINTEGER_MODE_BCMATH:
\r
471 if ($this->value === '0') {
\r
472 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
476 $current = $this->value;
\r
478 if ($current[0] == '-') {
\r
479 $current = substr($current, 1);
\r
482 // we don't do four bytes at a time because then numbers larger than 1<<31 would be negative
\r
483 // two's complimented numbers, which would break chr.
\r
484 while (bccomp($current, '0') > 0) {
\r
485 $temp = bcmod($current, 0x1000000);
\r
486 $value = chr($temp >> 16) . chr($temp >> 8) . chr($temp) . $value;
\r
487 $current = bcdiv($current, 0x1000000);
\r
490 return $this->precision > 0 ?
\r
491 substr(str_pad($value, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
\r
492 ltrim($value, chr(0));
\r
495 if (!count($this->value)) {
\r
496 return $this->precision > 0 ? str_repeat(chr(0), ($this->precision + 1) >> 3) : '';
\r
498 $result = $this->_int2bytes($this->value[count($this->value) - 1]);
\r
500 $temp = $this->copy();
\r
502 for ($i = count($temp->value) - 2; $i >= 0; $i--) {
\r
503 $temp->_base256_lshift($result, 26);
\r
504 $result = $result | str_pad($temp->_int2bytes($temp->value[$i]), strlen($result), chr(0), STR_PAD_LEFT);
\r
507 return $this->precision > 0 ?
\r
508 substr(str_pad($result, $this->precision >> 3, chr(0), STR_PAD_LEFT), -($this->precision >> 3)) :
\r
513 * Converts a BigInteger to a hex string (eg. base-16)).
\r
515 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
\r
516 * saved as two's compliment.
\r
518 * Here's an example:
\r
521 * include('Math/BigInteger.php');
\r
523 * $a = new Math_BigInteger('65');
\r
525 * echo $a->toHex(); // outputs '41'
\r
529 * @param Boolean $twos_compliment
\r
532 * @internal Converts a base-2**26 number to base-2**8
\r
534 function toHex($twos_compliment = false)
\r
536 return bin2hex($this->toBytes($twos_compliment));
\r
540 * Converts a BigInteger to a bit string (eg. base-2).
\r
542 * Negative numbers are saved as positive numbers, unless $twos_compliment is set to true, at which point, they're
\r
543 * saved as two's compliment.
\r
545 * Here's an example:
\r
548 * include('Math/BigInteger.php');
\r
550 * $a = new Math_BigInteger('65');
\r
552 * echo $a->toBits(); // outputs '1000001'
\r
556 * @param Boolean $twos_compliment
\r
559 * @internal Converts a base-2**26 number to base-2**2
\r
561 function toBits($twos_compliment = false)
\r
563 $hex = $this->toHex($twos_compliment);
\r
565 for ($i = 0; $i < strlen($hex); $i+=8) {
\r
566 $bits.= str_pad(decbin(hexdec(substr($hex, $i, 8))), 32, '0', STR_PAD_LEFT);
\r
568 return $this->precision > 0 ? substr($bits, -$this->precision) : ltrim($bits, '0');
\r
572 * Converts a BigInteger to a base-10 number.
\r
574 * Here's an example:
\r
577 * include('Math/BigInteger.php');
\r
579 * $a = new Math_BigInteger('50');
\r
581 * echo $a->toString(); // outputs 50
\r
587 * @internal Converts a base-2**26 number to base-10**7 (which is pretty much base-10)
\r
589 function toString()
\r
591 switch ( MATH_BIGINTEGER_MODE ) {
\r
592 case MATH_BIGINTEGER_MODE_GMP:
\r
593 return gmp_strval($this->value);
\r
594 case MATH_BIGINTEGER_MODE_BCMATH:
\r
595 if ($this->value === '0') {
\r
599 return ltrim($this->value, '0');
\r
602 if (!count($this->value)) {
\r
606 $temp = $this->copy();
\r
607 $temp->is_negative = false;
\r
609 $divisor = new Math_BigInteger();
\r
610 $divisor->value = array(10000000); // eg. 10**7
\r
612 while (count($temp->value)) {
\r
613 list($temp, $mod) = $temp->divide($divisor);
\r
614 $result = str_pad($mod->value[0], 7, '0', STR_PAD_LEFT) . $result;
\r
616 $result = ltrim($result, '0');
\r
618 if ($this->is_negative) {
\r
619 $result = '-' . $result;
\r
628 * PHP5 passes objects by reference while PHP4 passes by value. As such, we need a function to guarantee
\r
629 * that all objects are passed by value, when appropriate. More information can be found here:
\r
631 * {@link http://php.net/language.oop5.basic#51624}
\r
635 * @return Math_BigInteger
\r
639 $temp = new Math_BigInteger();
\r
640 $temp->value = $this->value;
\r
641 $temp->is_negative = $this->is_negative;
\r
642 $temp->generator = $this->generator;
\r
643 $temp->precision = $this->precision;
\r
644 $temp->bitmask = $this->bitmask;
\r
649 * __toString() magic method
\r
651 * Will be called, automatically, if you're supporting just PHP5. If you're supporting PHP4, you'll need to call
\r
655 * @internal Implemented per a suggestion by Techie-Michael - thanks!
\r
657 function __toString()
\r
659 return $this->toString();
\r
663 * __clone() magic method
\r
665 * Although you can call Math_BigInteger::__toString() directly in PHP5, you cannot call Math_BigInteger::__clone()
\r
666 * 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
\r
667 * only syntax of $y = clone $x. As such, if you're trying to write an application that works on both PHP4 and PHP5,
\r
668 * call Math_BigInteger::copy(), instead.
\r
672 * @return Math_BigInteger
\r
676 return $this->copy();
\r
680 * Adds two BigIntegers.
\r
682 * Here's an example:
\r
685 * include('Math/BigInteger.php');
\r
687 * $a = new Math_BigInteger('10');
\r
688 * $b = new Math_BigInteger('20');
\r
690 * $c = $a->add($b);
\r
692 * echo $c->toString(); // outputs 30
\r
696 * @param Math_BigInteger $y
\r
697 * @return Math_BigInteger
\r
699 * @internal Performs base-2**52 addition
\r
703 switch ( MATH_BIGINTEGER_MODE ) {
\r
704 case MATH_BIGINTEGER_MODE_GMP:
\r
705 $temp = new Math_BigInteger();
\r
706 $temp->value = gmp_add($this->value, $y->value);
\r
708 return $this->_normalize($temp);
\r
709 case MATH_BIGINTEGER_MODE_BCMATH:
\r
710 $temp = new Math_BigInteger();
\r
711 $temp->value = bcadd($this->value, $y->value);
\r
713 return $this->_normalize($temp);
\r
716 $this_size = count($this->value);
\r
717 $y_size = count($y->value);
\r
719 if ($this_size == 0) {
\r
721 } else if ($y_size == 0) {
\r
722 return $this->copy();
\r
725 // subtract, if appropriate
\r
726 if ( $this->is_negative != $y->is_negative ) {
\r
727 // is $y the negative number?
\r
728 $y_negative = $this->compare($y) > 0;
\r
730 $temp = $this->copy();
\r
732 $temp->is_negative = $y->is_negative = false;
\r
734 $diff = $temp->compare($y);
\r
736 $temp = new Math_BigInteger();
\r
737 return $this->_normalize($temp);
\r
740 $temp = $temp->subtract($y);
\r
742 $temp->is_negative = ($diff > 0) ? !$y_negative : $y_negative;
\r
744 return $this->_normalize($temp);
\r
747 $result = new Math_BigInteger();
\r
750 $size = max($this_size, $y_size);
\r
751 $size+= $size & 1; // rounds $size to the nearest 2.
\r
753 $x = array_pad($this->value, $size, 0);
\r
754 $y = array_pad($y->value, $size, 0);
\r
756 for ($i = 0; $i < $size - 1; $i+=2) {
\r
757 $sum = $x[$i + 1] * 0x4000000 + $x[$i] + $y[$i + 1] * 0x4000000 + $y[$i] + $carry;
\r
758 $carry = $sum >= MATH_BIGINTEGER_MAX_DIGIT52; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
\r
759 $sum = $carry ? $sum - MATH_BIGINTEGER_MAX_DIGIT52 : $sum;
\r
761 $temp = floor($sum / 0x4000000);
\r
763 $result->value[] = $sum - 0x4000000 * $temp; // eg. a faster alternative to fmod($sum, 0x4000000)
\r
764 $result->value[] = $temp;
\r
768 $result->value[] = (int) $carry;
\r
771 $result->is_negative = $this->is_negative;
\r
773 return $this->_normalize($result);
\r
777 * Subtracts two BigIntegers.
\r
779 * Here's an example:
\r
782 * include('Math/BigInteger.php');
\r
784 * $a = new Math_BigInteger('10');
\r
785 * $b = new Math_BigInteger('20');
\r
787 * $c = $a->subtract($b);
\r
789 * echo $c->toString(); // outputs -10
\r
793 * @param Math_BigInteger $y
\r
794 * @return Math_BigInteger
\r
796 * @internal Performs base-2**52 subtraction
\r
798 function subtract($y)
\r
800 switch ( MATH_BIGINTEGER_MODE ) {
\r
801 case MATH_BIGINTEGER_MODE_GMP:
\r
802 $temp = new Math_BigInteger();
\r
803 $temp->value = gmp_sub($this->value, $y->value);
\r
805 return $this->_normalize($temp);
\r
806 case MATH_BIGINTEGER_MODE_BCMATH:
\r
807 $temp = new Math_BigInteger();
\r
808 $temp->value = bcsub($this->value, $y->value);
\r
810 return $this->_normalize($temp);
\r
813 $this_size = count($this->value);
\r
814 $y_size = count($y->value);
\r
816 if ($this_size == 0) {
\r
817 $temp = $y->copy();
\r
818 $temp->is_negative = !$temp->is_negative;
\r
820 } else if ($y_size == 0) {
\r
821 return $this->copy();
\r
824 // add, if appropriate (ie. -$x - +$y or +$x - -$y)
\r
825 if ( $this->is_negative != $y->is_negative ) {
\r
826 $is_negative = $y->compare($this) > 0;
\r
828 $temp = $this->copy();
\r
830 $temp->is_negative = $y->is_negative = false;
\r
832 $temp = $temp->add($y);
\r
834 $temp->is_negative = $is_negative;
\r
836 return $this->_normalize($temp);
\r
839 $diff = $this->compare($y);
\r
842 $temp = new Math_BigInteger();
\r
843 return $this->_normalize($temp);
\r
846 // switch $this and $y around, if appropriate.
\r
847 if ( (!$this->is_negative && $diff < 0) || ($this->is_negative && $diff > 0) ) {
\r
848 $is_negative = $y->is_negative;
\r
850 $temp = $this->copy();
\r
852 $temp->is_negative = $y->is_negative = false;
\r
854 $temp = $y->subtract($temp);
\r
855 $temp->is_negative = !$is_negative;
\r
857 return $this->_normalize($temp);
\r
860 $result = new Math_BigInteger();
\r
863 $size = max($this_size, $y_size);
\r
866 $x = array_pad($this->value, $size, 0);
\r
867 $y = array_pad($y->value, $size, 0);
\r
869 for ($i = 0; $i < $size - 1; $i+=2) {
\r
870 $sum = $x[$i + 1] * 0x4000000 + $x[$i] - $y[$i + 1] * 0x4000000 - $y[$i] + $carry;
\r
871 $carry = $sum < 0 ? -1 : 0; // eg. floor($sum / 2**52); only possible values (in any base) are 0 and 1
\r
872 $sum = $carry ? $sum + MATH_BIGINTEGER_MAX_DIGIT52 : $sum;
\r
874 $temp = floor($sum / 0x4000000);
\r
876 $result->value[] = $sum - 0x4000000 * $temp;
\r
877 $result->value[] = $temp;
\r
880 // $carry shouldn't be anything other than zero, at this point, since we already made sure that $this
\r
881 // was bigger than $y.
\r
883 $result->is_negative = $this->is_negative;
\r
885 return $this->_normalize($result);
\r
889 * Multiplies two BigIntegers
\r
891 * Here's an example:
\r
894 * include('Math/BigInteger.php');
\r
896 * $a = new Math_BigInteger('10');
\r
897 * $b = new Math_BigInteger('20');
\r
899 * $c = $a->multiply($b);
\r
901 * echo $c->toString(); // outputs 200
\r
905 * @param Math_BigInteger $x
\r
906 * @return Math_BigInteger
\r
909 function multiply($x)
\r
911 switch ( MATH_BIGINTEGER_MODE ) {
\r
912 case MATH_BIGINTEGER_MODE_GMP:
\r
913 $temp = new Math_BigInteger();
\r
914 $temp->value = gmp_mul($this->value, $x->value);
\r
916 return $this->_normalize($temp);
\r
917 case MATH_BIGINTEGER_MODE_BCMATH:
\r
918 $temp = new Math_BigInteger();
\r
919 $temp->value = bcmul($this->value, $x->value);
\r
921 return $this->_normalize($temp);
\r
924 static $cutoff = false;
\r
925 if ($cutoff === false) {
\r
926 $cutoff = 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF;
\r
929 if ( $this->equals($x) ) {
\r
930 return $this->_square();
\r
933 $this_length = count($this->value);
\r
934 $x_length = count($x->value);
\r
936 if ( !$this_length || !$x_length ) { // a 0 is being multiplied
\r
937 $temp = new Math_BigInteger();
\r
938 return $this->_normalize($temp);
\r
941 $product = min($this_length, $x_length) < $cutoff ? $this->_multiply($x) : $this->_karatsuba($x);
\r
943 $product->is_negative = $this->is_negative != $x->is_negative;
\r
945 return $this->_normalize($product);
\r
949 * Performs long multiplication up to $stop digits
\r
951 * If you're going to be doing array_slice($product->value, 0, $stop), some cycles can be saved.
\r
954 * @param Math_BigInteger $x
\r
955 * @return Math_BigInteger
\r
958 function _multiplyLower($x, $stop)
\r
960 $this_length = count($this->value);
\r
961 $x_length = count($x->value);
\r
963 if ( !$this_length || !$x_length ) { // a 0 is being multiplied
\r
964 return new Math_BigInteger();
\r
967 if ( $this_length < $x_length ) {
\r
968 return $x->_multiplyLower($this, $stop);
\r
971 $product = new Math_BigInteger();
\r
972 $product->value = $this->_array_repeat(0, $this_length + $x_length);
\r
974 // the following for loop could be removed if the for loop following it
\r
975 // (the one with nested for loops) initially set $i to 0, but
\r
976 // doing so would also make the result in one set of unnecessary adds,
\r
977 // since on the outermost loops first pass, $product->value[$k] is going
\r
982 for ($j = 0; $j < $this_length; $j++) { // ie. $i = 0, $k = $i
\r
983 $temp = $this->value[$j] * $x->value[0] + $carry; // $product->value[$k] == 0
\r
984 $carry = floor($temp / 0x4000000);
\r
985 $product->value[$j] = $temp - 0x4000000 * $carry;
\r
989 $product->value[$j] = $carry;
\r
992 // the above for loop is what the previous comment was talking about. the
\r
993 // following for loop is the "one with nested for loops"
\r
995 for ($i = 1; $i < $x_length; $i++) {
\r
998 for ($j = 0, $k = $i; $j < $this_length && $k < $stop; $j++, $k++) {
\r
999 $temp = $product->value[$k] + $this->value[$j] * $x->value[$i] + $carry;
\r
1000 $carry = floor($temp / 0x4000000);
\r
1001 $product->value[$k] = $temp - 0x4000000 * $carry;
\r
1005 $product->value[$k] = $carry;
\r
1009 $product->is_negative = $this->is_negative != $x->is_negative;
\r
1015 * Performs long multiplication on two BigIntegers
\r
1017 * Modeled after 'multiply' in MutableBigInteger.java.
\r
1019 * @param Math_BigInteger $x
\r
1020 * @return Math_BigInteger
\r
1023 function _multiply($x)
\r
1025 $this_length = count($this->value);
\r
1026 $x_length = count($x->value);
\r
1028 if ( !$this_length || !$x_length ) { // a 0 is being multiplied
\r
1029 return new Math_BigInteger();
\r
1032 if ( $this_length < $x_length ) {
\r
1033 return $x->_multiply($this);
\r
1036 $product = new Math_BigInteger();
\r
1037 $product->value = $this->_array_repeat(0, $this_length + $x_length);
\r
1039 // the following for loop could be removed if the for loop following it
\r
1040 // (the one with nested for loops) initially set $i to 0, but
\r
1041 // doing so would also make the result in one set of unnecessary adds,
\r
1042 // since on the outermost loops first pass, $product->value[$k] is going
\r
1047 for ($j = 0; $j < $this_length; $j++) { // ie. $i = 0
\r
1048 $temp = $this->value[$j] * $x->value[0] + $carry; // $product->value[$k] == 0
\r
1049 $carry = floor($temp / 0x4000000);
\r
1050 $product->value[$j] = $temp - 0x4000000 * $carry;
\r
1053 $product->value[$j] = $carry;
\r
1055 // the above for loop is what the previous comment was talking about. the
\r
1056 // following for loop is the "one with nested for loops"
\r
1057 for ($i = 1; $i < $x_length; $i++) {
\r
1060 for ($j = 0, $k = $i; $j < $this_length; $j++, $k++) {
\r
1061 $temp = $product->value[$k] + $this->value[$j] * $x->value[$i] + $carry;
\r
1062 $carry = floor($temp / 0x4000000);
\r
1063 $product->value[$k] = $temp - 0x4000000 * $carry;
\r
1066 $product->value[$k] = $carry;
\r
1069 $product->is_negative = $this->is_negative != $x->is_negative;
\r
1071 return $this->_normalize($product);
\r
1075 * Performs Karatsuba multiplication on two BigIntegers
\r
1077 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
\r
1078 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=120 MPM 5.2.3}.
\r
1080 * @param Math_BigInteger $y
\r
1081 * @return Math_BigInteger
\r
1084 function _karatsuba($y)
\r
1086 $x = $this->copy();
\r
1088 $m = min(count($x->value) >> 1, count($y->value) >> 1);
\r
1090 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
\r
1091 return $x->_multiply($y);
\r
1094 $x1 = new Math_BigInteger();
\r
1095 $x0 = new Math_BigInteger();
\r
1096 $y1 = new Math_BigInteger();
\r
1097 $y0 = new Math_BigInteger();
\r
1099 $x1->value = array_slice($x->value, $m);
\r
1100 $x0->value = array_slice($x->value, 0, $m);
\r
1101 $y1->value = array_slice($y->value, $m);
\r
1102 $y0->value = array_slice($y->value, 0, $m);
\r
1104 $z2 = $x1->_karatsuba($y1);
\r
1105 $z0 = $x0->_karatsuba($y0);
\r
1107 $z1 = $x1->add($x0);
\r
1108 $z1 = $z1->_karatsuba($y1->add($y0));
\r
1109 $z1 = $z1->subtract($z2->add($z0));
\r
1111 $z2->value = array_merge(array_fill(0, 2 * $m, 0), $z2->value);
\r
1112 $z1->value = array_merge(array_fill(0, $m, 0), $z1->value);
\r
1114 $xy = $z2->add($z1);
\r
1115 $xy = $xy->add($z0);
\r
1121 * Squares a BigInteger
\r
1123 * @return Math_BigInteger
\r
1126 function _square()
\r
1128 static $cutoff = false;
\r
1129 if ($cutoff === false) {
\r
1130 $cutoff = 2 * MATH_BIGINTEGER_KARATSUBA_CUTOFF;
\r
1133 return count($this->value) < $cutoff ? $this->_baseSquare() : $this->_karatsubaSquare();
\r
1137 * Performs traditional squaring on two BigIntegers
\r
1139 * Squaring can be done faster than multiplying a number by itself can be. See
\r
1140 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=7 HAC 14.2.4} /
\r
1141 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=141 MPM 5.3} for more information.
\r
1143 * @return Math_BigInteger
\r
1146 function _baseSquare()
\r
1148 if ( empty($this->value) ) {
\r
1149 return new Math_BigInteger();
\r
1152 $square = new Math_BigInteger();
\r
1153 $square->value = $this->_array_repeat(0, 2 * count($this->value));
\r
1155 for ($i = 0, $max_index = count($this->value) - 1; $i <= $max_index; $i++) {
\r
1158 $temp = $square->value[$i2] + $this->value[$i] * $this->value[$i];
\r
1159 $carry = floor($temp / 0x4000000);
\r
1160 $square->value[$i2] = $temp - 0x4000000 * $carry;
\r
1162 // note how we start from $i+1 instead of 0 as we do in multiplication.
\r
1163 for ($j = $i + 1, $k = $i2 + 1; $j <= $max_index; $j++, $k++) {
\r
1164 $temp = $square->value[$k] + 2 * $this->value[$j] * $this->value[$i] + $carry;
\r
1165 $carry = floor($temp / 0x4000000);
\r
1166 $square->value[$k] = $temp - 0x4000000 * $carry;
\r
1169 // the following line can yield values larger 2**15. at this point, PHP should switch
\r
1170 // over to floats.
\r
1171 $square->value[$i + $max_index + 1] = $carry;
\r
1178 * Performs Karatsuba "squaring" on two BigIntegers
\r
1180 * See {@link http://en.wikipedia.org/wiki/Karatsuba_algorithm Karatsuba algorithm} and
\r
1181 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=151 MPM 5.3.4}.
\r
1183 * @param Math_BigInteger $y
\r
1184 * @return Math_BigInteger
\r
1187 function _karatsubaSquare()
\r
1189 $m = count($this->value) >> 1;
\r
1191 if ($m < MATH_BIGINTEGER_KARATSUBA_CUTOFF) {
\r
1192 return $this->_square();
\r
1195 $x1 = new Math_BigInteger();
\r
1196 $x0 = new Math_BigInteger();
\r
1198 $x1->value = array_slice($this->value, $m);
\r
1199 $x0->value = array_slice($this->value, 0, $m);
\r
1201 $z2 = $x1->_karatsubaSquare();
\r
1202 $z0 = $x0->_karatsubaSquare();
\r
1204 $z1 = $x1->add($x0);
\r
1205 $z1 = $z1->_karatsubaSquare();
\r
1206 $z1 = $z1->subtract($z2->add($z0));
\r
1208 $z2->value = array_merge(array_fill(0, 2 * $m, 0), $z2->value);
\r
1209 $z1->value = array_merge(array_fill(0, $m, 0), $z1->value);
\r
1211 $xx = $z2->add($z1);
\r
1212 $xx = $xx->add($z0);
\r
1218 * Divides two BigIntegers.
\r
1220 * Returns an array whose first element contains the quotient and whose second element contains the
\r
1221 * "common residue". If the remainder would be positive, the "common residue" and the remainder are the
\r
1222 * same. If the remainder would be negative, the "common residue" is equal to the sum of the remainder
\r
1223 * and the divisor (basically, the "common residue" is the first positive modulo).
\r
1225 * Here's an example:
\r
1228 * include('Math/BigInteger.php');
\r
1230 * $a = new Math_BigInteger('10');
\r
1231 * $b = new Math_BigInteger('20');
\r
1233 * list($quotient, $remainder) = $a->divide($b);
\r
1235 * echo $quotient->toString(); // outputs 0
\r
1237 * echo $remainder->toString(); // outputs 10
\r
1241 * @param Math_BigInteger $y
\r
1244 * @internal This function is based off of {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=9 HAC 14.20}.
\r
1246 function divide($y)
\r
1248 switch ( MATH_BIGINTEGER_MODE ) {
\r
1249 case MATH_BIGINTEGER_MODE_GMP:
\r
1250 $quotient = new Math_BigInteger();
\r
1251 $remainder = new Math_BigInteger();
\r
1253 list($quotient->value, $remainder->value) = gmp_div_qr($this->value, $y->value);
\r
1255 if (gmp_sign($remainder->value) < 0) {
\r
1256 $remainder->value = gmp_add($remainder->value, gmp_abs($y->value));
\r
1259 return array($this->_normalize($quotient), $this->_normalize($remainder));
\r
1260 case MATH_BIGINTEGER_MODE_BCMATH:
\r
1261 $quotient = new Math_BigInteger();
\r
1262 $remainder = new Math_BigInteger();
\r
1264 $quotient->value = bcdiv($this->value, $y->value);
\r
1265 $remainder->value = bcmod($this->value, $y->value);
\r
1267 if ($remainder->value[0] == '-') {
\r
1268 $remainder->value = bcadd($remainder->value, $y->value[0] == '-' ? substr($y->value, 1) : $y->value);
\r
1271 return array($this->_normalize($quotient), $this->_normalize($remainder));
\r
1274 if (count($y->value) == 1) {
\r
1275 $temp = $this->_divide_digit($y->value[0]);
\r
1276 $temp[0]->is_negative = $this->is_negative != $y->is_negative;
\r
1277 return array($this->_normalize($temp[0]), $this->_normalize($temp[1]));
\r
1281 if (!isset($zero)) {
\r
1282 $zero = new Math_BigInteger();
\r
1285 $x = $this->copy();
\r
1288 $x_sign = $x->is_negative;
\r
1289 $y_sign = $y->is_negative;
\r
1291 $x->is_negative = $y->is_negative = false;
\r
1293 $diff = $x->compare($y);
\r
1296 $temp = new Math_BigInteger();
\r
1297 $temp->value = array(1);
\r
1298 $temp->is_negative = $x_sign != $y_sign;
\r
1299 return array($this->_normalize($temp), $this->_normalize(new Math_BigInteger()));
\r
1302 if ( $diff < 0 ) {
\r
1303 // if $x is negative, "add" $y.
\r
1305 $x = $y->subtract($x);
\r
1307 return array($this->_normalize(new Math_BigInteger()), $this->_normalize($x));
\r
1310 // normalize $x and $y as described in HAC 14.23 / 14.24
\r
1311 $msb = $y->value[count($y->value) - 1];
\r
1312 for ($shift = 0; !($msb & 0x2000000); $shift++) {
\r
1315 $x->_lshift($shift);
\r
1316 $y->_lshift($shift);
\r
1318 $x_max = count($x->value) - 1;
\r
1319 $y_max = count($y->value) - 1;
\r
1321 $quotient = new Math_BigInteger();
\r
1322 $quotient->value = $this->_array_repeat(0, $x_max - $y_max + 1);
\r
1324 // $temp = $y << ($x_max - $y_max-1) in base 2**26
\r
1325 $temp = new Math_BigInteger();
\r
1326 $temp->value = array_merge($this->_array_repeat(0, $x_max - $y_max), $y->value);
\r
1328 while ( $x->compare($temp) >= 0 ) {
\r
1329 // calculate the "common residue"
\r
1330 $quotient->value[$x_max - $y_max]++;
\r
1331 $x = $x->subtract($temp);
\r
1332 $x_max = count($x->value) - 1;
\r
1335 for ($i = $x_max; $i >= $y_max + 1; $i--) {
\r
1338 ( $i > 0 ) ? $x->value[$i - 1] : 0,
\r
1339 ( $i > 1 ) ? $x->value[$i - 2] : 0
\r
1342 $y->value[$y_max],
\r
1343 ( $y_max > 0 ) ? $y->value[$y_max - 1] : 0
\r
1346 $q_index = $i - $y_max - 1;
\r
1347 if ($x_value[0] == $y_value[0]) {
\r
1348 $quotient->value[$q_index] = 0x3FFFFFF;
\r
1350 $quotient->value[$q_index] = floor(
\r
1351 ($x_value[0] * 0x4000000 + $x_value[1])
\r
1357 $temp = new Math_BigInteger();
\r
1358 $temp->value = array($y_value[1], $y_value[0]);
\r
1360 $lhs = new Math_BigInteger();
\r
1361 $lhs->value = array($quotient->value[$q_index]);
\r
1362 $lhs = $lhs->multiply($temp);
\r
1364 $rhs = new Math_BigInteger();
\r
1365 $rhs->value = array($x_value[2], $x_value[1], $x_value[0]);
\r
1367 while ( $lhs->compare($rhs) > 0 ) {
\r
1368 $quotient->value[$q_index]--;
\r
1370 $lhs = new Math_BigInteger();
\r
1371 $lhs->value = array($quotient->value[$q_index]);
\r
1372 $lhs = $lhs->multiply($temp);
\r
1375 $adjust = $this->_array_repeat(0, $q_index);
\r
1376 $temp = new Math_BigInteger();
\r
1377 $temp->value = array($quotient->value[$q_index]);
\r
1378 $temp = $temp->multiply($y);
\r
1379 $temp->value = array_merge($adjust, $temp->value);
\r
1381 $x = $x->subtract($temp);
\r
1383 if ($x->compare($zero) < 0) {
\r
1384 $temp->value = array_merge($adjust, $y->value);
\r
1385 $x = $x->add($temp);
\r
1387 $quotient->value[$q_index]--;
\r
1390 $x_max = count($x->value) - 1;
\r
1393 // unnormalize the remainder
\r
1394 $x->_rshift($shift);
\r
1396 $quotient->is_negative = $x_sign != $y_sign;
\r
1398 // calculate the "common residue", if appropriate
\r
1400 $y->_rshift($shift);
\r
1401 $x = $y->subtract($x);
\r
1404 return array($this->_normalize($quotient), $this->_normalize($x));
\r
1408 * Divides a BigInteger by a regular integer
\r
1410 * abc / x = a00 / x + b0 / x + c / x
\r
1412 * @param Math_BigInteger $divisor
\r
1416 function _divide_digit($divisor)
\r
1419 $result = new Math_BigInteger();
\r
1421 for ($i = count($this->value) - 1; $i >= 0; $i--) {
\r
1422 $temp = 0x4000000 * $carry + $this->value[$i];
\r
1423 $result->value[$i] = floor($temp / $divisor);
\r
1424 $carry = fmod($temp, $divisor);
\r
1427 $remainder = new Math_BigInteger();
\r
1428 $remainder->value = array($carry);
\r
1430 return array($result, $remainder);
\r
1434 * Performs modular exponentiation.
\r
1436 * Here's an example:
\r
1439 * include('Math/BigInteger.php');
\r
1441 * $a = new Math_BigInteger('10');
\r
1442 * $b = new Math_BigInteger('20');
\r
1443 * $c = new Math_BigInteger('30');
\r
1445 * $c = $a->modPow($b, $c);
\r
1447 * echo $c->toString(); // outputs 10
\r
1451 * @param Math_BigInteger $e
\r
1452 * @param Math_BigInteger $n
\r
1453 * @return Math_BigInteger
\r
1455 * @internal The most naive approach to modular exponentiation has very unreasonable requirements, and
\r
1456 * and although the approach involving repeated squaring does vastly better, it, too, is impractical
\r
1457 * for our purposes. The reason being that division - by far the most complicated and time-consuming
\r
1458 * of the basic operations (eg. +,-,*,/) - occurs multiple times within it.
\r
1460 * Modular reductions resolve this issue. Although an individual modular reduction takes more time
\r
1461 * then an individual division, when performed in succession (with the same modulo), they're a lot faster.
\r
1463 * The two most commonly used modular reductions are Barrett and Montgomery reduction. Montgomery reduction,
\r
1464 * although faster, only works when the gcd of the modulo and of the base being used is 1. In RSA, when the
\r
1465 * base is a power of two, the modulo - a product of two primes - is always going to have a gcd of 1 (because
\r
1466 * the product of two odd numbers is odd), but what about when RSA isn't used?
\r
1468 * In contrast, Barrett reduction has no such constraint. As such, some bigint implementations perform a
\r
1469 * Barrett reduction after every operation in the modpow function. Others perform Barrett reductions when the
\r
1470 * modulo is even and Montgomery reductions when the modulo is odd. BigInteger.java's modPow method, however,
\r
1471 * uses a trick involving the Chinese Remainder Theorem to factor the even modulo into two numbers - one odd and
\r
1472 * the other, a power of two - and recombine them, later. This is the method that this modPow function uses.
\r
1473 * {@link http://islab.oregonstate.edu/papers/j34monex.pdf Montgomery Reduction with Even Modulus} elaborates.
\r
1475 function modPow($e, $n)
\r
1477 $n = $this->bitmask !== false && $this->bitmask->compare($n) < 0 ? $this->bitmask : $n->abs();
\r
1479 if ($e->compare(new Math_BigInteger()) < 0) {
\r
1482 $temp = $this->modInverse($n);
\r
1483 if ($temp === false) {
\r
1487 return $this->_normalize($temp->modPow($e, $n));
\r
1490 switch ( MATH_BIGINTEGER_MODE ) {
\r
1491 case MATH_BIGINTEGER_MODE_GMP:
\r
1492 $temp = new Math_BigInteger();
\r
1493 $temp->value = gmp_powm($this->value, $e->value, $n->value);
\r
1495 return $this->_normalize($temp);
\r
1496 case MATH_BIGINTEGER_MODE_BCMATH:
\r
1497 $temp = new Math_BigInteger();
\r
1498 $temp->value = bcpowmod($this->value, $e->value, $n->value);
\r
1500 return $this->_normalize($temp);
\r
1503 if ( empty($e->value) ) {
\r
1504 $temp = new Math_BigInteger();
\r
1505 $temp->value = array(1);
\r
1506 return $this->_normalize($temp);
\r
1509 if ( $e->value == array(1) ) {
\r
1510 list(, $temp) = $this->divide($n);
\r
1511 return $this->_normalize($temp);
\r
1514 if ( $e->value == array(2) ) {
\r
1515 $temp = $this->_square();
\r
1516 list(, $temp) = $temp->divide($n);
\r
1517 return $this->_normalize($temp);
\r
1520 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_BARRETT));
\r
1522 // is the modulo odd?
\r
1523 if ( $n->value[0] & 1 ) {
\r
1524 return $this->_normalize($this->_slidingWindow($e, $n, MATH_BIGINTEGER_MONTGOMERY));
\r
1526 // if it's not, it's even
\r
1528 // find the lowest set bit (eg. the max pow of 2 that divides $n)
\r
1529 for ($i = 0; $i < count($n->value); $i++) {
\r
1530 if ( $n->value[$i] ) {
\r
1531 $temp = decbin($n->value[$i]);
\r
1532 $j = strlen($temp) - strrpos($temp, '1') - 1;
\r
1537 // at this point, 2^$j * $n/(2^$j) == $n
\r
1539 $mod1 = $n->copy();
\r
1540 $mod1->_rshift($j);
\r
1541 $mod2 = new Math_BigInteger();
\r
1542 $mod2->value = array(1);
\r
1543 $mod2->_lshift($j);
\r
1545 $part1 = ( $mod1->value != array(1) ) ? $this->_slidingWindow($e, $mod1, MATH_BIGINTEGER_MONTGOMERY) : new Math_BigInteger();
\r
1546 $part2 = $this->_slidingWindow($e, $mod2, MATH_BIGINTEGER_POWEROF2);
\r
1548 $y1 = $mod2->modInverse($mod1);
\r
1549 $y2 = $mod1->modInverse($mod2);
\r
1551 $result = $part1->multiply($mod2);
\r
1552 $result = $result->multiply($y1);
\r
1554 $temp = $part2->multiply($mod1);
\r
1555 $temp = $temp->multiply($y2);
\r
1557 $result = $result->add($temp);
\r
1558 list(, $result) = $result->divide($n);
\r
1560 return $this->_normalize($result);
\r
1564 * Performs modular exponentiation.
\r
1566 * Alias for Math_BigInteger::modPow()
\r
1568 * @param Math_BigInteger $e
\r
1569 * @param Math_BigInteger $n
\r
1570 * @return Math_BigInteger
\r
1573 function powMod($e, $n)
\r
1575 return $this->modPow($e, $n);
\r
1579 * Sliding Window k-ary Modular Exponentiation
\r
1581 * Based on {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=27 HAC 14.85} /
\r
1582 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=210 MPM 7.7}. In a departure from those algorithims,
\r
1583 * however, this function performs a modular reduction after every multiplication and squaring operation.
\r
1584 * As such, this function has the same preconditions that the reductions being used do.
\r
1586 * @param Math_BigInteger $e
\r
1587 * @param Math_BigInteger $n
\r
1588 * @param Integer $mode
\r
1589 * @return Math_BigInteger
\r
1592 function _slidingWindow($e, $n, $mode)
\r
1594 static $window_ranges = array(7, 25, 81, 241, 673, 1793); // from BigInteger.java's oddModPow function
\r
1595 //static $window_ranges = array(0, 7, 36, 140, 450, 1303, 3529); // from MPM 7.3.1
\r
1597 $e_length = count($e->value) - 1;
\r
1598 $e_bits = decbin($e->value[$e_length]);
\r
1599 for ($i = $e_length - 1; $i >= 0; $i--) {
\r
1600 $e_bits.= str_pad(decbin($e->value[$i]), 26, '0', STR_PAD_LEFT);
\r
1603 $e_length = strlen($e_bits);
\r
1605 // calculate the appropriate window size.
\r
1606 // $window_size == 3 if $window_ranges is between 25 and 81, for example.
\r
1607 for ($i = 0, $window_size = 1; $e_length > $window_ranges[$i] && $i < count($window_ranges); $window_size++, $i++);
\r
1609 case MATH_BIGINTEGER_MONTGOMERY:
\r
1610 $reduce = '_montgomery';
\r
1611 $prep = '_prepMontgomery';
\r
1613 case MATH_BIGINTEGER_BARRETT:
\r
1614 $reduce = '_barrett';
\r
1615 $prep = '_barrett';
\r
1617 case MATH_BIGINTEGER_POWEROF2:
\r
1618 $reduce = '_mod2';
\r
1621 case MATH_BIGINTEGER_CLASSIC:
\r
1622 $reduce = '_remainder';
\r
1623 $prep = '_remainder';
\r
1625 case MATH_BIGINTEGER_NONE:
\r
1626 // ie. do no modular reduction. useful if you want to just do pow as opposed to modPow.
\r
1631 // an invalid $mode was provided
\r
1634 // precompute $this^0 through $this^$window_size
\r
1635 $powers = array();
\r
1636 $powers[1] = $this->$prep($n);
\r
1637 $powers[2] = $powers[1]->_square();
\r
1638 $powers[2] = $powers[2]->$reduce($n);
\r
1640 // we do every other number since substr($e_bits, $i, $j+1) (see below) is supposed to end
\r
1641 // in a 1. ie. it's supposed to be odd.
\r
1642 $temp = 1 << ($window_size - 1);
\r
1643 for ($i = 1; $i < $temp; $i++) {
\r
1644 $powers[2 * $i + 1] = $powers[2 * $i - 1]->multiply($powers[2]);
\r
1645 $powers[2 * $i + 1] = $powers[2 * $i + 1]->$reduce($n);
\r
1648 $result = new Math_BigInteger();
\r
1649 $result->value = array(1);
\r
1650 $result = $result->$prep($n);
\r
1652 for ($i = 0; $i < $e_length; ) {
\r
1653 if ( !$e_bits[$i] ) {
\r
1654 $result = $result->_square();
\r
1655 $result = $result->$reduce($n);
\r
1658 for ($j = $window_size - 1; $j > 0; $j--) {
\r
1659 if ( !empty($e_bits[$i + $j]) ) {
\r
1664 for ($k = 0; $k <= $j; $k++) {// eg. the length of substr($e_bits, $i, $j+1)
\r
1665 $result = $result->_square();
\r
1666 $result = $result->$reduce($n);
\r
1669 $result = $result->multiply($powers[bindec(substr($e_bits, $i, $j + 1))]);
\r
1670 $result = $result->$reduce($n);
\r
1676 $result = $result->$reduce($n);
\r
1684 * A wrapper for the divide function.
\r
1687 * @see _slidingWindow()
\r
1689 * @param Math_BigInteger
\r
1690 * @return Math_BigInteger
\r
1692 function _remainder($n)
\r
1694 list(, $temp) = $this->divide($n);
\r
1699 * Modulos for Powers of Two
\r
1701 * Calculates $x%$n, where $n = 2**$e, for some $e. Since this is basically the same as doing $x & ($n-1),
\r
1702 * we'll just use this function as a wrapper for doing that.
\r
1704 * @see _slidingWindow()
\r
1706 * @param Math_BigInteger
\r
1707 * @return Math_BigInteger
\r
1709 function _mod2($n)
\r
1711 $temp = new Math_BigInteger();
\r
1712 $temp->value = array(1);
\r
1713 return $this->bitwise_and($n->subtract($temp));
\r
1717 * Barrett Modular Reduction
\r
1719 * See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=14 HAC 14.3.3} /
\r
1720 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=165 MPM 6.2.5} for more information. Modified slightly,
\r
1721 * so as not to require negative numbers (initially, this script didn't support negative numbers).
\r
1723 * @see _slidingWindow()
\r
1725 * @param Math_BigInteger
\r
1726 * @return Math_BigInteger
\r
1728 function _barrett($n)
\r
1730 static $cache = array(
\r
1731 MATH_BIGINTEGER_VARIABLE => array(),
\r
1732 MATH_BIGINTEGER_DATA => array()
\r
1735 $n_length = count($n->value);
\r
1737 if (count($this->value) > 2 * $n_length) {
\r
1738 list(, $temp) = $this->divide($n);
\r
1742 if ( ($key = array_search($n->value, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
\r
1743 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
\r
1744 $cache[MATH_BIGINTEGER_VARIABLE][] = $n->value;
\r
1745 $temp = new Math_BigInteger();
\r
1746 $temp->value = $this->_array_repeat(0, 2 * $n_length);
\r
1747 $temp->value[] = 1;
\r
1748 list($cache[MATH_BIGINTEGER_DATA][], ) = $temp->divide($n);
\r
1751 $temp = new Math_BigInteger();
\r
1752 $temp->value = array_slice($this->value, $n_length - 1);
\r
1753 $temp = $temp->multiply($cache[MATH_BIGINTEGER_DATA][$key]);
\r
1754 $temp->value = array_slice($temp->value, $n_length + 1);
\r
1756 $result = new Math_BigInteger();
\r
1757 $result->value = array_slice($this->value, 0, $n_length + 1);
\r
1758 $temp = $temp->_multiplyLower($n, $n_length + 1);
\r
1759 // $temp->value == array_slice($temp->multiply($n)->value, 0, $n_length + 1)
\r
1761 if ($result->compare($temp) < 0) {
\r
1762 $corrector = new Math_BigInteger();
\r
1763 $corrector->value = $this->_array_repeat(0, $n_length + 1);
\r
1764 $corrector->value[] = 1;
\r
1765 $result = $result->add($corrector);
\r
1768 $result = $result->subtract($temp);
\r
1769 while ($result->compare($n) > 0) {
\r
1770 $result = $result->subtract($n);
\r
1777 * Montgomery Modular Reduction
\r
1779 * ($this->_prepMontgomery($n))->_montgomery($n) yields $x%$n.
\r
1780 * {@link http://math.libtomcrypt.com/files/tommath.pdf#page=170 MPM 6.3} provides insights on how this can be
\r
1781 * improved upon (basically, by using the comba method). gcd($n, 2) must be equal to one for this function
\r
1782 * to work correctly.
\r
1784 * @see _prepMontgomery()
\r
1785 * @see _slidingWindow()
\r
1787 * @param Math_BigInteger
\r
1788 * @return Math_BigInteger
\r
1790 function _montgomery($n)
\r
1792 static $cache = array(
\r
1793 MATH_BIGINTEGER_VARIABLE => array(),
\r
1794 MATH_BIGINTEGER_DATA => array()
\r
1797 if ( ($key = array_search($n->value, $cache[MATH_BIGINTEGER_VARIABLE])) === false ) {
\r
1798 $key = count($cache[MATH_BIGINTEGER_VARIABLE]);
\r
1799 $cache[MATH_BIGINTEGER_VARIABLE][] = $n->value;
\r
1800 $cache[MATH_BIGINTEGER_DATA][] = $n->_modInverse67108864();
\r
1803 $k = count($n->value);
\r
1805 $result = $this->copy();
\r
1807 for ($i = 0; $i < $k; $i++) {
\r
1808 $temp = new Math_BigInteger();
\r
1809 $temp->value = array(
\r
1810 ($result->value[$i] * $cache[MATH_BIGINTEGER_DATA][$key]) & 0x3FFFFFF
\r
1813 $temp = $temp->multiply($n);
\r
1814 $temp->value = array_merge($this->_array_repeat(0, $i), $temp->value);
\r
1815 $result = $result->add($temp);
\r
1818 $result->value = array_slice($result->value, $k);
\r
1820 if ($result->compare($n) >= 0) {
\r
1821 $result = $result->subtract($n);
\r
1828 * Prepare a number for use in Montgomery Modular Reductions
\r
1830 * @see _montgomery()
\r
1831 * @see _slidingWindow()
\r
1833 * @param Math_BigInteger
\r
1834 * @return Math_BigInteger
\r
1836 function _prepMontgomery($n)
\r
1838 $k = count($n->value);
\r
1840 $temp = new Math_BigInteger();
\r
1841 $temp->value = array_merge($this->_array_repeat(0, $k), $this->value);
\r
1843 list(, $temp) = $temp->divide($n);
\r
1848 * Modular Inverse of a number mod 2**26 (eg. 67108864)
\r
1850 * Based off of the bnpInvDigit function implemented and justified in the following URL:
\r
1852 * {@link http://www-cs-students.stanford.edu/~tjw/jsbn/jsbn.js}
\r
1854 * The following URL provides more info:
\r
1856 * {@link http://groups.google.com/group/sci.crypt/msg/7a137205c1be7d85}
\r
1858 * As for why we do all the bitmasking... strange things can happen when converting from floats to ints. For
\r
1859 * instance, on some computers, var_dump((int) -4294967297) yields int(-1) and on others, it yields
\r
1860 * int(-2147483648). To avoid problems stemming from this, we use bitmasks to guarantee that ints aren't
\r
1861 * auto-converted to floats. The outermost bitmask is present because without it, there's no guarantee that
\r
1862 * the "residue" returned would be the so-called "common residue". We use fmod, in the last step, because the
\r
1863 * maximum possible $x is 26 bits and the maximum $result is 16 bits. Thus, we have to be able to handle up to
\r
1864 * 40 bits, which only 64-bit floating points will support.
\r
1866 * Thanks to Pedro Gimeno Fortea for input!
\r
1868 * @see _montgomery()
\r
1872 function _modInverse67108864() // 2**26 == 67108864
\r
1874 $x = -$this->value[0];
\r
1875 $result = $x & 0x3; // x**-1 mod 2**2
\r
1876 $result = ($result * (2 - $x * $result)) & 0xF; // x**-1 mod 2**4
\r
1877 $result = ($result * (2 - ($x & 0xFF) * $result)) & 0xFF; // x**-1 mod 2**8
\r
1878 $result = ($result * ((2 - ($x & 0xFFFF) * $result) & 0xFFFF)) & 0xFFFF; // x**-1 mod 2**16
\r
1879 $result = fmod($result * (2 - fmod($x * $result, 0x4000000)), 0x4000000); // x**-1 mod 2**26
\r
1880 return $result & 0x3FFFFFF;
\r
1884 * Calculates modular inverses.
\r
1886 * Say you have (30 mod 17 * x mod 17) mod 17 == 1. x can be found using modular inverses.
\r
1888 * Here's an example:
\r
1891 * include('Math/BigInteger.php');
\r
1893 * $a = new Math_BigInteger(30);
\r
1894 * $b = new Math_BigInteger(17);
\r
1896 * $c = $a->modInverse($b);
\r
1897 * echo $c->toString(); // outputs 4
\r
1901 * $d = $a->multiply($c);
\r
1902 * list(, $d) = $d->divide($b);
\r
1903 * echo $d; // outputs 1 (as per the definition of modular inverse)
\r
1907 * @param Math_BigInteger $n
\r
1908 * @return mixed false, if no modular inverse exists, Math_BigInteger, otherwise.
\r
1910 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=21 HAC 14.64} for more information.
\r
1912 function modInverse($n)
\r
1914 switch ( MATH_BIGINTEGER_MODE ) {
\r
1915 case MATH_BIGINTEGER_MODE_GMP:
\r
1916 $temp = new Math_BigInteger();
\r
1917 $temp->value = gmp_invert($this->value, $n->value);
\r
1919 return ( $temp->value === false ) ? false : $this->_normalize($temp);
\r
1922 static $zero, $one;
\r
1923 if (!isset($zero)) {
\r
1924 $zero = new Math_BigInteger();
\r
1925 $one = new Math_BigInteger(1);
\r
1928 // $x mod $n == $x mod -$n.
\r
1931 if ($this->compare($zero) < 0) {
\r
1932 $temp = $this->abs();
\r
1933 $temp = $temp->modInverse($n);
\r
1934 return $negated === false ? false : $this->_normalize($n->subtract($temp));
\r
1937 extract($this->extendedGCD($n));
\r
1939 if (!$gcd->equals($one)) {
\r
1943 $x = $x->compare($zero) < 0 ? $x->add($n) : $x;
\r
1945 return $this->compare($zero) < 0 ? $this->_normalize($n->subtract($x)) : $this->_normalize($x);
\r
1949 * Calculates the greatest common divisor and Bézout's identity.
\r
1951 * Say you have 693 and 609. The GCD is 21. Bézout's identity states that there exist integers x and y such that
\r
1952 * 693*x + 609*y == 21. In point of fact, there are actually an infinite number of x and y combinations and which
\r
1953 * combination is returned is dependant upon which mode is in use. See
\r
1954 * {@link http://en.wikipedia.org/wiki/B%C3%A9zout%27s_identity Bézout's identity - Wikipedia} for more information.
\r
1956 * Here's an example:
\r
1959 * include('Math/BigInteger.php');
\r
1961 * $a = new Math_BigInteger(693);
\r
1962 * $b = new Math_BigInteger(609);
\r
1964 * extract($a->extendedGCD($b));
\r
1966 * echo $gcd->toString() . "\r\n"; // outputs 21
\r
1967 * echo $a->toString() * $x->toString() + $b->toString() * $y->toString(); // outputs 21
\r
1971 * @param Math_BigInteger $n
\r
1972 * @return Math_BigInteger
\r
1974 * @internal Calculates the GCD using the binary xGCD algorithim described in
\r
1975 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap14.pdf#page=19 HAC 14.61}. As the text above 14.61 notes,
\r
1976 * the more traditional algorithim requires "relatively costly multiple-precision divisions".
\r
1978 function extendedGCD($n) {
\r
1979 switch ( MATH_BIGINTEGER_MODE ) {
\r
1980 case MATH_BIGINTEGER_MODE_GMP:
\r
1981 extract(gmp_gcdext($this->value, $n->value));
\r
1984 'gcd' => $this->_normalize(new Math_BigInteger($g)),
\r
1985 'x' => $this->_normalize(new Math_BigInteger($s)),
\r
1986 'y' => $this->_normalize(new Math_BigInteger($t))
\r
1988 case MATH_BIGINTEGER_MODE_BCMATH:
\r
1989 // it might be faster to use the binary xGCD algorithim here, as well, but (1) that algorithim works
\r
1990 // best when the base is a power of 2 and (2) i don't think it'd make much difference, anyway. as is,
\r
1991 // the basic extended euclidean algorithim is what we're using.
\r
1993 $u = $this->value;
\r
2001 while (bccomp($v, '0') != 0) {
\r
2002 $q = bcdiv($u, $v);
\r
2006 $v = bcsub($temp, bcmul($v, $q));
\r
2010 $c = bcsub($temp, bcmul($a, $q));
\r
2014 $d = bcsub($temp, bcmul($b, $q));
\r
2018 'gcd' => $this->_normalize(new Math_BigInteger($u)),
\r
2019 'x' => $this->_normalize(new Math_BigInteger($a)),
\r
2020 'y' => $this->_normalize(new Math_BigInteger($b))
\r
2025 $x = $this->copy();
\r
2026 $g = new Math_BigInteger();
\r
2027 $g->value = array(1);
\r
2029 while ( !(($x->value[0] & 1)|| ($y->value[0] & 1)) ) {
\r
2038 $a = new Math_BigInteger();
\r
2039 $b = new Math_BigInteger();
\r
2040 $c = new Math_BigInteger();
\r
2041 $d = new Math_BigInteger();
\r
2043 $a->value = $d->value = $g->value = array(1);
\r
2045 while ( !empty($u->value) ) {
\r
2046 while ( !($u->value[0] & 1) ) {
\r
2048 if ( ($a->value[0] & 1) || ($b->value[0] & 1) ) {
\r
2050 $b = $b->subtract($x);
\r
2056 while ( !($v->value[0] & 1) ) {
\r
2058 if ( ($c->value[0] & 1) || ($d->value[0] & 1) ) {
\r
2060 $d = $d->subtract($x);
\r
2066 if ($u->compare($v) >= 0) {
\r
2067 $u = $u->subtract($v);
\r
2068 $a = $a->subtract($c);
\r
2069 $b = $b->subtract($d);
\r
2071 $v = $v->subtract($u);
\r
2072 $c = $c->subtract($a);
\r
2073 $d = $d->subtract($b);
\r
2078 'gcd' => $this->_normalize($g->multiply($v)),
\r
2079 'x' => $this->_normalize($c),
\r
2080 'y' => $this->_normalize($d)
\r
2085 * Calculates the greatest common divisor
\r
2087 * Say you have 693 and 609. The GCD is 21.
\r
2089 * Here's an example:
\r
2092 * include('Math/BigInteger.php');
\r
2094 * $a = new Math_BigInteger(693);
\r
2095 * $b = new Math_BigInteger(609);
\r
2097 * $gcd = a->extendedGCD($b);
\r
2099 * echo $gcd->toString() . "\r\n"; // outputs 21
\r
2103 * @param Math_BigInteger $n
\r
2104 * @return Math_BigInteger
\r
2109 extract($this->extendedGCD($n));
\r
2116 * @return Math_BigInteger
\r
2121 $temp = new Math_BigInteger();
\r
2123 switch ( MATH_BIGINTEGER_MODE ) {
\r
2124 case MATH_BIGINTEGER_MODE_GMP:
\r
2125 $temp->value = gmp_abs($this->value);
\r
2127 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2128 $temp->value = (bccomp($this->value, '0') < 0) ? substr($this->value, 1) : $this->value;
\r
2131 $temp->value = $this->value;
\r
2138 * Compares two numbers.
\r
2140 * Although one might think !$x->compare($y) means $x != $y, it, in fact, means the opposite. The reason for this is
\r
2141 * demonstrated thusly:
\r
2143 * $x > $y: $x->compare($y) > 0
\r
2144 * $x < $y: $x->compare($y) < 0
\r
2145 * $x == $y: $x->compare($y) == 0
\r
2147 * Note how the same comparison operator is used. If you want to test for equality, use $x->equals($y).
\r
2149 * @param Math_BigInteger $x
\r
2150 * @return Integer < 0 if $this is less than $x; > 0 if $this is greater than $x, and 0 if they are equal.
\r
2153 * @internal Could return $this->sub($x), but that's not as fast as what we do do.
\r
2155 function compare($y)
\r
2157 switch ( MATH_BIGINTEGER_MODE ) {
\r
2158 case MATH_BIGINTEGER_MODE_GMP:
\r
2159 return gmp_cmp($this->value, $y->value);
\r
2160 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2161 return bccomp($this->value, $y->value);
\r
2164 $x = $this->_normalize($this->copy());
\r
2165 $y = $this->_normalize($y);
\r
2167 if ( $x->is_negative != $y->is_negative ) {
\r
2168 return ( !$x->is_negative && $y->is_negative ) ? 1 : -1;
\r
2171 $result = $x->is_negative ? -1 : 1;
\r
2173 if ( count($x->value) != count($y->value) ) {
\r
2174 return ( count($x->value) > count($y->value) ) ? $result : -$result;
\r
2177 for ($i = count($x->value) - 1; $i >= 0; $i--) {
\r
2178 if ($x->value[$i] != $y->value[$i]) {
\r
2179 return ( $x->value[$i] > $y->value[$i] ) ? $result : -$result;
\r
2187 * Tests the equality of two numbers.
\r
2189 * If you need to see if one number is greater than or less than another number, use Math_BigInteger::compare()
\r
2191 * @param Math_BigInteger $x
\r
2196 function equals($x)
\r
2198 switch ( MATH_BIGINTEGER_MODE ) {
\r
2199 case MATH_BIGINTEGER_MODE_GMP:
\r
2200 return gmp_cmp($this->value, $x->value) == 0;
\r
2202 return $this->value == $x->value && $this->is_negative == $x->is_negative;
\r
2209 * Some bitwise operations give different results depending on the precision being used. Examples include left
\r
2210 * shift, not, and rotates.
\r
2212 * @param Math_BigInteger $x
\r
2214 * @return Math_BigInteger
\r
2216 function setPrecision($bits)
\r
2218 $this->precision = $bits;
\r
2219 if ( MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ) {
\r
2220 $this->bitmask = new Math_BigInteger(chr((1 << ($bits & 0x7)) - 1) . str_repeat(chr(0xFF), $bits >> 3), 256);
\r
2222 $this->bitmask = new Math_BigInteger(bcpow('2', $bits));
\r
2229 * @param Math_BigInteger $x
\r
2231 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2232 * @return Math_BigInteger
\r
2234 function bitwise_and($x)
\r
2236 switch ( MATH_BIGINTEGER_MODE ) {
\r
2237 case MATH_BIGINTEGER_MODE_GMP:
\r
2238 $temp = new Math_BigInteger();
\r
2239 $temp->value = gmp_and($this->value, $x->value);
\r
2241 return $this->_normalize($temp);
\r
2242 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2243 $left = $this->toBytes();
\r
2244 $right = $x->toBytes();
\r
2246 $length = max(strlen($left), strlen($right));
\r
2248 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
\r
2249 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
\r
2251 return $this->_normalize(new Math_BigInteger($left & $right, 256));
\r
2254 $result = $this->copy();
\r
2256 $length = min(count($x->value), count($this->value));
\r
2258 $result->value = array_slice($result->value, 0, $length);
\r
2260 for ($i = 0; $i < $length; $i++) {
\r
2261 $result->value[$i] = $result->value[$i] & $x->value[$i];
\r
2264 return $this->_normalize($result);
\r
2270 * @param Math_BigInteger $x
\r
2272 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2273 * @return Math_BigInteger
\r
2275 function bitwise_or($x)
\r
2277 switch ( MATH_BIGINTEGER_MODE ) {
\r
2278 case MATH_BIGINTEGER_MODE_GMP:
\r
2279 $temp = new Math_BigInteger();
\r
2280 $temp->value = gmp_or($this->value, $x->value);
\r
2282 return $this->_normalize($temp);
\r
2283 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2284 $left = $this->toBytes();
\r
2285 $right = $x->toBytes();
\r
2287 $length = max(strlen($left), strlen($right));
\r
2289 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
\r
2290 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
\r
2292 return $this->_normalize(new Math_BigInteger($left | $right, 256));
\r
2295 $length = max(count($this->value), count($x->value));
\r
2296 $result = $this->copy();
\r
2297 $result->value = array_pad($result->value, 0, $length);
\r
2298 $x->value = array_pad($x->value, 0, $length);
\r
2300 for ($i = 0; $i < $length; $i++) {
\r
2301 $result->value[$i] = $this->value[$i] | $x->value[$i];
\r
2304 return $this->_normalize($result);
\r
2308 * Logical Exclusive-Or
\r
2310 * @param Math_BigInteger $x
\r
2312 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2313 * @return Math_BigInteger
\r
2315 function bitwise_xor($x)
\r
2317 switch ( MATH_BIGINTEGER_MODE ) {
\r
2318 case MATH_BIGINTEGER_MODE_GMP:
\r
2319 $temp = new Math_BigInteger();
\r
2320 $temp->value = gmp_xor($this->value, $x->value);
\r
2322 return $this->_normalize($temp);
\r
2323 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2324 $left = $this->toBytes();
\r
2325 $right = $x->toBytes();
\r
2327 $length = max(strlen($left), strlen($right));
\r
2329 $left = str_pad($left, $length, chr(0), STR_PAD_LEFT);
\r
2330 $right = str_pad($right, $length, chr(0), STR_PAD_LEFT);
\r
2332 return $this->_normalize(new Math_BigInteger($left ^ $right, 256));
\r
2335 $length = max(count($this->value), count($x->value));
\r
2336 $result = $this->copy();
\r
2337 $result->value = array_pad($result->value, 0, $length);
\r
2338 $x->value = array_pad($x->value, 0, $length);
\r
2340 for ($i = 0; $i < $length; $i++) {
\r
2341 $result->value[$i] = $this->value[$i] ^ $x->value[$i];
\r
2344 return $this->_normalize($result);
\r
2351 * @internal Implemented per a request by Lluis Pamies i Juarez <lluis _a_ pamies.cat>
\r
2352 * @return Math_BigInteger
\r
2354 function bitwise_not()
\r
2356 // calculuate "not" without regard to $this->precision
\r
2357 // (will always result in a smaller number. ie. ~1 isn't 1111 1110 - it's 0)
\r
2358 $temp = $this->toBytes();
\r
2359 $pre_msb = decbin(ord($temp[0]));
\r
2361 $msb = decbin(ord($temp[0]));
\r
2362 if (strlen($msb) == 8) {
\r
2363 $msb = substr($msb, strpos($msb, '0'));
\r
2365 $temp[0] = chr(bindec($msb));
\r
2367 // see if we need to add extra leading 1's
\r
2368 $current_bits = strlen($pre_msb) + 8 * strlen($temp) - 8;
\r
2369 $new_bits = $this->precision - $current_bits;
\r
2370 if ($new_bits <= 0) {
\r
2371 return $this->_normalize(new Math_BigInteger($temp, 256));
\r
2374 // generate as many leading 1's as we need to.
\r
2375 $leading_ones = chr((1 << ($new_bits & 0x7)) - 1) . str_repeat(chr(0xFF), $new_bits >> 3);
\r
2376 $this->_base256_lshift($leading_ones, $current_bits);
\r
2378 $temp = str_pad($temp, ceil($this->bits / 8), chr(0), STR_PAD_LEFT);
\r
2380 return $this->_normalize(new Math_BigInteger($leading_ones | $temp, 256));
\r
2384 * Logical Right Shift
\r
2386 * Shifts BigInteger's by $shift bits, effectively dividing by 2**$shift.
\r
2388 * @param Integer $shift
\r
2389 * @return Math_BigInteger
\r
2391 * @internal The only version that yields any speed increases is the internal version.
\r
2393 function bitwise_rightShift($shift)
\r
2395 $temp = new Math_BigInteger();
\r
2397 switch ( MATH_BIGINTEGER_MODE ) {
\r
2398 case MATH_BIGINTEGER_MODE_GMP:
\r
2401 if (empty($two)) {
\r
2402 $two = gmp_init('2');
\r
2405 $temp->value = gmp_div_q($this->value, gmp_pow($two, $shift));
\r
2408 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2409 $temp->value = bcdiv($this->value, bcpow('2', $shift));
\r
2412 default: // could just replace _lshift with this, but then all _lshift() calls would need to be rewritten
\r
2413 // and I don't want to do that...
\r
2414 $temp->value = $this->value;
\r
2415 $temp->_rshift($shift);
\r
2418 return $this->_normalize($temp);
\r
2422 * Logical Left Shift
\r
2424 * Shifts BigInteger's by $shift bits, effectively multiplying by 2**$shift.
\r
2426 * @param Integer $shift
\r
2427 * @return Math_BigInteger
\r
2429 * @internal The only version that yields any speed increases is the internal version.
\r
2431 function bitwise_leftShift($shift)
\r
2433 $temp = new Math_BigInteger();
\r
2435 switch ( MATH_BIGINTEGER_MODE ) {
\r
2436 case MATH_BIGINTEGER_MODE_GMP:
\r
2439 if (empty($two)) {
\r
2440 $two = gmp_init('2');
\r
2443 $temp->value = gmp_mul($this->value, gmp_pow($two, $shift));
\r
2446 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2447 $temp->value = bcmul($this->value, bcpow('2', $shift));
\r
2450 default: // could just replace _rshift with this, but then all _lshift() calls would need to be rewritten
\r
2451 // and I don't want to do that...
\r
2452 $temp->value = $this->value;
\r
2453 $temp->_lshift($shift);
\r
2456 return $this->_normalize($temp);
\r
2460 * Logical Left Rotate
\r
2462 * Instead of the top x bits being dropped they're appended to the shifted bit string.
\r
2464 * @param Integer $shift
\r
2465 * @return Math_BigInteger
\r
2468 function bitwise_leftRotate($shift)
\r
2470 $bits = $this->toBytes();
\r
2472 if ($this->precision > 0) {
\r
2473 $precision = $this->precision;
\r
2474 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
\r
2475 $mask = $this->bitmask->subtract(new Math_BigInteger(1));
\r
2476 $mask = $mask->toBytes();
\r
2478 $mask = $this->bitmask->toBytes();
\r
2481 $temp = ord($bits[0]);
\r
2482 for ($i = 0; $temp >> $i; $i++);
\r
2483 $precision = 8 * strlen($bits) - 8 + $i;
\r
2484 $mask = chr((1 << ($precision & 0x7)) - 1) . str_repeat(chr(0xFF), $precision >> 3);
\r
2488 $shift+= $precision;
\r
2490 $shift%= $precision;
\r
2493 return $this->copy();
\r
2496 $left = $this->bitwise_leftShift($shift);
\r
2497 $left = $left->bitwise_and(new Math_BigInteger($mask, 256));
\r
2498 $right = $this->bitwise_rightShift($precision - $shift);
\r
2499 $result = MATH_BIGINTEGER_MODE != MATH_BIGINTEGER_MODE_BCMATH ? $left->bitwise_or($right) : $left->add($right);
\r
2500 return $this->_normalize($result);
\r
2504 * Logical Right Rotate
\r
2506 * Instead of the bottom x bits being dropped they're prepended to the shifted bit string.
\r
2508 * @param Integer $shift
\r
2509 * @return Math_BigInteger
\r
2512 function bitwise_rightRotate($shift)
\r
2514 return $this->bitwise_leftRotate(-$shift);
\r
2518 * Set random number generator function
\r
2520 * $generator should be the name of a random generating function whose first parameter is the minimum
\r
2521 * value and whose second parameter is the maximum value. If this function needs to be seeded, it should
\r
2522 * be seeded prior to calling Math_BigInteger::random() or Math_BigInteger::randomPrime()
\r
2524 * If the random generating function is not explicitly set, it'll be assumed to be mt_rand().
\r
2527 * @see randomPrime()
\r
2528 * @param optional String $generator
\r
2531 function setRandomGenerator($generator)
\r
2533 $this->generator = $generator;
\r
2537 * Generate a random number
\r
2539 * @param optional Integer $min
\r
2540 * @param optional Integer $max
\r
2541 * @return Math_BigInteger
\r
2544 function random($min = false, $max = false)
\r
2546 if ($min === false) {
\r
2547 $min = new Math_BigInteger(0);
\r
2550 if ($max === false) {
\r
2551 $max = new Math_BigInteger(0x7FFFFFFF);
\r
2554 $compare = $max->compare($min);
\r
2557 return $this->_normalize($min);
\r
2558 } else if ($compare < 0) {
\r
2559 // if $min is bigger then $max, swap $min and $max
\r
2565 $generator = $this->generator;
\r
2567 $max = $max->subtract($min);
\r
2568 $max = ltrim($max->toBytes(), chr(0));
\r
2569 $size = strlen($max) - 1;
\r
2572 $bytes = $size & 1;
\r
2573 for ($i = 0; $i < $bytes; $i++) {
\r
2574 $random.= chr($generator(0, 255));
\r
2577 $blocks = $size >> 1;
\r
2578 for ($i = 0; $i < $blocks; $i++) {
\r
2579 // mt_rand(-2147483648, 0x7FFFFFFF) always produces -2147483648 on some systems
\r
2580 $random.= pack('n', $generator(0, 0xFFFF));
\r
2583 $temp = new Math_BigInteger($random, 256);
\r
2584 if ($temp->compare(new Math_BigInteger(substr($max, 1), 256)) > 0) {
\r
2585 $random = chr($generator(0, ord($max[0]) - 1)) . $random;
\r
2587 $random = chr($generator(0, ord($max[0]) )) . $random;
\r
2590 $random = new Math_BigInteger($random, 256);
\r
2592 return $this->_normalize($random->add($min));
\r
2596 * Generate a random prime number.
\r
2598 * If there's not a prime within the given range, false will be returned. If more than $timeout seconds have elapsed,
\r
2599 * give up and return false.
\r
2601 * @param optional Integer $min
\r
2602 * @param optional Integer $max
\r
2603 * @param optional Integer $timeout
\r
2604 * @return Math_BigInteger
\r
2606 * @internal See {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=15 HAC 4.44}.
\r
2608 function randomPrime($min = false, $max = false, $timeout = false)
\r
2610 // gmp_nextprime() requires PHP 5 >= 5.2.0 per <http://php.net/gmp-nextprime>.
\r
2611 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_GMP && function_exists('gmp_nextprime') ) {
\r
2612 // we don't rely on Math_BigInteger::random()'s min / max when gmp_nextprime() is being used since this function
\r
2613 // does its own checks on $max / $min when gmp_nextprime() is used. When gmp_nextprime() is not used, however,
\r
2614 // the same $max / $min checks are not performed.
\r
2615 if ($min === false) {
\r
2616 $min = new Math_BigInteger(0);
\r
2619 if ($max === false) {
\r
2620 $max = new Math_BigInteger(0x7FFFFFFF);
\r
2623 $compare = $max->compare($min);
\r
2627 } else if ($compare < 0) {
\r
2628 // if $min is bigger then $max, swap $min and $max
\r
2634 $x = $this->random($min, $max);
\r
2636 $x->value = gmp_nextprime($x->value);
\r
2638 if ($x->compare($max) <= 0) {
\r
2642 $x->value = gmp_nextprime($min->value);
\r
2644 if ($x->compare($max) <= 0) {
\r
2651 $repeat1 = $repeat2 = array();
\r
2653 $one = new Math_BigInteger(1);
\r
2654 $two = new Math_BigInteger(2);
\r
2659 if ($timeout !== false && time() - $start > $timeout) {
\r
2663 $x = $this->random($min, $max);
\r
2664 if ($x->equals($two)) {
\r
2668 // make the number odd
\r
2669 switch ( MATH_BIGINTEGER_MODE ) {
\r
2670 case MATH_BIGINTEGER_MODE_GMP:
\r
2671 gmp_setbit($x->value, 0);
\r
2673 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2674 if ($x->value[strlen($x->value) - 1] % 2 == 0) {
\r
2675 $x = $x->add($one);
\r
2679 $x->value[0] |= 1;
\r
2682 // if we've seen this number twice before, assume there are no prime numbers within the given range
\r
2683 if (in_array($x->value, $repeat1)) {
\r
2684 if (in_array($x->value, $repeat2)) {
\r
2687 $repeat2[] = $x->value;
\r
2690 $repeat1[] = $x->value;
\r
2692 } while (!$x->isPrime());
\r
2698 * Checks a numer to see if it's prime
\r
2700 * Assuming the $t parameter is not set, this functoin has an error rate of 2**-80. The main motivation for the
\r
2701 * $t parameter is distributability. Math_BigInteger::randomPrime() can be distributed accross multiple pageloads
\r
2702 * on a website instead of just one.
\r
2704 * @param optional Integer $t
\r
2707 * @internal Uses the
\r
2708 * {@link http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test Miller
\96Rabin primality test}. See
\r
2709 * {@link http://www.cacr.math.uwaterloo.ca/hac/about/chap4.pdf#page=8 HAC 4.24}.
\r
2711 function isPrime($t = false)
\r
2713 $length = strlen($this->toBytes());
\r
2716 // see HAC 4.49 "Note (controlling the error probability)"
\r
2717 if ($length >= 163) { $t = 2; } // floor(1300 / 8)
\r
2718 else if ($length >= 106) { $t = 3; } // floor( 850 / 8)
\r
2719 else if ($length >= 81 ) { $t = 4; } // floor( 650 / 8)
\r
2720 else if ($length >= 68 ) { $t = 5; } // floor( 550 / 8)
\r
2721 else if ($length >= 56 ) { $t = 6; } // floor( 450 / 8)
\r
2722 else if ($length >= 50 ) { $t = 7; } // floor( 400 / 8)
\r
2723 else if ($length >= 43 ) { $t = 8; } // floor( 350 / 8)
\r
2724 else if ($length >= 37 ) { $t = 9; } // floor( 300 / 8)
\r
2725 else if ($length >= 31 ) { $t = 12; } // floor( 250 / 8)
\r
2726 else if ($length >= 25 ) { $t = 15; } // floor( 200 / 8)
\r
2727 else if ($length >= 18 ) { $t = 18; } // floor( 150 / 8)
\r
2731 // ie. gmp_testbit($this, 0)
\r
2732 // ie. isEven() or !isOdd()
\r
2733 switch ( MATH_BIGINTEGER_MODE ) {
\r
2734 case MATH_BIGINTEGER_MODE_GMP:
\r
2735 return gmp_prob_prime($this->value, $t) != 0;
\r
2736 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2737 if ($this->value == '2') {
\r
2740 if ($this->value[strlen($this->value) - 1] % 2 == 0) {
\r
2745 if ($this->value == array(2)) {
\r
2748 if (~$this->value[0] & 1) {
\r
2753 static $primes, $zero, $one, $two;
\r
2755 if (!isset($primes)) {
\r
2757 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
\r
2758 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137,
\r
2759 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227,
\r
2760 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
\r
2761 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419,
\r
2762 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509,
\r
2763 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617,
\r
2764 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727,
\r
2765 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829,
\r
2766 839, 853, 857, 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947,
\r
2767 953, 967, 971, 977, 983, 991, 997
\r
2770 for ($i = 0; $i < count($primes); $i++) {
\r
2771 $primes[$i] = new Math_BigInteger($primes[$i]);
\r
2774 $zero = new Math_BigInteger();
\r
2775 $one = new Math_BigInteger(1);
\r
2776 $two = new Math_BigInteger(2);
\r
2779 // see HAC 4.4.1 "Random search for probable primes"
\r
2780 for ($i = 0; $i < count($primes); $i++) {
\r
2781 list(, $r) = $this->divide($primes[$i]);
\r
2782 if ($r->equals($zero)) {
\r
2787 $n = $this->copy();
\r
2788 $n_1 = $n->subtract($one);
\r
2789 $n_2 = $n->subtract($two);
\r
2791 $r = $n_1->copy();
\r
2792 // ie. $s = gmp_scan1($n, 0) and $r = gmp_div_q($n, gmp_pow(gmp_init('2'), $s));
\r
2793 if ( MATH_BIGINTEGER_MODE == MATH_BIGINTEGER_MODE_BCMATH ) {
\r
2795 while ($r->value[strlen($r->value) - 1] % 2 == 0) {
\r
2796 $r->value = bcdiv($r->value, 2);
\r
2800 for ($i = 0; $i < count($r->value); $i++) {
\r
2801 $temp = ~$r->value[$i] & 0xFFFFFF;
\r
2802 for ($j = 1; ($temp >> $j) & 1; $j++);
\r
2807 $s = 26 * $i + $j - 1;
\r
2811 for ($i = 0; $i < $t; $i++) {
\r
2812 $a = new Math_BigInteger();
\r
2813 $a = $a->random($two, $n_2);
\r
2814 $y = $a->modPow($r, $n);
\r
2816 if (!$y->equals($one) && !$y->equals($n_1)) {
\r
2817 for ($j = 1; $j < $s && !$y->equals($n_1); $j++) {
\r
2818 $y = $y->modPow($two, $n);
\r
2819 if ($y->equals($one)) {
\r
2824 if (!$y->equals($n_1)) {
\r
2833 * Logical Left Shift
\r
2835 * Shifts BigInteger's by $shift bits.
\r
2837 * @param Integer $shift
\r
2840 function _lshift($shift)
\r
2842 if ( $shift == 0 ) {
\r
2846 $num_digits = floor($shift / 26);
\r
2848 $shift = 1 << $shift;
\r
2852 for ($i = 0; $i < count($this->value); $i++) {
\r
2853 $temp = $this->value[$i] * $shift + $carry;
\r
2854 $carry = floor($temp / 0x4000000);
\r
2855 $this->value[$i] = $temp - $carry * 0x4000000;
\r
2859 $this->value[] = $carry;
\r
2862 while ($num_digits--) {
\r
2863 array_unshift($this->value, 0);
\r
2868 * Logical Right Shift
\r
2870 * Shifts BigInteger's by $shift bits.
\r
2872 * @param Integer $shift
\r
2875 function _rshift($shift)
\r
2877 if ($shift == 0) {
\r
2881 $num_digits = floor($shift / 26);
\r
2883 $carry_shift = 26 - $shift;
\r
2884 $carry_mask = (1 << $shift) - 1;
\r
2886 if ( $num_digits ) {
\r
2887 $this->value = array_slice($this->value, $num_digits);
\r
2892 for ($i = count($this->value) - 1; $i >= 0; $i--) {
\r
2893 $temp = $this->value[$i] >> $shift | $carry;
\r
2894 $carry = ($this->value[$i] & $carry_mask) << $carry_shift;
\r
2895 $this->value[$i] = $temp;
\r
2902 * Deletes leading zeros and truncates (if necessary) to maintain the appropriate precision
\r
2904 * @return Math_BigInteger
\r
2907 function _normalize($result)
\r
2909 $result->precision = $this->precision;
\r
2910 $result->bitmask = $this->bitmask;
\r
2912 switch ( MATH_BIGINTEGER_MODE ) {
\r
2913 case MATH_BIGINTEGER_MODE_GMP:
\r
2914 if (!empty($result->bitmask->value)) {
\r
2915 $result->value = gmp_and($result->value, $result->bitmask->value);
\r
2919 case MATH_BIGINTEGER_MODE_BCMATH:
\r
2920 if (!empty($result->bitmask->value)) {
\r
2921 $result->value = bcmod($result->value, $result->bitmask->value);
\r
2927 if ( !count($result->value) ) {
\r
2931 for ($i = count($result->value) - 1; $i >= 0; $i--) {
\r
2932 if ( $result->value[$i] ) {
\r
2935 unset($result->value[$i]);
\r
2938 if (!empty($result->bitmask->value)) {
\r
2939 $length = min(count($result->value), count($this->bitmask->value));
\r
2940 $result->value = array_slice($result->value, 0, $length);
\r
2942 for ($i = 0; $i < $length; $i++) {
\r
2943 $result->value[$i] = $result->value[$i] & $this->bitmask->value[$i];
\r
2953 * @param $input Array
\r
2954 * @param $multiplier mixed
\r
2958 function _array_repeat($input, $multiplier)
\r
2960 return ($multiplier) ? array_fill(0, $multiplier, $input) : array();
\r
2964 * Logical Left Shift
\r
2966 * Shifts binary strings $shift bits, essentially multiplying by 2**$shift.
\r
2968 * @param $x String
\r
2969 * @param $shift Integer
\r
2973 function _base256_lshift(&$x, $shift)
\r
2975 if ($shift == 0) {
\r
2979 $num_bytes = $shift >> 3; // eg. floor($shift/8)
\r
2980 $shift &= 7; // eg. $shift % 8
\r
2983 for ($i = strlen($x) - 1; $i >= 0; $i--) {
\r
2984 $temp = ord($x[$i]) << $shift | $carry;
\r
2985 $x[$i] = chr($temp);
\r
2986 $carry = $temp >> 8;
\r
2988 $carry = ($carry != 0) ? chr($carry) : '';
\r
2989 $x = $carry . $x . str_repeat(chr(0), $num_bytes);
\r
2993 * Logical Right Shift
\r
2995 * Shifts binary strings $shift bits, essentially dividing by 2**$shift and returning the remainder.
\r
2997 * @param $x String
\r
2998 * @param $shift Integer
\r
3002 function _base256_rshift(&$x, $shift)
\r
3004 if ($shift == 0) {
\r
3005 $x = ltrim($x, chr(0));
\r
3009 $num_bytes = $shift >> 3; // eg. floor($shift/8)
\r
3010 $shift &= 7; // eg. $shift % 8
\r
3014 $start = $num_bytes > strlen($x) ? -strlen($x) : -$num_bytes;
\r
3015 $remainder = substr($x, $start);
\r
3016 $x = substr($x, 0, -$num_bytes);
\r
3020 $carry_shift = 8 - $shift;
\r
3021 for ($i = 0; $i < strlen($x); $i++) {
\r
3022 $temp = (ord($x[$i]) >> $shift) | $carry;
\r
3023 $carry = (ord($x[$i]) << $carry_shift) & 0xFF;
\r
3024 $x[$i] = chr($temp);
\r
3026 $x = ltrim($x, chr(0));
\r
3028 $remainder = chr($carry >> $carry_shift) . $remainder;
\r
3030 return ltrim($remainder, chr(0));
\r
3033 // one quirk about how the following functions are implemented is that PHP defines N to be an unsigned long
\r
3034 // at 32-bits, while java's longs are 64-bits.
\r
3037 * Converts 32-bit integers to bytes.
\r
3039 * @param Integer $x
\r
3043 function _int2bytes($x)
\r
3045 return ltrim(pack('N', $x), chr(0));
\r
3049 * Converts bytes to 32-bit integers
\r
3051 * @param String $x
\r
3055 function _bytes2int($x)
\r
3057 $temp = unpack('Nint', str_pad($x, 4, chr(0), STR_PAD_LEFT));
\r
3058 return $temp['int'];
\r
projects / quix0rs-gnu-social.git / blob