loginizer / IPv6 / BigInteger.php

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

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