num_theory/miller_rabin/index.php

<?php
if (!$STDNWPSTYLE_INCLUDED)
   {
   include("stdnwpstyle.inc");
   $STDNWPSTYLE_INCLUDED=1;
   }
?>
<?php
//********************************************************************************
//Copyright (C) 2003 David T. Ashley
//********************************************************************************
//This program or source file is free software; you can redistribute it and/or 
//modify it under the terms of the GNU General Public License as published by
//the Free Software Foundation; either version 2 of the License, or (at your 
//option) any later version.
//
//This program or source file is distributed in the hope that it will 
//be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
//GNU General Public License for more details.
//
//You may have received a copy of the GNU General Public License
//along with this program; if not, write to the Free Software
//Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
//********************************************************************************
//
//Returns TRUE if the passed argument is a digit, or FALSE otherwise.  If the
//passed string has length > 1, only the least significant digit is
//considered.
function miller_rabin_isdigit($Digit)
   {
   $Digit = (string)$Digit;

   //If the string has zero length, this is an error condition and return 0.
   $Length = strlen($Digit);  

   if ($Length==0)
      {
      return(0);
      }

   //Obtain the trailing character of the string.
   $Trailing_char = Substr($Digit, $Length-1, 1);

   //Do a switch and return an integer based on the character.
   switch($Trailing_char)
      {
      case "9":
         return 1;
         break;
      case "8":
         return 1;
         break;
      case "7":
         return 1;
         break;
      case "6":
         return 1;
         break;
      case "5":
         return 1;
         break;
      case "4":
         return 1;
         break;
      case "3":
         return 1;
         break;
      case "2":
         return 1;
         break;
      case "1":
         return 1;
         break;
      case "0":
         return 1;
         break;
      default:
         return 0;
         break;
      }
   }
//
//
//Returns TRUE if the passed argument is a simple integer (no error   
//codes, no commas), or FALSE otherwise.
function miller_rabin_issimpleint($Intnum)
   {
   $Intnum = (string)$Intnum;

   //If the string has zero length, this is an error condition and return 0.
   $Length = strlen($Intnum);  

   if ($Length==0)
      {
      return(0);
      }

   //If the first digit is "0", this must be the only character in the string,
   //otherwise there is a leading-zero violation.
   if (Substr($Intnum, 0, 1)=="0")
      {
      if ($Length==1)
         {
         return 1;
         }
      else
         {
         return 0;
         }
      }

   //If the first character is a "-" sign, it may not be the only character,
   //and it may not precede a "0" (which would again be a leading 0 violation).
   //If it is a "-", we can exclude "0" and parse as a positive.
   if (Substr($Intnum, 0, 1)=="-")
      {
      if ($Length==1)
         {
         return 0;
         }
      else
         {
         if (Substr($Intnum, 1, 1) == "0")
            {
            //This is illegal (a "-" followed by a "0").
            return 0;
            }
         else
            {
            //We can just remove the "-" and parse as a positive.
            $Intnum = Substr($Intnum, 1, $Length - 1);
            $Length--;
            }
         }
      }

   //It is known at this point that the length is at least 1 and the leading 
   //character is not zero.  All we need to do at this point is check that each 
   //and every character is a digit.
   for ($index=0; $index < $Length; $index++)
      {
      if (!miller_rabin_isdigit(Substr($Intnum, $index, 1)))
         return 0;
      }

   return 1;
   }
//
//
//Returns the number of digits in the argument, which must be a valid simple
//integer.
function miller_rabin_ndigits($Intnum)
   {
   $Intnum = (string)$Intnum;

   if (Substr($Intnum, 0, 1) == "-")
      {
      $rv = strlen($Intnum) - 1;
      }
   else
      {
      $rv = strlen($Intnum);
      }

   return($rv);
   }
