num_theory/pfact18digit/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 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	<?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	?>