contact-forms / phpseclib-crypt / BigInteger.php

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

3,820 lines 131.1 KB

Raw Download Zip

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