//
//
//Given a string, converts the final character to an integer.  If the character
//is not a digit, returns 0.
function miller_rabin_digittoint($Digit)
   {
   //echo "Digit is: ";
   //echo $Digit;
   //echo "<br>";

   $Digit = (string)$Digit;

   //echo "Digit is: ";
   //echo $Digit;
   //echo "<br>";
   
   //If the string has zero length, this is an error condition and return 0.
   $Length = strlen($Digit);  

   //echo "Length is: ";
   //echo $Length;
   //echo "<br>";

   if ($Length==0)
      {
      return(0);
      }

   //Obtain the trailing character of the string.
   $Trailing_char = Substr($Digit, $Length-1, 1);

   //echo "Trailing char is: ";
   //echo $Trailing_char;
   //echo "<br>";

   //Do a switch and return an integer based on the character.
   //The default case gives 0.

   switch($Trailing_char)
      {
      case "9":
         return 9;
         break;
      case "8":
         return 8;
         break;
      case "7":
         return 7;
         break;
      case "6":
         return 6;
         break;
      case "5":
         return 5;
         break;
      case "4":
         return 4;
         break;
      case "3":
         return 3;
         break;
      case "2":
         return 2;
         break;
      case "1":
         return 1;
         break;
      default:
         return 0;
         break;
      }
   }

//Decommanates an integer and removes all other crap without respect for 
//whether the commas are in the right place or the integer is syntactically valid.
function miller_rabin_decommanate(&$arg)
   {
   $temp = "";

   $len = strlen($arg);

   for ($i=0; $i<$len; $i++)
      {
      $c = (string)Substr($arg, $i, 1);
   
      if (miller_rabin_isdigit($c) || ($c == "-"))
         $temp = $temp . $c;
      }

   $arg = (string)$temp;
   } 

//Commanates an integer which is assumed to by syntactically correct.
function miller_rabin_commanate(&$arg)
   {
   miller_rabin_decommanate($arg);
 
   $temp = "";
  
   $len = strlen($arg);

   for ($i=0; $i<$len; $i++)
      {
      $c = (string)Substr($arg, $len - $i - 1, 1);

      $temp = $c . $temp;
      
      if ($i != ($len-1))
         {
         if (Substr($arg, $len-$i-2, 1) != "-")
            {
            if (($i % 3) == 2)
               $temp = "," . $temp;
            }
         }
      }

   $arg = (string)$temp;
   } 

function do_header(&$style, $miller_rabin_nrounds)
   {
   $style->header_title("Probable Primality Test (Miller-Rabin)",
                        "Miller-Rabin Probable Primality Test",
                        "This utility uses " . $miller_rabin_nrounds . " applications of the " .
                        "<a href=\"http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html\">" .
                        "Miller-Rabin test</a> to determine " .
                        "with high probabilistic certainty whether an integer " .
                        "is " .
                        "<a href=\"http://mathworld.wolfram.com/PrimeNumber.html\">prime</a> or " .
                        "<a href=\"http://mathworld.wolfram.com/CompositeNumber.html\">composite</a>." .
                        "&nbsp;  This utility does <i>not</i> " .
                        "factor composite numbers.");
   }  

function do_footer(&$style)
   {
   $style->hrule_std();
   echo "<p align=\"center\">This utility is powered by the ";
   echo "<a href=\"http://www.swox.com/gmp\"><img hspace=\"5\" vspace=\"5\" src=\"../genimages/gmplogo1.png\" width=\"232\" height=\"104\" align=\"absmiddle\"></a>.&nbsp; All source code is available ";
   echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
   $style->footer_std();
   }

function do_form($N_refresh, $Buttontext, $max_digits)
   {
   echo "<form method=get action=\"miller_rabin.php\" width=\"100%\">\n";
   echo "<table align=\"center\">\n";
   echo "<tr>\n";
   echo "  <td width=\"10%\">\n";
   echo "   <p align=\"right\"><b>N</b> (" . number_format($max_digits) . "-digit maximum):</td>\n";
   echo "    <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
   if (strlen($N_refresh))
     {
     echo "value=\"" . $N_refresh . "\" ";
     }
   echo "name=\"N\" size=\"50\"></p></td>\n";
   echo "  </tr>\n";
   echo "  <tr>\n";
   echo "    <td width=\"20%\" colspan=\"2\">\n";
   echo "      <p align=\"center\"><input type=\"submit\" value=\"";
   echo $Buttontext;
   echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
   echo "  </tr>\n";
   echo "</table>\n";
   echo "</form>\n";
}

function do_err_msg($Err_msg)
   {
   echo "<p align=\"center\"><b><font color=\"#FF0000\">";
   echo $Err_msg;
   echo "</font></b></p>\n";
   }


