htdocs/phpcgibin/pfact18digit.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 pfact18_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 pfact18_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 (!pfact18_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 pfact18_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 pfact18_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 pfact18_decommanate(&$arg)
   {
   $temp = "";

   $len = strlen($arg);

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

   $arg = (string)$temp;
   } 

//Commanates an integer which is assumed to by syntactically correct.
function pfact18_commanate(&$arg)
   {
   pfact18_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)
   {
   $style->header_title("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)",
                        "Prime Factorization Of An Integer (18 Or Fewer Digits)",
                        "This utility attempts to factor an integer of 18 or fewer digits into its " .
                        "prime components.");
   }  

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)
   {
   echo "<form method=get action=\"pfact18digit.php\" width=\"100%\">\n";
   echo "<table align=\"center\">\n";
   echo "<tr>\n";
   echo "  <td width=\"10%\">\n";
   echo "   <p align=\"right\"><b>N</b> (18-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";
   }

//Prints algorithm notes with no extraneous HTML (no horizontal lines, etc.)
//
function pfact18_algorithm_notes($cgi_max)
 {
?>
<p><b><u>Algorithm Notes:</u></b></p>
<ul>
<li>This web page uses trial division combined with the 
<a href="http://mathworld.wolfram.com/EratosthenesSieve.html">Sieve of Eratosthenes</a> 
with a sieve of 2,310 = 2 * 3 * 5 * 7 * 11 elements.&nbsp; The
sieve is automatically generated, automatically compacted into a
difference table containing 480 elements, and packaged as a C-language source 
file containing a 480-element lookup table of 
integers.&nbsp; The algorithm checks divisibility by increasing trial divisors,
but it does so with all multiples of 2, 3, 5, 7, and 11 omitted (this is the
role of the Sieve of Eratosthenes).</li>
<li>Although this web page does factor effectively,
it is strictly "parlor amusement" grade, and will answer questions 
such as <i>Is the year I was born a prime number?</i> or <i>Is my street address
prime?</i>, but is inadequate for serious factoring.&nbsp; Because this CGI-BIN
application runs on a shared server, it protects itself by only allowing 
<?php echo " " . $cgi_max . " "; ?>seconds to elapse while factoring.&nbsp; The busier
the server is, the less actual CPU time is represented by
<?php echo " " . $cgi_max . " "; ?>seconds of elapsed time.&nbsp; This means that    
factoring operations may be less successful when the server is busy.</li>
<li>This utility uses the <a href="http://www.swox.com/gmp">GMP library</a>
for arithmetic.&nbsp; The limit of 18-digit integers is in place so that
machine-native integers can be used for the trial divisor (it is more 
efficient that way, and the GMP provides special function calls 
for small divisors).&nbsp; Since the trial divisor need only attain
the square root of the number to be factored, any trial divisor for
an 18-digit integer will fit in one machine-native integer.</li>
</ul>
<?php
   }

