Mistpark/phpsec/math.html

157 lines
17 KiB
HTML
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
<html xmlns="http://www.w3.org/1999/xhtml"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8" /><title>Chapter 2. Math</title><link rel="stylesheet" href="docbook.css" type="text/css" /><meta name="generator" content="DocBook XSL Stylesheets V1.73.2" /><link rel="start" href="index.html" title="PHP Secure Communications Library" /><link rel="up" href="index.html" title="PHP Secure Communications Library" /><link rel="prev" href="intro.html" title="Chapter 1. Introduction" /><link rel="next" href="sym_crypt.html" title="Chapter 3. Symmetric-key Cryptography" /></head><body><div class="navheader"><table width="100%" summary="Navigation header"><tr><th colspan="3" align="center">Chapter 2. Math</th></tr><tr><td width="20%" align="left"><a accesskey="p" href="intro.html">Prev</a> </td><th width="60%" align="center"> </th><td width="20%" align="right"> <a accesskey="n" href="sym_crypt.html">Next</a></td></tr></table><hr /></div><div class="chapter" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title"><a id="math"></a>Chapter 2. Math</h2></div></div></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="section"><a href="math.html#math_biginteger">2.1. Math_BigInteger</a></span></dt><dd><dl><dt><span class="section"><a href="math.html#math_biginteger_dependencies">2.1.1. Dependencies</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_constructor">2.1.2. The constructor</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_output">2.1.3. toString(), toBytes(), toHex() and toBits()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_fourfunctions">2.1.4. add(), subtract(), multiply() and divide()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_modulo">2.1.5. powMod() and modInverse()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_gcd">2.1.6. gcd() and extendedGCD()</a></span></dt><dt><span class="section"><a href="math.html#math_abs">2.1.7. abs()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_compare">2.1.8. equals() and compare()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_precision">2.1.9. setPrecision()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_bitwise">2.1.10. bitwise_and(), bitwise_or(), bitwise_xor() and bitwise_not()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_shifts">2.1.11. bitwise_rightShift() and bitwise_leftShift()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_rotates">2.1.12. bitwise_rightRotate() and bitwise_leftRotate()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_setrandom">2.1.13. setRandomGenerator()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_prime">2.1.14. isPrime()</a></span></dt><dt><span class="section"><a href="math.html#math_biginteger_random">2.1.15. random() and randomPrime()</a></span></dt></dl></dd></dl></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a id="math_biginteger"></a>2.1. Math_BigInteger</h2></div></div></div><p>
Implements an arbitrary precision integer arithmetic library. Uses gmp or bcmath, if available, and an
internal implementation, otherwise. Here's an example:
</p><pre class="programlisting">&lt;?php
include('Math/BigInteger.php');
$a = new Math_BigInteger(2);
$b = new Math_BigInteger(3);
$c = $a-&gt;add($b);
echo $c-&gt;toString(); // outputs 5
?&gt;</pre><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_dependencies"></a>2.1.1. Dependencies</h3></div></div></div><p>
If you're running PHP 5, Math_BigInteger's only dependancy is the PCRE extension (which is enabled by default). Math_BigInteger also works on PHP 4 if PHP/Compat/Function/array_fill.php and PHP/Compat/Function/bcpowmod.php are included.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_constructor"></a>2.1.2. The constructor</h3></div></div></div><p>
The constructor takes two parameters. The first is the number and the second represents the base. Both
are optional (if they're not provided, the Math_BigInteger object will assume a value of 0).
</p><p>
The supported bases are base-2, base-10 (default), base-16, and base-256. To set $a, in the
above example, to 2, using base-2, we'd do <code class="code">new Math_BigInteger('10', 2)</code>. To do it using
base-16, you could do <code class="code">new Math_BigInteger('2', 16)</code> or <code class="code">new Math_BigInteger('0x2', 16)</code>.
To set it to 2 using base-256, you'd do <code class="code">new Math_BigInteger(chr(2), 256)</code>.
</p><p>
If the base is negative (eg. -256), two's compliment will be used. Thus, <code class="code">new Math_BigInteger(chr(0xFF), -256)</code>
is equal to -1, as is <code class="code">new Math_BigInteger('0xFFFFFFFF', -16)</code> and <code class="code">new Math_BigInteger('11', -2)</code>.
Basically, if the leading bit is 1, the number is assumed to be negative.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_output"></a>2.1.3. toString(), toBytes(), toHex() and toBits()</h3></div></div></div><p>
<code class="code">toString()</code> returns the base-10 form of a number. <code class="code">toBytes()</code> returns the base-256
form of a number, <code class="code">toHex()</code> returns the base-16 form, and <code class="code">toBits()</code> the base-2 form.
<code class="code">toBytes()</code>, <code class="code">toHex()</code>, and <code class="code">toBits()</code> also take an optional parameter which,
if set, will return the two's compliment of a number. So if, for example, $a is equal to -1,
<code class="code">toBytes(true)</code> will return <code class="code">chr(0xFF)</code>.
</p><p>
On PHP 5, <code class="code">toString()</code> is called automatically when used in a string context via the
<a class="ulink" href="http://php.net/language.oop5.magic#language.oop5.magic.tostring" target="_top">__toString() magic method</a>.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_fourfunctions"></a>2.1.4. add(), subtract(), multiply() and divide()</h3></div></div></div><p>
<code class="code">subtract()</code> and <code class="code">multiply()</code> operate similarly to <code class="code">add()</code>. <code class="code">divide()</code>,
however, does not. Namely, it returns an array whose first element contains the quotient and whose
second element contains the "common residue". If the remainder would be positive, the "common residue"
and the remainder are the same. If the remainder would be negative, the "common residue" is equal to
the sum of the remainder and the divisor (basically, the "common residue" is the first positive modulo).
Here's an example:
</p><pre class="programlisting">&lt;?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('10');
$b = new Math_BigInteger('20');
list($quotient, $remainder) = $a-&gt;divide($b);
echo $quotient-&gt;toString(); // outputs 0
echo "\r\n";
echo $remainder-&gt;toString(); // outputs 10
?&gt;</pre></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_modulo"></a>2.1.5. powMod() and modInverse()</h3></div></div></div><p>
Examples of each follow:
</p><pre class="programlisting">&lt;?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('10');
$b = new Math_BigInteger('20');
$c = new Math_BigInteger('30');
$c = $a-&gt;powMod($b, $c);
echo $c-&gt;toString(); // outputs 10
?&gt;</pre><pre class="programlisting">&lt;?php
include('Math/BigInteger.php');
$a = new Math_BigInteger(30);
$b = new Math_BigInteger(17);
$c = $a-&gt;modInverse($b);
echo $c-&gt;toString(); // outputs 4
?&gt;</pre></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_gcd"></a>2.1.6. gcd() and extendedGCD()</h3></div></div></div><p>
<code class="code">extendedGCD()</code> returns an array containing three Math_BigInteger values indexed with x, y,
and gcd. x and y represent Bézout's identity. <code class="code">gcd()</code> returns a Math_BigInteger value
equal to the gcd. An example of each follows:
</p><pre class="programlisting">&lt;?php
include('Math/BigInteger.php');
$a = new Math_BigInteger(693);
$b = new Math_BigInteger(609);
extract($a-&gt;extendedGCD($b));
$c = $a-&gt;gcd($b);
echo $gcd-&gt;toString() . "\r\n"; // outputs 21
echo $c-&gt;toString() . "\r\n"; // outputs 21
echo $a-&gt;toString() * $x-&gt;toString() + $b-&gt;toString() * $y-&gt;toString(); // outputs 21
?&gt;</pre></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_abs"></a>2.1.7. abs()</h3></div></div></div><p>
<code class="code">$x-&gt;abs()</code> returns the absolute value of <code class="code">$x</code>.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_compare"></a>2.1.8. equals() and compare()</h3></div></div></div><p>
<code class="code">$x-&gt;equals($y)</code> returns true or false depending on whether or not <code class="code">$x</code> and
<code class="code">$y</code> are equal.
</p><p>
<code class="code">$x-&gt;compare($y)</code> returns 1 if $x &gt; $y, 0 if $x == $y, and -1 if $x &lt; $y. The reason for this
is demonstrated thusly:
</p><pre class="programlisting">$x &gt; $y: $x-&gt;compare($y) &gt; 0
$x &lt; $y: $x-&gt;compare($y) &lt; 0
$x == $y: $x-&gt;compare($y) == 0
$x &gt;= $y: $x-&gt;compare($y) &gt;= 0
$x &lt;= $y: $x-&gt;compare($y) &lt;= 0</pre><p>
As a consequence of this, <code class="code">!$x-&gt;compare($y)</code> does not mean <code class="code">$x != $y</code> but rather
<code class="code">$x == $y</code>.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_precision"></a>2.1.9. setPrecision()</h3></div></div></div><p>
Some bitwise operations give different results depending on the precision being used. Examples include
left shift, not, and rotates, as discussed for <a class="link" href="math.html#math_biginteger_bitwise" title="2.1.10. bitwise_and(), bitwise_or(), bitwise_xor() and bitwise_not()">bitwise_not()</a>.
This function lets you control the precision.
</p><p>
Whenever a new Math_BigInteger object is created it's precision is set to the same precision as the
calling object. In other words, if you do <code class="code">$b = $a-&gt;bitwise_not()</code> then <code class="code">$b</code> will
have the same precision as <code class="code">$a</code>.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_bitwise"></a>2.1.10. bitwise_and(), bitwise_or(), bitwise_xor() and bitwise_not()</h3></div></div></div><p>
<code class="code">bitwise_and()</code>, <code class="code">bitwise_or()</code> and <code class="code">bitwise_xor()</code> operate similar to
<code class="code">add()</code>. <code class="code">bitwise_not()</code> is a bit more complicated. To elaborate, if the
precision (see <a class="link" href="math.html#math_biginteger_precision" title="2.1.9. setPrecision()">setPrecision</a>) is arbitrary,
<code class="code">$x-&gt;bitwise_not()</code> will always yield a smaller value since the most significant bit is
assumed to have a value of one. With fixed precision, however, the leading bit can be anything.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_shifts"></a>2.1.11. bitwise_rightShift() and bitwise_leftShift()</h3></div></div></div><p>
<code class="code">$a-&gt;bitwise_rightShift($shift)</code> shifts $a by $shift bits, effectively dividing by 2**$shift.
<code class="code">$a-&gt;bitwise_leftShift($shift)</code> shifts $a by $shift bits, effectively multiplying by 2**$shift.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_rotates"></a>2.1.12. bitwise_rightRotate() and bitwise_leftRotate()</h3></div></div></div><p>
<code class="code">$a-&gt;bitwise_rightRotate($shift)</code> and <code class="code">$a-&gt;bitwise_leftRotate($shift)</code> are
demonstrated thusly:
</p><pre class="programlisting">&lt;?php
include('Math/BigInteger.php');
$a = new Math_BigInteger('00111000', 2);
$a-&gt;setPrecision(8);
$b = $a-&gt;bitwise_leftRotate(2);
echo $b-&gt;toBits(); // returns 11100000
echo "\r\n";
$a = new Math_BigInteger('00111000', 2);
$b = $a-&gt;bitwise_leftRotate(2);
echo $b-&gt;toBits(); // returns 100011
?&gt;</pre><p>
Just as with <a class="link" href="math.html#math_biginteger_bitwise" title="2.1.10. bitwise_and(), bitwise_or(), bitwise_xor() and bitwise_not()">bitwise_not()</a>, these operations are
precision dependant.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_setrandom"></a>2.1.13. setRandomGenerator()</h3></div></div></div><p>
Sets the random generator. To set it to <code class="code">mt_rand()</code> (which is what it is by default), call
<code class="code">$x-&gt;setRandomGenerator('mt_rand')</code>.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_prime"></a>2.1.14. isPrime()</h3></div></div></div><p>
Returns true if a number is prime and false if it isn't.
</p></div><div class="section" lang="en" xml:lang="en"><div class="titlepage"><div><div><h3 class="title"><a id="math_biginteger_random"></a>2.1.15. random() and randomPrime()</h3></div></div></div><p>
<code class="code">random($min, $max)</code> generates a random number between <code class="code">$min</code> and <code class="code">$max</code>.
<code class="code">randomPrime($min, $max)</code> generates a random prime number between <code class="code">$min</code> and <code class="code">$max</code>.
If no prime number exists between <code class="code">$min</code> and <code class="code">$max</code> false is returned.
</p><p>
<code class="code">randomPrime()</code> has an optional third parameter, as well - $timeout. Generating prime numbers
is a particurarly expensive operation and although in certain environments even 512-bit primes can be
generated in a less than a second it can take other environments upwards of around a minute if not more.
</p></div></div></div><div class="navfooter"><hr /><table width="100%" summary="Navigation footer"><tr><td width="40%" align="left"><a accesskey="p" href="intro.html">Prev</a> </td><td width="20%" align="center"> </td><td width="40%" align="right"> <a accesskey="n" href="sym_crypt.html">Next</a></td></tr><tr><td width="40%" align="left" valign="top">Chapter 1. Introduction </td><td width="20%" align="center"><a accesskey="h" href="index.html">Home</a></td><td width="40%" align="right" valign="top"> Chapter 3. Symmetric-key Cryptography</td></tr></table></div></body></html>