loginizer / IPv6 / BigInteger.php

BigInteger.php in Loginizer 1.3.3, at IPv6/BigInteger.php

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