function pfact18_print_tabular_results(&$style, 
                                        $cgi_result, 
                                        $cgi_result_nelem, 
                                        $mr_nrounds, 
                                        $mr_pcntprime,
                                        $mr_recip,
                                        $cgi_max)
   {
   //Add commas to the number to factor, the number of Miller-Rabin rounds, and 
   //the timeout.
   pfact18_commanate($cgi_result[1]);
   pfact18_commanate($cgi_result[2]);
   pfact18_commanate($cgi_result[3]);

   //Add commas to each prime factor and its multiplicity.
   $nfactors = ($cgi_result_nelem - 6)/3;

   for ($i=0; $i<$nfactors; $i++)
     {
     pfact18_commanate($cgi_result[$i * 3 + 5]);
     pfact18_commanate($cgi_result[$i * 3 + 6]);
     }

   //echo "<br>" . $cgi_result_nelem . "<br>";

   //Announce the overall result.
   $print_table = 0;
   echo "<p align=\"center\"><font size=\"4\">";
   if (($cgi_result[$cgi_result_nelem - 5] == "P") && ($cgi_result_nelem == 9) && ($cgi_result[$cgi_result_nelem - 3] == "1"))
      {
      echo "The integer " . $cgi_result[1] . " is prime (with 100% certainty)."; 
      }
   elseif (($cgi_result[$cgi_result_nelem - 5] == "p") && ($cgi_result_nelem == 9))
      {
      echo "Based on " . $mr_nrounds . " applications of the Miller-Rabin test, the integer ";
      echo $cgi_result[1] . " is probably (with " . $mr_pcntprime . "% probability) ";
      echo "prime.&nbsp; (This means that there is no more than 1 chance ";
      echo "in " . $mr_recip . " that this integer is composite.)"; 
      }
   elseif (($cgi_result[$cgi_result_nelem - 5] == "C") && ($cgi_result_nelem == 9))
      {
      echo "The integer " . $cgi_result[1] . " has been verified by the Miller-Rabin test ";
      echo "to be composite.&nbsp; However, ";
      echo "due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
      echo "it was not possible to make any progress in factoring ";
      echo "this integer.&nbsp; Please try again when the server is less active ";
      echo "or try another factoring resource."; 
      }
   elseif ($cgi_result[$cgi_result_nelem - 5] == "P")
      {
      echo "The composite integer " ;
      echo $cgi_result[1] . " was successfully factored into its prime components with ";
      echo "100% certainty.&nbsp; Its prime factors and their multiplicities are listed ";
      echo "in the table below."; 
      $print_table = 1;
      }
   elseif ($cgi_result[$cgi_result_nelem - 5] == "p")
      {
      echo "The composite integer " ;
      echo $cgi_result[1] . " was successfully factored into its prime components, ";
      echo "and these prime components and their multiplicities are listed in the ";
      echo "table below.&nbsp; ";
      echo "The last component listed in the table was judged to be prime based on ";
      echo $mr_nrounds . " applications of the Miller-Rabin test, meaning that it is ";
      echo $mr_pcntprime . "% probable ";
      echo "that this last component is prime (i.e. that there is no more than 1 chance ";
      echo "in " . $mr_recip . " that it is composite)."; 
      $print_table = 1;
      }
   elseif ($cgi_result[$cgi_result_nelem - 5] == "C")
      {
      echo "Due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
      echo "the integer ";
      echo $cgi_result[1] . " could only be partially factored.&nbsp; In the results below, note that ";
      echo "the last component ";
      echo "listed bears the category code <i>C</i> (for <u>c</u>omposite).&nbsp; Please ";
      echo " try again when the server is less active ";
      echo "or try another factoring resource."; 
      $print_table = 1;
      }
   echo "</p></font>";

   //Print the table if demanded.
   if ($print_table)
      {
      $style->hrule_std();  

      //Assign the table column widths.  They are centralized here for easy change.
      $width[0] = 10;
      $width[1] = 10;
      $width[2] = 10;
      $width[3] = 10;

      echo "<p><table align=\"center\" border=\"1\" width=\"90%\">\n";

      for ($i=0; $i <= ($cgi_result_nelem/3 - 2); $i++)
         {
         //Factor number.
         echo "<tr>\n";

         echo "   <td width=\"" . $width[0] . "%\">\n";
         if ($i==0)
            {
            echo "      <p align=\"center\"><b>Factor<br>Number</b></p>\n";
            }
         else
            {
            echo "      <p align=\"center\">" . $i . "</p>\n";
            }
         echo "   </td>\n";

         //Prime Factor
         echo "   <td width=\"" . $width[1] . "%\">\n";
         if ($i==0)
            {
            echo "      <p align=\"center\"><b>Component<br>Factor</b></p>\n";
            }
         else
            {
            echo "      <p align=\"center\">" . $cgi_result[$i * 3 + 2] . "</p>\n";
            }
         echo "   </td>\n";

         //Multiplicity.
         echo "   <td width=\"" . $width[2] . "%\">\n";
         if ($i==0)
            {
            echo "      <p align=\"center\"><b>Multiplicity</b></p>\n";
            }
         else
            {
            echo "      <p align=\"center\">" . $cgi_result[$i * 3 + 3] . "</p>\n";
            }
         echo "   </td>\n";

         //Category code.
         echo "   <td width=\"" . $width[3] . "%\">\n";
         if ($i==0)
            {
            echo "      <p align=\"center\"><b>Category<br>Code</b></p>\n";
            }
         else
            {
            echo "      <p align=\"center\">" . $cgi_result[$i * 3 + 1] . "</p>\n";
            }
         echo "   </td>\n";


         echo "</tr>\n";
         }

      echo "</table></p>\n";
      echo "<p align=\"center\"><b>Table legend:</b>&nbsp; <b>P</b>=prime with absolute certainty, ";
      echo "<b>p</b>=prime established by Miller-Rabin test with ";
      echo $mr_pcntprime . "% certainty, and <b>C</b>=composite established by Miller-Rabin test ";
      echo "with absolute certainty, but not factorable in the time allowed.</p>\n";

      $style->hrule_std();  
      pfact18_algorithm_notes($cgi_max);
      }
   }