//Main script begins here.
//
//
//Let's agree on a maximum for number of digits in the number to test.  It is known that
//Apache won't process URL's larger than 1024, so let's be conservative and say 500
//digits.
$max_digits = 500;
//
//Let's agree on a number of rounds for the Miller-Rabin test.  This influences the
//probabilities.
$miller_rabin_nrounds = 25;
//
//We need to establish the probability that a number which passes the rounds specified
//above is still in fact composite.  This values need to be calculated by hand whenever
//the value above is changed.
$miller_rabin_p_real                 =  "0.99999999999999911182";
$miller_rabin_p_percent              = "99.999999999999911182";
$miller_rabin_residual_real          =  "0.00000000000000088818";
$miller_rabin_residual_percent       =  "0.000000000000088818";
$miller_rabin_residual_lt_reciprocal =  "1,125,899,906,842,624";
//
$style = new Stdnwpstyle;
//Assign the current style in force.  Also, starts the CPU
//usage clock.

//Do the header unconditionally.  The header is always used on this page.
do_header($style, $miller_rabin_nrounds);
//
//
//If N was supplied, decommanate it and be sure it is a string.
if (isset($N))
   miller_rabin_decommanate($N);
//
//There are a few cases to break into here, and this affects the overall layout of the page.
//The header and footer are fixed, but the "guts" will change.
if (!isset($N))
   {
   //In this case, we are probably visiting the form for the first time, and have not done a submit.
   //Just display the form itself.
   do_form("", "Is This Prime?", $max_digits);
   }
elseif (!miller_rabin_issimpleint($N))
   {
   do_err_msg("N is a malformed integer. &nbsp;Choose a new value for N and try again.");
   $style->hrule_std();  
   miller_rabin_commanate($N);
   do_form($N, "Is This Prime?", $max_digits);
   }  
elseif ($N == "1")
   {
   do_err_msg("It is not a valid question to ask if 1 is prime.&nbsp; It is agreed " .
              "in number theory (largely to minimize exception cases in proofs and results) " .
              "that 1 is neither prime nor composite.&nbsp; " .
              "Choose a new value for N and try again.");
   $style->hrule_std();  
   miller_rabin_commanate($N);
   do_form($N, "Is This Prime?", $max_digits);
   }  
elseif (strlen($N) > $max_digits)
   {
   do_err_msg("N is too long (a " . number_format($max_digits) . "-digit maximum is " .
               "in effect).&nbsp; Choose a shorter value and try again.");
   $style->hrule_std();  
   miller_rabin_commanate($N);
   do_form($N, "Is This Prime?", $max_digits);
   }
