worker / lib / PHPSecLib / Math / BigInteger.php

BigInteger.php in ManageWP Worker 3.9.28, at lib/PHPSecLib/Math/BigInteger.php

3,651 lines 124.4 KB

Raw Download Zip

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