worker / src / PHPSecLib / Math / BigInteger.php

BigInteger.php in ManageWP Worker 4.9.25, at src/PHPSecLib/Math/BigInteger.php

3,877 lines 128.3 KB

Raw Download Zip

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