//
//Main script begins here.
//
//Let's agree on a number of rounds for the Miller-Rabin test.  This influences the
//probabilities.
$miller_rabin_nrounds = 25;
//
//Let's agree how long the CGI may take to factor.
$max_cgi_time = 10;
//     
//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);
//
//
//If N was supplied, decommanate it and be sure it is a string.
if (isset($N))
   pfact18_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("", "Attempt To Factor Integer");
   }
elseif (!pfact18_issimpleint($N))
   {
   //N is supplied, but is malformed.  Need to advise.
   do_err_msg("N is a malformed integer. &nbsp;Choose a new value for N and try again.");
   $style->hrule_std();  
   pfact18_commanate($N2);
   do_form($N, "Attempt To Factor Integer");
   }  
elseif (strlen($N) > 18)
   {
   //N is supplied, but is too long.  Need to advise.
   do_err_msg("N is too long (the maximum is 18 digits). &nbsp;Choose a new value for N and try again.");
   $style->hrule_std();  
   pfact18_commanate($N);
   do_form($N, "Attempt To Factor Integer");
   }
else
   {
   //N is supplied and 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" or "1", make it "2".
   if ($N=="0")
     $N = (string)"1";
   if ($N=="1")
     $N = (string)"2";

   //We can now run the external program to do the calculation.
   $cgi_command_string = "./arith_large_cgi pfact_18 " . $N . " " . $miller_rabin_nrounds . " " . $max_cgi_time;
   //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 < 9)
      $cgi_output_is_sane = 0;
   if ($cgi_result_nelem >= 9)
      {
      if (($cgi_result_nelem % 3) != 0)
         $cgi_output_is_sane = 0;
      if ($cgi_result[0] != "S")
         $cgi_output_is_sane = 0;
      if ($cgi_result[$cgi_result_nelem - 2] != "X")
         $cgi_output_is_sane = 0;
      if ($cgi_result[$cgi_result_nelem - 1] != "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();  
      pfact18_commanate($N);
      do_form($N, "Attempt To Factor Integer");
      }
   else
      {
      pfact18_print_tabular_results($style, 
                                    $cgi_result, 
                                    $cgi_result_nelem,
                                    $miller_rabin_nrounds,
                                    $miller_rabin_p_percent,
                                    $miller_rabin_residual_lt_reciprocal,
                                    $max_cgi_time);
      $style->hrule_std();  

      pfact18_commanate($N);
      do_form($N, "Attempt To Factor Another Integer");
      }
   }

//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 pfact18_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 pfact18_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 (!pfact18_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 pfact18_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 pfact18_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 pfact18_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 (pfact18_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 pfact18_commanate(&$arg)
262			{
263			pfact18_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)
289			{
290			$style->header_title("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)",
291			"Prime Factorization Of An Integer (18 Or Fewer Digits)",
292			"This utility attempts to factor an integer of 18 or fewer digits into its " .
293			"prime components.");
294			}
295
296			function do_footer(&$style)
297			{
298			$style->hrule_std();
299			echo "<p align=\"center\">This utility is powered by the ";
300			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 ";
301			echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
302			$style->footer_std();
303			}
304
305			function do_form($N_refresh, $Buttontext)
306			{
307			echo "<form method=get action=\"pfact18digit.php\" width=\"100%\">\n";
308			echo "<table align=\"center\">\n";
309			echo "<tr>\n";
310			echo " <td width=\"10%\">\n";
311			echo " <p align=\"right\"><b>N</b> (18-digit maximum):</td>\n";
312			echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
313			if (strlen($N_refresh))
314			{
315			echo "value=\"" . $N_refresh . "\" ";
316			}
317			echo "name=\"N\" size=\"50\"></p></td>\n";
318			echo " </tr>\n";
319			echo " <tr>\n";
320			echo " <td width=\"20%\" colspan=\"2\">\n";
321			echo " <p align=\"center\"><input type=\"submit\" value=\"";
322			echo $Buttontext;
323			echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
324			echo " </tr>\n";
325			echo "</table>\n";
326			echo "</form>\n";
327			}
328
329			function do_err_msg($Err_msg)
330			{
331			echo "<p align=\"center\"><b><font color=\"#FF0000\">";
332			echo $Err_msg;
333			echo "</font></b></p>\n";
334			}
335
336			//Prints algorithm notes with no extraneous HTML (no horizontal lines, etc.)
337			//
338			function pfact18_algorithm_notes($cgi_max)
339			{
340			?>
341			<p><b><u>Algorithm Notes:</u></b></p>
342			<ul>
343			<li>This web page uses trial division combined with the
344			<a href="http://mathworld.wolfram.com/EratosthenesSieve.html">Sieve of Eratosthenes</a>
345			with a sieve of 2,310 = 2 * 3 * 5 * 7 * 11 elements.  The
346			sieve is automatically generated, automatically compacted into a
347			difference table containing 480 elements, and packaged as a C-language source
348			file containing a 480-element lookup table of
349			integers.  The algorithm checks divisibility by increasing trial divisors,
350			but it does so with all multiples of 2, 3, 5, 7, and 11 omitted (this is the
351			role of the Sieve of Eratosthenes).</li>
352			<li>Although this web page does factor effectively,
353			it is strictly "parlor amusement" grade, and will answer questions
354			such as <i>Is the year I was born a prime number?</i> or <i>Is my street address
355			prime?</i>, but is inadequate for serious factoring.  Because this CGI-BIN
356			application runs on a shared server, it protects itself by only allowing
357			<?php echo " " . $cgi_max . " "; ?>seconds to elapse while factoring.  The busier
358			the server is, the less actual CPU time is represented by
359			<?php echo " " . $cgi_max . " "; ?>seconds of elapsed time.  This means that
360			factoring operations may be less successful when the server is busy.</li>
361			<li>This utility uses the <a href="http://www.swox.com/gmp">GMP library</a>
362			for arithmetic.  The limit of 18-digit integers is in place so that
363			machine-native integers can be used for the trial divisor (it is more
364			efficient that way, and the GMP provides special function calls
365			for small divisors).  Since the trial divisor need only attain
366			the square root of the number to be factored, any trial divisor for
367			an 18-digit integer will fit in one machine-native integer.</li>
368			</ul>
369			<?php
370			}
371
372			function pfact18_print_tabular_results(&$style,
373			$cgi_result,
374			$cgi_result_nelem,
375			$mr_nrounds,
376			$mr_pcntprime,
377			$mr_recip,
378			$cgi_max)
379			{
380			//Add commas to the number to factor, the number of Miller-Rabin rounds, and
381			//the timeout.
382			pfact18_commanate($cgi_result[1]);
383			pfact18_commanate($cgi_result[2]);
384			pfact18_commanate($cgi_result[3]);
385
386			//Add commas to each prime factor and its multiplicity.
387			$nfactors = ($cgi_result_nelem - 6)/3;
388
389			for ($i=0; $i<$nfactors; $i++)
390			{
391			pfact18_commanate($cgi_result[$i * 3 + 5]);
392			pfact18_commanate($cgi_result[$i * 3 + 6]);
393			}
394
395			//echo "<br>" . $cgi_result_nelem . "<br>";
396
397			//Announce the overall result.
398			$print_table = 0;
399			echo "<p align=\"center\"><font size=\"4\">";
400			if (($cgi_result[$cgi_result_nelem - 5] == "P") && ($cgi_result_nelem == 9) && ($cgi_result[$cgi_result_nelem - 3] == "1"))
401			{
402			echo "The integer " . $cgi_result[1] . " is prime (with 100% certainty).";
403			}
404			elseif (($cgi_result[$cgi_result_nelem - 5] == "p") && ($cgi_result_nelem == 9))
405			{
406			echo "Based on " . $mr_nrounds . " applications of the Miller-Rabin test, the integer ";
407			echo $cgi_result[1] . " is probably (with " . $mr_pcntprime . "% probability) ";
408			echo "prime.  (This means that there is no more than 1 chance ";
409			echo "in " . $mr_recip . " that this integer is composite.)";
410			}
411			elseif (($cgi_result[$cgi_result_nelem - 5] == "C") && ($cgi_result_nelem == 9))
412			{
413			echo "The integer " . $cgi_result[1] . " has been verified by the Miller-Rabin test ";
414			echo "to be composite.  However, ";
415			echo "due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
416			echo "it was not possible to make any progress in factoring ";
417			echo "this integer.  Please try again when the server is less active ";
418			echo "or try another factoring resource.";
419			}
420			elseif ($cgi_result[$cgi_result_nelem - 5] == "P")
421			{
422			echo "The composite integer " ;
423			echo $cgi_result[1] . " was successfully factored into its prime components with ";
424			echo "100% certainty.  Its prime factors and their multiplicities are listed ";
425			echo "in the table below.";
426			$print_table = 1;
427			}
428			elseif ($cgi_result[$cgi_result_nelem - 5] == "p")
429			{
430			echo "The composite integer " ;
431			echo $cgi_result[1] . " was successfully factored into its prime components, ";
432			echo "and these prime components and their multiplicities are listed in the ";
433			echo "table below.  ";
434			echo "The last component listed in the table was judged to be prime based on ";
435			echo $mr_nrounds . " applications of the Miller-Rabin test, meaning that it is ";
436			echo $mr_pcntprime . "% probable ";
437			echo "that this last component is prime (i.e. that there is no more than 1 chance ";
438			echo "in " . $mr_recip . " that it is composite).";
439			$print_table = 1;
440			}
441			elseif ($cgi_result[$cgi_result_nelem - 5] == "C")
442			{
443			echo "Due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
444			echo "the integer ";
445			echo $cgi_result[1] . " could only be partially factored.  In the results below, note that ";
446			echo "the last component ";
447			echo "listed bears the category code <i>C</i> (for <u>c</u>omposite).  Please ";
448			echo " try again when the server is less active ";
449			echo "or try another factoring resource.";
450			$print_table = 1;
451			}
452			echo "</p></font>";
453
454			//Print the table if demanded.
455			if ($print_table)
456			{
457			$style->hrule_std();
458
459			//Assign the table column widths. They are centralized here for easy change.
460			$width[0] = 10;
461			$width[1] = 10;
462			$width[2] = 10;
463			$width[3] = 10;
464
465			echo "<p><table align=\"center\" border=\"1\" width=\"90%\">\n";
466
467			for ($i=0; $i <= ($cgi_result_nelem/3 - 2); $i++)
468			{
469			//Factor number.
470			echo "<tr>\n";
471
472			echo " <td width=\"" . $width[0] . "%\">\n";
473			if ($i==0)
474			{
475			echo " <p align=\"center\"><b>Factor<br>Number</b></p>\n";
476			}
477			else
478			{
479			echo " <p align=\"center\">" . $i . "</p>\n";
480			}
481			echo " </td>\n";
482
483			//Prime Factor
484			echo " <td width=\"" . $width[1] . "%\">\n";
485			if ($i==0)
486			{
487			echo " <p align=\"center\"><b>Component<br>Factor</b></p>\n";
488			}
489			else
490			{
491			echo " <p align=\"center\">" . $cgi_result[$i * 3 + 2] . "</p>\n";
492			}
493			echo " </td>\n";
494
495			//Multiplicity.
496			echo " <td width=\"" . $width[2] . "%\">\n";
497			if ($i==0)
498			{
499			echo " <p align=\"center\"><b>Multiplicity</b></p>\n";
500			}
501			else
502			{
503			echo " <p align=\"center\">" . $cgi_result[$i * 3 + 3] . "</p>\n";
504			}
505			echo " </td>\n";
506
507			//Category code.
508			echo " <td width=\"" . $width[3] . "%\">\n";
509			if ($i==0)
510			{
511			echo " <p align=\"center\"><b>Category<br>Code</b></p>\n";
512			}
513			else
514			{
515			echo " <p align=\"center\">" . $cgi_result[$i * 3 + 1] . "</p>\n";
516			}
517			echo " </td>\n";
518
519
520			echo "</tr>\n";
521			}
522
523			echo "</table></p>\n";
524			echo "<p align=\"center\"><b>Table legend:</b>  <b>P</b>=prime with absolute certainty, ";
525			echo "<b>p</b>=prime established by Miller-Rabin test with ";
526			echo $mr_pcntprime . "% certainty, and <b>C</b>=composite established by Miller-Rabin test ";
527			echo "with absolute certainty, but not factorable in the time allowed.</p>\n";
528
529			$style->hrule_std();
530			pfact18_algorithm_notes($cgi_max);
531			}
532			}
533			//
534			//Main script begins here.
535			//
536			//Let's agree on a number of rounds for the Miller-Rabin test. This influences the
537			//probabilities.
538			$miller_rabin_nrounds = 25;
539			//
540			//Let's agree how long the CGI may take to factor.
541			$max_cgi_time = 10;
542			//
543			//We need to establish the probability that a number which passes the rounds specified
544			//above is still in fact composite. This values need to be calculated by hand whenever
545			//the value above is changed.
546			$miller_rabin_p_real = "0.99999999999999911182";
547			$miller_rabin_p_percent = "99.999999999999911182";
548			$miller_rabin_residual_real = "0.00000000000000088818";
549			$miller_rabin_residual_percent = "0.000000000000088818";
550			$miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624";
551			//
552			$style = new Stdnwpstyle;
553			//Assign the current style in force. Also, starts the CPU
554			//usage clock.
555
556			//Do the header unconditionally. The header is always used on this page.
557			do_header($style);
558			//
559			//
560			//If N was supplied, decommanate it and be sure it is a string.
561			if (isset($N))
562			pfact18_decommanate($N);
563			//
564			//There are a few cases to break into here, and this affects the overall layout of the page.
565			//The header and footer are fixed, but the "guts" will change.
566			if (!isset($N))
567			{
568			//In this case, we are probably visiting the form for the first time, and have not done a submit.
569			//Just display the form itself.
570			do_form("", "Attempt To Factor Integer");
571			}
572			elseif (!pfact18_issimpleint($N))
573			{
574			//N is supplied, but is malformed. Need to advise.
575			do_err_msg("N is a malformed integer.  Choose a new value for N and try again.");
576			$style->hrule_std();
577			pfact18_commanate($N2);
578			do_form($N, "Attempt To Factor Integer");
579			}
580			elseif (strlen($N) > 18)
581			{
582			//N is supplied, but is too long. Need to advise.
583			do_err_msg("N is too long (the maximum is 18 digits).  Choose a new value for N and try again.");
584			$style->hrule_std();
585			pfact18_commanate($N);
586			do_form($N, "Attempt To Factor Integer");
587			}
588			else
589			{
590			//N is supplied and seems to be a valid integer.
591			//
592			//If N is negative, make it positive.
593			if (Substr($N, 0, 1)=="-")
594			$N = Substr($N, 1, strlen($N)-1);
595
596			//If N is "0" or "1", make it "2".
597			if ($N=="0")
598			$N = (string)"1";
599			if ($N=="1")
600			$N = (string)"2";
601
602			//We can now run the external program to do the calculation.
603			$cgi_command_string = "./arith_large_cgi pfact_18 " . $N . " " . $miller_rabin_nrounds . " " . $max_cgi_time;
604			//echo "CGI command string is : " . $cgi_command_string . "<br>\n";
605
606			exec($cgi_command_string, $cgi_result);
607			$cgi_result_nelem = count($cgi_result);
608
609			//echo "Result is : " . $cgi_result_nelem . "<br>\n";
610
611			//for ($i=0; $i<$cgi_result_nelem; $i++)
612			//{
613			// echo $cgi_result[$i] . "<br>\n";
614			//}
615
616			//We need to perform some sanity checks on the CGI output to be sure it
617			//is what we want. If it seems wrong, we need to generate an error message
618			//and not try to display the output.
619			$cgi_output_is_sane = 1;
620			if ($cgi_result_nelem < 9)
621			$cgi_output_is_sane = 0;
622			if ($cgi_result_nelem >= 9)
623			{
624			if (($cgi_result_nelem % 3) != 0)
625			$cgi_output_is_sane = 0;
626			if ($cgi_result[0] != "S")
627			$cgi_output_is_sane = 0;
628			if ($cgi_result[$cgi_result_nelem - 2] != "X")
629			$cgi_output_is_sane = 0;
630			if ($cgi_result[$cgi_result_nelem - 1] != "S")
631			$cgi_output_is_sane = 0;
632			}
633
634			if (!$cgi_output_is_sane)
635			{
636			do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.  Please advise the webmaster.");
637			$style->hrule_std();
638			pfact18_commanate($N);
639			do_form($N, "Attempt To Factor Integer");
640			}
641			else
642			{
643			pfact18_print_tabular_results($style,
644			$cgi_result,
645			$cgi_result_nelem,
646			$miller_rabin_nrounds,
647			$miller_rabin_p_percent,
648			$miller_rabin_residual_lt_reciprocal,
649			$max_cgi_time);
650			$style->hrule_std();
651
652			pfact18_commanate($N);
653			do_form($N, "Attempt To Factor Another Integer");
654			}
655			}
656
657			//Now do the footer unconditionally. The footer is always used on this web page.
658			do_footer($style);
659			?>