contact-forms / phpseclib-crypt / BigInteger.php

BigInteger.php in Contact Forms by Cimatti 1.9.2, at phpseclib-crypt/BigInteger.php

3,813 lines 130.8 KB

Raw Download Zip

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