library/phpsec/math.html

   1 <?xml version="1.0" encoding="UTF-8" standalone="no"?>
   2 <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
   3 <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>
   4                 Implements an arbitrary precision integer arithmetic library.  Uses gmp or bcmath, if available, and an
   5                 internal implementation, otherwise.  Here's an example:
   6             </p><pre class="programlisting">&lt;?php
   7     include('Math/BigInteger.php');
   8
   9     $a = new Math_BigInteger(2);
  10     $b = new Math_BigInteger(3);
  11
  12     $c = $a-&gt;add($b);
  13
  14     echo $c-&gt;toString(); // outputs 5
  15 ?&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>
  16                     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.
  17                 </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>
  18                     The constructor takes two parameters.  The first is the number and the second represents the base.  Both
  19                     are optional (if they're not provided, the Math_BigInteger object will assume a value of 0).
  20                 </p><p>
  21                     The supported bases are base-2, base-10 (default), base-16, and base-256.  To set $a, in the
  22                     above example, to 2, using base-2, we'd do <code class="code">new Math_BigInteger('10', 2)</code>.  To do it using
  23                     base-16, you could do <code class="code">new Math_BigInteger('2', 16)</code> or <code class="code">new Math_BigInteger('0x2', 16)</code>.
  24                     To set it to 2 using base-256, you'd do <code class="code">new Math_BigInteger(chr(2), 256)</code>.
  25                 </p><p>
  26                     If the base is negative (eg. -256), two's compliment will be used.  Thus, <code class="code">new Math_BigInteger(chr(0xFF), -256)</code>
  27                     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>.
  28                     Basically, if the leading bit is 1, the number is assumed to be negative.
  29                 </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>
  30                     <code class="code">toString()</code> returns the base-10 form of a number.  <code class="code">toBytes()</code> returns the base-256
  31                     form of a number, <code class="code">toHex()</code> returns the base-16 form, and <code class="code">toBits()</code> the base-2 form.
  32                     <code class="code">toBytes()</code>, <code class="code">toHex()</code>, and <code class="code">toBits()</code> also take an optional parameter which,
  33                     if set, will return the two's compliment of a number.  So if, for example, $a is equal to -1,
  34                     <code class="code">toBytes(true)</code> will return <code class="code">chr(0xFF)</code>.
  35                 </p><p>
  36                     On PHP 5, <code class="code">toString()</code> is called automatically when used in a string context via the
  37                     <a class="ulink" href="http://php.net/language.oop5.magic#language.oop5.magic.tostring" target="_top">__toString() magic method</a>.
  38                 </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>
  39                     <code class="code">subtract()</code> and <code class="code">multiply()</code> operate similarly to <code class="code">add()</code>.  <code class="code">divide()</code>,
  40                     however, does not.  Namely, it returns an array whose first element contains the quotient and whose
  41                     second element contains the "common residue".  If the remainder would be positive, the "common residue"
  42                     and the remainder are the same.  If the remainder would be negative, the "common residue" is equal to
  43                     the sum of the remainder and the divisor (basically, the "common residue" is the first positive modulo).
  44                     Here's an example:
  45                 </p><pre class="programlisting">&lt;?php
  46     include('Math/BigInteger.php');
  47
  48     $a = new Math_BigInteger('10');
  49     $b = new Math_BigInteger('20');
  50
  51     list($quotient, $remainder) = $a-&gt;divide($b);
  52
  53     echo $quotient-&gt;toString(); // outputs 0
  54     echo "\r\n";
  55     echo $remainder-&gt;toString(); // outputs 10
  56 ?&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>
  57                     Examples of each follow:
  58                 </p><pre class="programlisting">&lt;?php
  59     include('Math/BigInteger.php');
  60
  61     $a = new Math_BigInteger('10');
  62     $b = new Math_BigInteger('20');
  63     $c = new Math_BigInteger('30');
  64
  65     $c = $a-&gt;powMod($b, $c);
  66
  67     echo $c-&gt;toString(); // outputs 10
  68 ?&gt;</pre><pre class="programlisting">&lt;?php
  69     include('Math/BigInteger.php');
  70
  71     $a = new Math_BigInteger(30);
  72     $b = new Math_BigInteger(17);
  73
  74     $c = $a-&gt;modInverse($b);
  75
  76     echo $c-&gt;toString(); // outputs 4
  77 ?&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>
  78                     <code class="code">extendedGCD()</code> returns an array containing three Math_BigInteger values indexed with x, y,
  79                     and gcd.  x and y represent Bézout's identity.  <code class="code">gcd()</code> returns a Math_BigInteger value
  80                     equal to the gcd.  An example of each follows:
  81                 </p><pre class="programlisting">&lt;?php
  82 include('Math/BigInteger.php');
  83
  84 $a = new Math_BigInteger(693);
  85 $b = new Math_BigInteger(609);
  86
  87 extract($a-&gt;extendedGCD($b));
  88 $c = $a-&gt;gcd($b);
  89
  90 echo $gcd-&gt;toString() . "\r\n"; // outputs 21
  91 echo $c-&gt;toString() . "\r\n"; // outputs 21
  92 echo $a-&gt;toString() * $x-&gt;toString() + $b-&gt;toString() * $y-&gt;toString(); // outputs 21
  93 ?&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>
  94                     <code class="code">$x-&gt;abs()</code> returns the absolute value of <code class="code">$x</code>.
  95                 </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>
  96                     <code class="code">$x-&gt;equals($y)</code> returns true or false depending on whether or not <code class="code">$x</code> and
  97                     <code class="code">$y</code> are equal.
  98                 </p><p>
  99                     <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
 100                     is demonstrated thusly:
 101                 </p><pre class="programlisting">$x  &gt; $y: $x-&gt;compare($y)  &gt; 0
 102 $x  &lt; $y: $x-&gt;compare($y)  &lt; 0
 103 $x == $y: $x-&gt;compare($y) == 0
 104 $x &gt;= $y: $x-&gt;compare($y) &gt;= 0
 105 $x &lt;= $y: $x-&gt;compare($y) &lt;= 0</pre><p>
 106                     As a consequence of this, <code class="code">!$x-&gt;compare($y)</code> does not mean <code class="code">$x != $y</code> but rather
 107                     <code class="code">$x == $y</code>.
 108                 </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>
 109                     Some bitwise operations give different results depending on the precision being used.  Examples include
 110                     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>.
 111                     This function lets you control the precision.
 112                 </p><p>
 113                     Whenever a new Math_BigInteger object is created it's precision is set to the same precision as the
 114                     calling object.  In other words, if you do <code class="code">$b = $a-&gt;bitwise_not()</code> then <code class="code">$b</code> will
 115                     have the same precision as <code class="code">$a</code>.
 116                 </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>
 117                     <code class="code">bitwise_and()</code>, <code class="code">bitwise_or()</code> and <code class="code">bitwise_xor()</code> operate similar to
 118                     <code class="code">add()</code>.  <code class="code">bitwise_not()</code> is a bit more complicated.  To elaborate, if the
 119                     precision (see <a class="link" href="math.html#math_biginteger_precision" title="2.1.9. setPrecision()">setPrecision</a>) is arbitrary,
 120                     <code class="code">$x-&gt;bitwise_not()</code> will always yield a smaller value since the most significant bit is
 121                     assumed to have a value of one.  With fixed precision, however, the leading bit can be anything.
 122                 </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>
 123                     <code class="code">$a-&gt;bitwise_rightShift($shift)</code> shifts $a by $shift bits, effectively dividing by 2**$shift.
 124                     <code class="code">$a-&gt;bitwise_leftShift($shift)</code> shifts $a by $shift bits, effectively multiplying by 2**$shift.
 125                 </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>
 126                     <code class="code">$a-&gt;bitwise_rightRotate($shift)</code> and <code class="code">$a-&gt;bitwise_leftRotate($shift)</code> are
 127                     demonstrated thusly:
 128                 </p><pre class="programlisting">&lt;?php
 129 include('Math/BigInteger.php');
 130
 131 $a = new Math_BigInteger('00111000', 2);
 132 $a-&gt;setPrecision(8);
 133 $b = $a-&gt;bitwise_leftRotate(2);
 134 echo $b-&gt;toBits(); // returns 11100000
 135
 136 echo "\r\n";
 137
 138 $a = new Math_BigInteger('00111000', 2);
 139 $b = $a-&gt;bitwise_leftRotate(2);
 140 echo $b-&gt;toBits(); // returns 100011
 141 ?&gt;</pre><p>
 142                     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
 143                     precision dependant.
 144                 </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>
 145                     Sets the random generator.  To set it to <code class="code">mt_rand()</code> (which is what it is by default), call
 146                     <code class="code">$x-&gt;setRandomGenerator('mt_rand')</code>.
 147                 </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>
 148                     Returns true if a number is prime and false if it isn't.
 149                 </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>
 150                     <code class="code">random($min, $max)</code> generates a random number between <code class="code">$min</code> and <code class="code">$max</code>.
 151                     <code class="code">randomPrime($min, $max)</code> generates a random prime number between <code class="code">$min</code> and <code class="code">$max</code>.
 152                     If no prime number exists between <code class="code">$min</code> and <code class="code">$max</code> false is returned.
 153                 </p><p>
 154                     <code class="code">randomPrime()</code> has an optional third parameter, as well - $timeout.  Generating prime numbers
 155                     is a particurarly expensive operation and although in certain environments even 512-bit primes can be
 156                     generated in a less than a second it can take other environments upwards of around a minute if not more.
 157                 </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>