else
   {
   //N seems to be a valid integer.
   //
   //If N is negative, make it positive.
   if (Substr($N, 0, 1)=="-")
     $N = Substr($N, 1, strlen($N)-1);

   //If N is "0", make it "2".
   if ($N=="0")
     $N = (string)"2";

   //We can now run the external program to do the calculation.
   $cgi_command_string = "./arith_large_cgi gmp_prob_prime " . $N . " " . $miller_rabin_nrounds;

   //echo "CGI command string is : " . $cgi_command_string . "<br>\n";

   exec($cgi_command_string, $cgi_result);
   $cgi_result_nelem = count($cgi_result);

   //echo "Result is : " . $cgi_result_nelem . "<br>\n";

   //for ($i=0; $i<$cgi_result_nelem; $i++)
   //{
   //  echo $cgi_result[$i] . "<br>\n";
   //}

   //We need to perform some sanity checks on the CGI output to be sure it
   //is what we want.  If it seems wrong, we need to generate an error message
   //and not try to display the output.
   $cgi_output_is_sane = 1;
   if ($cgi_result_nelem == 0)
      $cgi_output_is_sane = 0;
   if ($cgi_result_nelem > 0)
      {
      if ($cgi_result_nelem != 5)
         $cgi_output_is_sane = 0;
      if ($cgi_result[0] != "S")
         $cgi_output_is_sane = 0;
      if (($cgi_result[3] != "0") && ($cgi_result[3] != "1") && ($cgi_result[3] != "2"))
         $cgi_output_is_sane = 0;
      if ($cgi_result[4] != "S")
         $cgi_output_is_sane = 0;
      }

   if (!$cgi_output_is_sane)
      {
      do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.&nbsp; Please advise the webmaster.");
      $style->hrule_std();  
      miller_rabin_commanate($N);
      do_form($N, "Is This Prime", $max_digits);
      }
   else
      {
      miller_rabin_commanate($cgi_result[1]);

      if ($cgi_result[3] == 0)
         {
         echo "<p align=\"center\"><font size=\"4\">The integer ";
         echo $cgi_result[1];
         echo " is definitely (with 100% certainty) composite.&nbsp; Note, however, that although ";
         echo "it was relatively computationally inexpensive to determine that this integer is composite, ";
         echo "factoring it may be computationally <i>much</i> more expensive.</font></p>\n";
         }
      elseif ($cgi_result[3] == 1)
         {
         echo "<p align=\"center\"><font size=\"4\">Based on " . $miller_rabin_nrounds . " applications of ";
         echo "the Miller-Rabin test, the integer ";
         echo $cgi_result[1];
         echo " is probably (with " . $miller_rabin_p_percent . "% certainty) ";
         echo "prime.&nbsp; (This means that there is no more than 1 chance in ";
         echo $miller_rabin_residual_lt_reciprocal . " that this integer is ";
         echo "composite.)</font></p>\n";
         }
      else
         {
         echo "<p align=\"center\"><font size=\"4\">The integer ";
         echo $cgi_result[1];
         echo " is prime (with 100% certainty).&nbsp; This means that the ";
         echo "GMP";
         echo " library routine was able to attempt trial division with divisors ";
         echo "up to <i>floor</i>(<i>sqrt</i>(N)).</font></p>\n";
         }

      $style->hrule_std();  
?>
<p align="left"><b>Notes on the algorithm:</b>
<ul>
    <li>It is agreed in number theory that 
        <a href="http://www.mth.uct.ac.za/~digest/faq/prime.html">'1' is neither prime nor 
        composite</a>.&nbsp; This definition
        is largely <a href="http://dictionary.reference.com/search?q=arbitrary">arbitrary</a>, 
        and there is some discussion in Usenet newsgroups
        such as <i>sci.math</i> from time to time about this topic.&nbsp; It substantially shortens
        and neatens many results and proofs to define '1' in this way.&nbsp; For this reason,
        this utility refuses to <a href="http://dictionary.reference.com/search?q=opine">opine</a> on '1'. 
        </li>
    <li>The <a href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Miller-Rabin 
        test</a> and other 
        <a href="http://mathworld.wolfram.com/StrongPseudoprime.html">strong pseudoprime</a> tests 
        are part of the backbone of popular 
        <a href="http://mathworld.wolfram.com/Public-KeyCryptography.html">public-key cryptography</a>,
        specifically 
        <a href="http://mathworld.wolfram.com/RSAEncryption.html">RSA public-key cryptography</a>,
        which relies on the fact that it is much easier to create a large composite number with
        large prime components than to factor it.        
        </li>
    <li>This utility uses the <i>mpz_prob_prime_p()</i> function from
        the <a href="http://www.swox.com/gmp">GMP</a>
        to make its primality assessment.&nbsp; This function has not been proofread
        to verify how it selects bases and applies the Miller-Rabin test.&nbsp; It is assumed 
        that the standard upper bound of 0.25^N can be applied where N is the <i>reps</i>
        parameter to the function (in the case of this utility, <i>reps</i> is  
        <?php echo " " . $miller_rabin_nrounds ; ?>). 
        </li>
    <li>This web site also contains a <a href="pfact18digit.php">factorization
        utility</a> which will factor integers subject to size and CPU time constraints.                
</ul>
<?php
      $style->hrule_std();  

      miller_rabin_commanate($N);
      do_form($N, "Is This Prime?", $max_digits);
      }
   }

