defender-security / extra / hub-connector / lib / PHPSecLib / Math / BigInteger.php

BigInteger.php in Defender Security – Malware Scanner, Login Security & Firewall 6.3.0, at extra/hub-connector/lib/PHPSecLib/Math/BigInteger.php

3,923 lines 130.9 KB

Raw Download Zip

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