//Now do the footer unconditionally.  The footer is always used on this web page.
do_footer($style);  
?>
1	dashley	23	<?php
2			if (!$STDNWPSTYLE_INCLUDED)
3			{
4			include("stdnwpstyle.inc");
5			$STDNWPSTYLE_INCLUDED=1;
6			}
7			?>
8			<?php
9			//********************************************************************************
10			//Copyright (C) 2003 David T. Ashley
11			//********************************************************************************
12			//This program or source file is free software; you can redistribute it and/or
13			//modify it under the terms of the GNU General Public License as published by
14			//the Free Software Foundation; either version 2 of the License, or (at your
15			//option) any later version.
16			//
17			//This program or source file is distributed in the hope that it will
18			//be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of
19			//MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
20			//GNU General Public License for more details.
21			//
22			//You may have received a copy of the GNU General Public License
23			//along with this program; if not, write to the Free Software
24			//Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
25			//********************************************************************************
26			//
27			//Returns TRUE if the passed argument is a digit, or FALSE otherwise. If the
28			//passed string has length > 1, only the least significant digit is
29			//considered.
30			function miller_rabin_isdigit($Digit)
31			{
32			$Digit = (string)$Digit;
33
34			//If the string has zero length, this is an error condition and return 0.
35			$Length = strlen($Digit);
36
37			if ($Length==0)
38			{
39			return(0);
40			}
41
42			//Obtain the trailing character of the string.
43			$Trailing_char = Substr($Digit, $Length-1, 1);
44
45			//Do a switch and return an integer based on the character.
46			switch($Trailing_char)
47			{
48			case "9":
49			return 1;
50			break;
51			case "8":
52			return 1;
53			break;
54			case "7":
55			return 1;
56			break;
57			case "6":
58			return 1;
59			break;
60			case "5":
61			return 1;
62			break;
63			case "4":
64			return 1;
65			break;
66			case "3":
67			return 1;
68			break;
69			case "2":
70			return 1;
71			break;
72			case "1":
73			return 1;
74			break;
75			case "0":
76			return 1;
77			break;
78			default:
79			return 0;
80			break;
81			}
82			}
83			//
84			//
85			//Returns TRUE if the passed argument is a simple integer (no error
86			//codes, no commas), or FALSE otherwise.
87			function miller_rabin_issimpleint($Intnum)
88			{
89			$Intnum = (string)$Intnum;
90
91			//If the string has zero length, this is an error condition and return 0.
92			$Length = strlen($Intnum);
93
94			if ($Length==0)
95			{
96			return(0);
97			}
98
99			//If the first digit is "0", this must be the only character in the string,
100			//otherwise there is a leading-zero violation.
101			if (Substr($Intnum, 0, 1)=="0")
102			{
103			if ($Length==1)
104			{
105			return 1;
106			}
107			else
108			{
109			return 0;
110			}
111			}
112
113			//If the first character is a "-" sign, it may not be the only character,
114			//and it may not precede a "0" (which would again be a leading 0 violation).
115			//If it is a "-", we can exclude "0" and parse as a positive.
116			if (Substr($Intnum, 0, 1)=="-")
117			{
118			if ($Length==1)
119			{
120			return 0;
121			}
122			else
123			{
124			if (Substr($Intnum, 1, 1) == "0")
125			{
126			//This is illegal (a "-" followed by a "0").
127			return 0;
128			}
129			else
130			{
131			//We can just remove the "-" and parse as a positive.
132			$Intnum = Substr($Intnum, 1, $Length - 1);
133			$Length--;
134			}
135			}
136			}
137
138			//It is known at this point that the length is at least 1 and the leading
139			//character is not zero. All we need to do at this point is check that each
140			//and every character is a digit.
141			for ($index=0; $index < $Length; $index++)
142			{
143			if (!miller_rabin_isdigit(Substr($Intnum, $index, 1)))
144			return 0;
145			}
146
147			return 1;
148			}
149			//
150			//
151			//Returns the number of digits in the argument, which must be a valid simple
152			//integer.
153			function miller_rabin_ndigits($Intnum)
154			{
155			$Intnum = (string)$Intnum;
156
157			if (Substr($Intnum, 0, 1) == "-")
158			{
159			$rv = strlen($Intnum) - 1;
160			}
161			else
162			{
163			$rv = strlen($Intnum);
164			}
165
166			return($rv);
167			}
168			//
169			//
170			//Given a string, converts the final character to an integer. If the character
171			//is not a digit, returns 0.
172			function miller_rabin_digittoint($Digit)
173			{
174			//echo "Digit is: ";
175			//echo $Digit;
176			//echo "<br>";
177
178			$Digit = (string)$Digit;
179
180			//echo "Digit is: ";
181			//echo $Digit;
182			//echo "<br>";
183
184			//If the string has zero length, this is an error condition and return 0.
185			$Length = strlen($Digit);
186
187			//echo "Length is: ";
188			//echo $Length;
189			//echo "<br>";
190
191			if ($Length==0)
192			{
193			return(0);
194			}
195
196			//Obtain the trailing character of the string.
197			$Trailing_char = Substr($Digit, $Length-1, 1);
198
199			//echo "Trailing char is: ";
200			//echo $Trailing_char;
201			//echo "<br>";
202
203			//Do a switch and return an integer based on the character.
204			//The default case gives 0.
205
206			switch($Trailing_char)
207			{
208			case "9":
209			return 9;
210			break;
211			case "8":
212			return 8;
213			break;
214			case "7":
215			return 7;
216			break;
217			case "6":
218			return 6;
219			break;
220			case "5":
221			return 5;
222			break;
223			case "4":
224			return 4;
225			break;
226			case "3":
227			return 3;
228			break;
229			case "2":
230			return 2;
231			break;
232			case "1":
233			return 1;
234			break;
235			default:
236			return 0;
237			break;
238			}
239			}
240
241			//Decommanates an integer and removes all other crap without respect for
242			//whether the commas are in the right place or the integer is syntactically valid.
243			function miller_rabin_decommanate(&$arg)
244			{
245			$temp = "";
246
247			$len = strlen($arg);
248
249			for ($i=0; $i<$len; $i++)
250			{
251			$c = (string)Substr($arg, $i, 1);
252
253			if (miller_rabin_isdigit($c) \|\| ($c == "-"))
254			$temp = $temp . $c;
255			}
256
257			$arg = (string)$temp;
258			}
259
260			//Commanates an integer which is assumed to by syntactically correct.
261			function miller_rabin_commanate(&$arg)
262			{
263			miller_rabin_decommanate($arg);
264
265			$temp = "";
266
267			$len = strlen($arg);
268
269			for ($i=0; $i<$len; $i++)
270			{
271			$c = (string)Substr($arg, $len - $i - 1, 1);
272
273			$temp = $c . $temp;
274
275			if ($i != ($len-1))
276			{
277			if (Substr($arg, $len-$i-2, 1) != "-")
278			{
279			if (($i % 3) == 2)
280			$temp = "," . $temp;
281			}
282			}
283			}
284
285			$arg = (string)$temp;
286			}
287
288			function do_header(&$style, $miller_rabin_nrounds)
289			{
290			$style->header_title("Probable Primality Test (Miller-Rabin)",
291			"Miller-Rabin Probable Primality Test",
292			"This utility uses " . $miller_rabin_nrounds . " applications of the " .
293			"<a href=\"http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html\">" .
294			"Miller-Rabin test</a> to determine " .
295			"with high probabilistic certainty whether an integer " .
296			"is " .
297			"<a href=\"http://mathworld.wolfram.com/PrimeNumber.html\">prime</a> or " .
298			"<a href=\"http://mathworld.wolfram.com/CompositeNumber.html\">composite</a>." .
299			"  This utility does <i>not</i> " .
300			"factor composite numbers.");
301			}
302
303			function do_footer(&$style)
304			{
305			$style->hrule_std();
306			echo "<p align=\"center\">This utility is powered by the ";
307			echo "<a href=\"http://www.swox.com/gmp\"><img hspace=\"5\" vspace=\"5\" src=\"../genimages/gmplogo1.png\" width=\"232\" height=\"104\" align=\"absmiddle\"></a>.  All source code is available ";
308			echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
309			$style->footer_std();
310			}
311
312			function do_form($N_refresh, $Buttontext, $max_digits)
313			{
314			echo "<form method=get action=\"miller_rabin.php\" width=\"100%\">\n";
315			echo "<table align=\"center\">\n";
316			echo "<tr>\n";
317			echo " <td width=\"10%\">\n";
318			echo " <p align=\"right\"><b>N</b> (" . number_format($max_digits) . "-digit maximum):</td>\n";
319			echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
320			if (strlen($N_refresh))
321			{
322			echo "value=\"" . $N_refresh . "\" ";
323			}
324			echo "name=\"N\" size=\"50\"></p></td>\n";
325			echo " </tr>\n";
326			echo " <tr>\n";
327			echo " <td width=\"20%\" colspan=\"2\">\n";
328			echo " <p align=\"center\"><input type=\"submit\" value=\"";
329			echo $Buttontext;
330			echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
331			echo " </tr>\n";
332			echo "</table>\n";
333			echo "</form>\n";
334			}
335
336			function do_err_msg($Err_msg)
337			{
338			echo "<p align=\"center\"><b><font color=\"#FF0000\">";
339			echo $Err_msg;
340			echo "</font></b></p>\n";
341			}
342
343
344			//Main script begins here.
345			//
346			//
347			//Let's agree on a maximum for number of digits in the number to test. It is known that
348			//Apache won't process URL's larger than 1024, so let's be conservative and say 500
349			//digits.
350			$max_digits = 500;
351			//
352			//Let's agree on a number of rounds for the Miller-Rabin test. This influences the
353			//probabilities.
354			$miller_rabin_nrounds = 25;
355			//
356			//We need to establish the probability that a number which passes the rounds specified
357			//above is still in fact composite. This values need to be calculated by hand whenever
358			//the value above is changed.
359			$miller_rabin_p_real = "0.99999999999999911182";
360			$miller_rabin_p_percent = "99.999999999999911182";
361			$miller_rabin_residual_real = "0.00000000000000088818";
362			$miller_rabin_residual_percent = "0.000000000000088818";
363			$miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624";
364			//
365			$style = new Stdnwpstyle;
366			//Assign the current style in force. Also, starts the CPU
367			//usage clock.
368
369			//Do the header unconditionally. The header is always used on this page.
370			do_header($style, $miller_rabin_nrounds);
371			//
372			//
373			//If N was supplied, decommanate it and be sure it is a string.
374			if (isset($N))
375			miller_rabin_decommanate($N);
376			//
377			//There are a few cases to break into here, and this affects the overall layout of the page.
378			//The header and footer are fixed, but the "guts" will change.
379			if (!isset($N))
380			{
381			//In this case, we are probably visiting the form for the first time, and have not done a submit.
382			//Just display the form itself.
383			do_form("", "Is This Prime?", $max_digits);
384			}
385			elseif (!miller_rabin_issimpleint($N))
386			{
387			do_err_msg("N is a malformed integer.  Choose a new value for N and try again.");
388			$style->hrule_std();
389			miller_rabin_commanate($N);
390			do_form($N, "Is This Prime?", $max_digits);
391			}
392			elseif ($N == "1")
393			{
394			do_err_msg("It is not a valid question to ask if 1 is prime.  It is agreed " .
395			"in number theory (largely to minimize exception cases in proofs and results) " .
396			"that 1 is neither prime nor composite.  " .
397			"Choose a new value for N and try again.");
398			$style->hrule_std();
399			miller_rabin_commanate($N);
400			do_form($N, "Is This Prime?", $max_digits);
401			}
402			elseif (strlen($N) > $max_digits)
403			{
404			do_err_msg("N is too long (a " . number_format($max_digits) . "-digit maximum is " .
405			"in effect).  Choose a shorter value and try again.");
406			$style->hrule_std();
407			miller_rabin_commanate($N);
408			do_form($N, "Is This Prime?", $max_digits);
409			}
410			else
411			{
412			//N seems to be a valid integer.
413			//
414			//If N is negative, make it positive.
415			if (Substr($N, 0, 1)=="-")
416			$N = Substr($N, 1, strlen($N)-1);
417
418			//If N is "0", make it "2".
419			if ($N=="0")
420			$N = (string)"2";
421
422			//We can now run the external program to do the calculation.
423			$cgi_command_string = "./arith_large_cgi gmp_prob_prime " . $N . " " . $miller_rabin_nrounds;
424
425			//echo "CGI command string is : " . $cgi_command_string . "<br>\n";
426
427			exec($cgi_command_string, $cgi_result);
428			$cgi_result_nelem = count($cgi_result);
429
430			//echo "Result is : " . $cgi_result_nelem . "<br>\n";
431
432			//for ($i=0; $i<$cgi_result_nelem; $i++)
433			//{
434			// echo $cgi_result[$i] . "<br>\n";
435			//}
436
437			//We need to perform some sanity checks on the CGI output to be sure it
438			//is what we want. If it seems wrong, we need to generate an error message
439			//and not try to display the output.
440			$cgi_output_is_sane = 1;
441			if ($cgi_result_nelem == 0)
442			$cgi_output_is_sane = 0;
443			if ($cgi_result_nelem > 0)
444			{
445			if ($cgi_result_nelem != 5)
446			$cgi_output_is_sane = 0;
447			if ($cgi_result[0] != "S")
448			$cgi_output_is_sane = 0;
449			if (($cgi_result[3] != "0") && ($cgi_result[3] != "1") && ($cgi_result[3] != "2"))
450			$cgi_output_is_sane = 0;
451			if ($cgi_result[4] != "S")
452			$cgi_output_is_sane = 0;
453			}
454
455			if (!$cgi_output_is_sane)
456			{
457			do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.  Please advise the webmaster.");
458			$style->hrule_std();
459			miller_rabin_commanate($N);
460			do_form($N, "Is This Prime", $max_digits);
461			}
462			else
463			{
464			miller_rabin_commanate($cgi_result[1]);
465
466			if ($cgi_result[3] == 0)
467			{
468			echo "<p align=\"center\"><font size=\"4\">The integer ";
469			echo $cgi_result[1];
470			echo " is definitely (with 100% certainty) composite.  Note, however, that although ";
471			echo "it was relatively computationally inexpensive to determine that this integer is composite, ";
472			echo "factoring it may be computationally <i>much</i> more expensive.</font></p>\n";
473			}
474			elseif ($cgi_result[3] == 1)
475			{
476			echo "<p align=\"center\"><font size=\"4\">Based on " . $miller_rabin_nrounds . " applications of ";
477			echo "the Miller-Rabin test, the integer ";
478			echo $cgi_result[1];
479			echo " is probably (with " . $miller_rabin_p_percent . "% certainty) ";
480			echo "prime.  (This means that there is no more than 1 chance in ";
481			echo $miller_rabin_residual_lt_reciprocal . " that this integer is ";
482			echo "composite.)</font></p>\n";
483			}
484			else
485			{
486			echo "<p align=\"center\"><font size=\"4\">The integer ";
487			echo $cgi_result[1];
488			echo " is prime (with 100% certainty).  This means that the ";
489			echo "GMP";
490			echo " library routine was able to attempt trial division with divisors ";
491			echo "up to <i>floor</i>(<i>sqrt</i>(N)).</font></p>\n";
492			}
493
494			$style->hrule_std();
495			?>
496			<p align="left"><b>Notes on the algorithm:</b>
497			<ul>
498			<li>It is agreed in number theory that
499			<a href="http://www.mth.uct.ac.za/~digest/faq/prime.html">'1' is neither prime nor
500			composite</a>.  This definition
501			is largely <a href="http://dictionary.reference.com/search?q=arbitrary">arbitrary</a>,
502			and there is some discussion in Usenet newsgroups
503			such as <i>sci.math</i> from time to time about this topic.  It substantially shortens
504			and neatens many results and proofs to define '1' in this way.  For this reason,
505			this utility refuses to <a href="http://dictionary.reference.com/search?q=opine">opine</a> on '1'.
506			</li>
507			<li>The <a href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Miller-Rabin
508			test</a> and other
509			<a href="http://mathworld.wolfram.com/StrongPseudoprime.html">strong pseudoprime</a> tests
510			are part of the backbone of popular
511			<a href="http://mathworld.wolfram.com/Public-KeyCryptography.html">public-key cryptography</a>,
512			specifically
513			<a href="http://mathworld.wolfram.com/RSAEncryption.html">RSA public-key cryptography</a>,
514			which relies on the fact that it is much easier to create a large composite number with
515			large prime components than to factor it.
516			</li>
517			<li>This utility uses the <i>mpz_prob_prime_p()</i> function from
518			the <a href="http://www.swox.com/gmp">GMP</a>
519			to make its primality assessment.  This function has not been proofread
520			to verify how it selects bases and applies the Miller-Rabin test.  It is assumed
521			that the standard upper bound of 0.25^N can be applied where N is the <i>reps</i>
522			parameter to the function (in the case of this utility, <i>reps</i> is
523			<?php echo " " . $miller_rabin_nrounds ; ?>).
524			</li>
525			<li>This web site also contains a <a href="pfact18digit.php">factorization
526			utility</a> which will factor integers subject to size and CPU time constraints.
527			</ul>
528			<?php
529			$style->hrule_std();
530
531			miller_rabin_commanate($N);
532			do_form($N, "Is This Prime?", $max_digits);
533			}
534			}
535
536			//Now do the footer unconditionally. The footer is always used on this web page.
537			do_footer($style);
538			?>