num_theory/pfact18digit/index.php

<?php
require_once("style/std/stdwpstyle.inc");
//----------------------------------------------------------------------------------------------------
//Copyright (c) 2003, 2018 David T. Ashley.
//
//Permission is hereby granted, free of charge, to any person obtaining a copy
//of this software and associated documentation files (the "Software"), to deal
//in the Software without restriction, including without limitation the rights
//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
//copies of the Software, and to permit persons to whom the Software is
//furnished to do so, subject to the following conditions:
//
//The above copyright notice and this permission notice shall be included in all
//copies or substantial portions of the Software.
//
//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
//SOFTWARE.
//----------------------------------------------------------------------------------------------------
//
//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->static_page_header_title_std("[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->static_page_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->static_page_footer_std();
   }

function do_form($N_refresh, $Buttontext)
   {
   echo "<form method=get action=\"index.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->static_page_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->static_page_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 StdWpStyle;
//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 (isset($_GET['N']))
   $N = $_GET['N'];
//
//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->static_page_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->static_page_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 = "/hl/cgibin/aux_progs/dtats_cgi_aux_arith_large 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->static_page_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->static_page_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	dashley	186	require_once("style/std/stdwpstyle.inc");
3			//----------------------------------------------------------------------------------------------------
4			//Copyright (c) 2003, 2018 David T. Ashley.
5	dashley	23	//
6	dashley	186	//Permission is hereby granted, free of charge, to any person obtaining a copy
7			//of this software and associated documentation files (the "Software"), to deal
8			//in the Software without restriction, including without limitation the rights
9			//to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
10			//copies of the Software, and to permit persons to whom the Software is
11			//furnished to do so, subject to the following conditions:
12	dashley	23	//
13	dashley	186	//The above copyright notice and this permission notice shall be included in all
14			//copies or substantial portions of the Software.
15	dashley	23	//
16	dashley	186	//THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17			//IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18			//FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19			//AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20			//LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21			//OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22			//SOFTWARE.
23			//----------------------------------------------------------------------------------------------------
24			//
25	dashley	23	//Returns TRUE if the passed argument is a digit, or FALSE otherwise. If the
26			//passed string has length > 1, only the least significant digit is
27			//considered.
28			function pfact18_isdigit($Digit)
29			{
30			$Digit = (string)$Digit;
31
32			//If the string has zero length, this is an error condition and return 0.
33			$Length = strlen($Digit);
34
35			if ($Length==0)
36			{
37			return(0);
38			}
39
40			//Obtain the trailing character of the string.
41			$Trailing_char = Substr($Digit, $Length-1, 1);
42
43			//Do a switch and return an integer based on the character.
44			switch($Trailing_char)
45			{
46			case "9":
47			return 1;
48			break;
49			case "8":
50			return 1;
51			break;
52			case "7":
53			return 1;
54			break;
55			case "6":
56			return 1;
57			break;
58			case "5":
59			return 1;
60			break;
61			case "4":
62			return 1;
63			break;
64			case "3":
65			return 1;
66			break;
67			case "2":
68			return 1;
69			break;
70			case "1":
71			return 1;
72			break;
73			case "0":
74			return 1;
75			break;
76			default:
77			return 0;
78			break;
79			}
80			}
81			//
82			//
83			//Returns TRUE if the passed argument is a simple integer (no error
84			//codes, no commas), or FALSE otherwise.
85			function pfact18_issimpleint($Intnum)
86			{
87			$Intnum = (string)$Intnum;
88
89			//If the string has zero length, this is an error condition and return 0.
90			$Length = strlen($Intnum);
91
92			if ($Length==0)
93			{
94			return(0);
95			}
96
97			//If the first digit is "0", this must be the only character in the string,
98			//otherwise there is a leading-zero violation.
99			if (Substr($Intnum, 0, 1)=="0")
100			{
101			if ($Length==1)
102			{
103			return 1;
104			}
105			else
106			{
107			return 0;
108			}
109			}
110
111			//If the first character is a "-" sign, it may not be the only character,
112			//and it may not precede a "0" (which would again be a leading 0 violation).
113			//If it is a "-", we can exclude "0" and parse as a positive.
114			if (Substr($Intnum, 0, 1)=="-")
115			{
116			if ($Length==1)
117			{
118			return 0;
119			}
120			else
121			{
122			if (Substr($Intnum, 1, 1) == "0")
123			{
124			//This is illegal (a "-" followed by a "0").
125			return 0;
126			}
127			else
128			{
129			//We can just remove the "-" and parse as a positive.
130			$Intnum = Substr($Intnum, 1, $Length - 1);
131			$Length--;
132			}
133			}
134			}
135
136			//It is known at this point that the length is at least 1 and the leading
137			//character is not zero. All we need to do at this point is check that each
138			//and every character is a digit.
139			for ($index=0; $index < $Length; $index++)
140			{
141			if (!pfact18_isdigit(Substr($Intnum, $index, 1)))
142			return 0;
143			}
144
145			return 1;
146			}
147			//
148			//
149			//Returns the number of digits in the argument, which must be a valid simple
150			//integer.
151			function pfact18_ndigits($Intnum)
152			{
153			$Intnum = (string)$Intnum;
154
155			if (Substr($Intnum, 0, 1) == "-")
156			{
157			$rv = strlen($Intnum) - 1;
158			}
159			else
160			{
161			$rv = strlen($Intnum);
162			}
163
164			return($rv);
165			}
166			//
167			//
168			//Given a string, converts the final character to an integer. If the character
169			//is not a digit, returns 0.
170			function pfact18_digittoint($Digit)
171			{
172			//echo "Digit is: ";
173			//echo $Digit;
174			//echo "<br>";
175
176			$Digit = (string)$Digit;
177
178			//echo "Digit is: ";
179			//echo $Digit;
180			//echo "<br>";
181
182			//If the string has zero length, this is an error condition and return 0.
183			$Length = strlen($Digit);
184
185			//echo "Length is: ";
186			//echo $Length;
187			//echo "<br>";
188
189			if ($Length==0)
190			{
191			return(0);
192			}
193
194			//Obtain the trailing character of the string.
195			$Trailing_char = Substr($Digit, $Length-1, 1);
196
197			//echo "Trailing char is: ";
198			//echo $Trailing_char;
199			//echo "<br>";
200
201			//Do a switch and return an integer based on the character.
202			//The default case gives 0.
203
204			switch($Trailing_char)
205			{
206			case "9":
207			return 9;
208			break;
209			case "8":
210			return 8;
211			break;
212			case "7":
213			return 7;
214			break;
215			case "6":
216			return 6;
217			break;
218			case "5":
219			return 5;
220			break;
221			case "4":
222			return 4;
223			break;
224			case "3":
225			return 3;
226			break;
227			case "2":
228			return 2;
229			break;
230			case "1":
231			return 1;
232			break;
233			default:
234			return 0;
235			break;
236			}
237			}
238
239			//Decommanates an integer and removes all other crap without respect for
240			//whether the commas are in the right place or the integer is syntactically valid.
241			function pfact18_decommanate(&$arg)
242			{
243			$temp = "";
244
245			$len = strlen($arg);
246
247			for ($i=0; $i<$len; $i++)
248			{
249			$c = (string)Substr($arg, $i, 1);
250
251			if (pfact18_isdigit($c) \|\| ($c == "-"))
252			$temp = $temp . $c;
253			}
254
255			$arg = (string)$temp;
256			}
257
258			//Commanates an integer which is assumed to by syntactically correct.
259			function pfact18_commanate(&$arg)
260			{
261			pfact18_decommanate($arg);
262
263			$temp = "";
264
265			$len = strlen($arg);
266
267			for ($i=0; $i<$len; $i++)
268			{
269			$c = (string)Substr($arg, $len - $i - 1, 1);
270
271			$temp = $c . $temp;
272
273			if ($i != ($len-1))
274			{
275			if (Substr($arg, $len-$i-2, 1) != "-")
276			{
277			if (($i % 3) == 2)
278			$temp = "," . $temp;
279			}
280			}
281			}
282
283			$arg = (string)$temp;
284			}
285
286			function do_header(&$style)
287			{
288	dashley	186	$style->static_page_header_title_std("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)",
289	dashley	23	"Prime Factorization Of An Integer (18 Or Fewer Digits)",
290			"This utility attempts to factor an integer of 18 or fewer digits into its " .
291			"prime components.");
292			}
293
294			function do_footer(&$style)
295			{
296	dashley	186	// $style->static_page_hrule_std();
297			// echo "<p align=\"center\">This utility is powered by the ";
298			// 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 ";
299			// echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
300			$style->static_page_footer_std();
301	dashley	23	}
302
303			function do_form($N_refresh, $Buttontext)
304			{
305	dashley	186	echo "<form method=get action=\"index.php\" width=\"100%\">\n";
306	dashley	23	echo "<table align=\"center\">\n";
307			echo "<tr>\n";
308			echo " <td width=\"10%\">\n";
309			echo " <p align=\"right\"><b>N</b> (18-digit maximum):</td>\n";
310			echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
311			if (strlen($N_refresh))
312			{
313			echo "value=\"" . $N_refresh . "\" ";
314			}
315			echo "name=\"N\" size=\"50\"></p></td>\n";
316			echo " </tr>\n";
317			echo " <tr>\n";
318			echo " <td width=\"20%\" colspan=\"2\">\n";
319			echo " <p align=\"center\"><input type=\"submit\" value=\"";
320			echo $Buttontext;
321			echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
322			echo " </tr>\n";
323			echo "</table>\n";
324			echo "</form>\n";
325			}
326
327			function do_err_msg($Err_msg)
328			{
329			echo "<p align=\"center\"><b><font color=\"#FF0000\">";
330			echo $Err_msg;
331			echo "</font></b></p>\n";
332			}
333
334			//Prints algorithm notes with no extraneous HTML (no horizontal lines, etc.)
335			//
336			function pfact18_algorithm_notes($cgi_max)
337			{
338			?>
339			<p><b><u>Algorithm Notes:</u></b></p>
340			<ul>
341			<li>This web page uses trial division combined with the
342			<a href="http://mathworld.wolfram.com/EratosthenesSieve.html">Sieve of Eratosthenes</a>
343			with a sieve of 2,310 = 2 * 3 * 5 * 7 * 11 elements.  The
344			sieve is automatically generated, automatically compacted into a
345			difference table containing 480 elements, and packaged as a C-language source
346			file containing a 480-element lookup table of
347			integers.  The algorithm checks divisibility by increasing trial divisors,
348			but it does so with all multiples of 2, 3, 5, 7, and 11 omitted (this is the
349			role of the Sieve of Eratosthenes).</li>
350			<li>Although this web page does factor effectively,
351			it is strictly "parlor amusement" grade, and will answer questions
352			such as <i>Is the year I was born a prime number?</i> or <i>Is my street address
353			prime?</i>, but is inadequate for serious factoring.  Because this CGI-BIN
354			application runs on a shared server, it protects itself by only allowing
355			<?php echo " " . $cgi_max . " "; ?>seconds to elapse while factoring.  The busier
356			the server is, the less actual CPU time is represented by
357			<?php echo " " . $cgi_max . " "; ?>seconds of elapsed time.  This means that
358			factoring operations may be less successful when the server is busy.</li>
359			<li>This utility uses the <a href="http://www.swox.com/gmp">GMP library</a>
360			for arithmetic.  The limit of 18-digit integers is in place so that
361			machine-native integers can be used for the trial divisor (it is more
362			efficient that way, and the GMP provides special function calls
363			for small divisors).  Since the trial divisor need only attain
364			the square root of the number to be factored, any trial divisor for
365			an 18-digit integer will fit in one machine-native integer.</li>
366			</ul>
367			<?php
368			}
369
370			function pfact18_print_tabular_results(&$style,
371			$cgi_result,
372			$cgi_result_nelem,
373			$mr_nrounds,
374			$mr_pcntprime,
375			$mr_recip,
376			$cgi_max)
377			{
378			//Add commas to the number to factor, the number of Miller-Rabin rounds, and
379			//the timeout.
380			pfact18_commanate($cgi_result[1]);
381			pfact18_commanate($cgi_result[2]);
382			pfact18_commanate($cgi_result[3]);
383
384			//Add commas to each prime factor and its multiplicity.
385			$nfactors = ($cgi_result_nelem - 6)/3;
386
387			for ($i=0; $i<$nfactors; $i++)
388			{
389			pfact18_commanate($cgi_result[$i * 3 + 5]);
390			pfact18_commanate($cgi_result[$i * 3 + 6]);
391			}
392
393			//echo "<br>" . $cgi_result_nelem . "<br>";
394
395			//Announce the overall result.
396			$print_table = 0;
397			echo "<p align=\"center\"><font size=\"4\">";
398			if (($cgi_result[$cgi_result_nelem - 5] == "P") && ($cgi_result_nelem == 9) && ($cgi_result[$cgi_result_nelem - 3] == "1"))
399			{
400			echo "The integer " . $cgi_result[1] . " is prime (with 100% certainty).";
401			}
402			elseif (($cgi_result[$cgi_result_nelem - 5] == "p") && ($cgi_result_nelem == 9))
403			{
404			echo "Based on " . $mr_nrounds . " applications of the Miller-Rabin test, the integer ";
405			echo $cgi_result[1] . " is probably (with " . $mr_pcntprime . "% probability) ";
406			echo "prime.  (This means that there is no more than 1 chance ";
407			echo "in " . $mr_recip . " that this integer is composite.)";
408			}
409			elseif (($cgi_result[$cgi_result_nelem - 5] == "C") && ($cgi_result_nelem == 9))
410			{
411			echo "The integer " . $cgi_result[1] . " has been verified by the Miller-Rabin test ";
412			echo "to be composite.  However, ";
413			echo "due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
414			echo "it was not possible to make any progress in factoring ";
415			echo "this integer.  Please try again when the server is less active ";
416			echo "or try another factoring resource.";
417			}
418			elseif ($cgi_result[$cgi_result_nelem - 5] == "P")
419			{
420			echo "The composite integer " ;
421			echo $cgi_result[1] . " was successfully factored into its prime components with ";
422			echo "100% certainty.  Its prime factors and their multiplicities are listed ";
423			echo "in the table below.";
424			$print_table = 1;
425			}
426			elseif ($cgi_result[$cgi_result_nelem - 5] == "p")
427			{
428			echo "The composite integer " ;
429			echo $cgi_result[1] . " was successfully factored into its prime components, ";
430			echo "and these prime components and their multiplicities are listed in the ";
431			echo "table below.  ";
432			echo "The last component listed in the table was judged to be prime based on ";
433			echo $mr_nrounds . " applications of the Miller-Rabin test, meaning that it is ";
434			echo $mr_pcntprime . "% probable ";
435			echo "that this last component is prime (i.e. that there is no more than 1 chance ";
436			echo "in " . $mr_recip . " that it is composite).";
437			$print_table = 1;
438			}
439			elseif ($cgi_result[$cgi_result_nelem - 5] == "C")
440			{
441			echo "Due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), ";
442			echo "the integer ";
443			echo $cgi_result[1] . " could only be partially factored.  In the results below, note that ";
444			echo "the last component ";
445			echo "listed bears the category code <i>C</i> (for <u>c</u>omposite).  Please ";
446			echo " try again when the server is less active ";
447			echo "or try another factoring resource.";
448			$print_table = 1;
449			}
450			echo "</p></font>";
451
452			//Print the table if demanded.
453			if ($print_table)
454			{
455	dashley	186	$style->static_page_hrule_std();
456	dashley	23
457			//Assign the table column widths. They are centralized here for easy change.
458			$width[0] = 10;
459			$width[1] = 10;
460			$width[2] = 10;
461			$width[3] = 10;
462
463			echo "<p><table align=\"center\" border=\"1\" width=\"90%\">\n";
464
465			for ($i=0; $i <= ($cgi_result_nelem/3 - 2); $i++)
466			{
467			//Factor number.
468			echo "<tr>\n";
469
470			echo " <td width=\"" . $width[0] . "%\">\n";
471			if ($i==0)
472			{
473			echo " <p align=\"center\"><b>Factor<br>Number</b></p>\n";
474			}
475			else
476			{
477			echo " <p align=\"center\">" . $i . "</p>\n";
478			}
479			echo " </td>\n";
480
481			//Prime Factor
482			echo " <td width=\"" . $width[1] . "%\">\n";
483			if ($i==0)
484			{
485			echo " <p align=\"center\"><b>Component<br>Factor</b></p>\n";
486			}
487			else
488			{
489			echo " <p align=\"center\">" . $cgi_result[$i * 3 + 2] . "</p>\n";
490			}
491			echo " </td>\n";
492
493			//Multiplicity.
494			echo " <td width=\"" . $width[2] . "%\">\n";
495			if ($i==0)
496			{
497			echo " <p align=\"center\"><b>Multiplicity</b></p>\n";
498			}
499			else
500			{
501			echo " <p align=\"center\">" . $cgi_result[$i * 3 + 3] . "</p>\n";
502			}
503			echo " </td>\n";
504
505			//Category code.
506			echo " <td width=\"" . $width[3] . "%\">\n";
507			if ($i==0)
508			{
509			echo " <p align=\"center\"><b>Category<br>Code</b></p>\n";
510			}
511			else
512			{
513			echo " <p align=\"center\">" . $cgi_result[$i * 3 + 1] . "</p>\n";
514			}
515			echo " </td>\n";
516
517
518			echo "</tr>\n";
519			}
520
521			echo "</table></p>\n";
522			echo "<p align=\"center\"><b>Table legend:</b>  <b>P</b>=prime with absolute certainty, ";
523			echo "<b>p</b>=prime established by Miller-Rabin test with ";
524			echo $mr_pcntprime . "% certainty, and <b>C</b>=composite established by Miller-Rabin test ";
525			echo "with absolute certainty, but not factorable in the time allowed.</p>\n";
526
527	dashley	186	$style->static_page_hrule_std();
528	dashley	23	pfact18_algorithm_notes($cgi_max);
529			}
530			}
531			//
532			//Main script begins here.
533			//
534			//Let's agree on a number of rounds for the Miller-Rabin test. This influences the
535			//probabilities.
536			$miller_rabin_nrounds = 25;
537			//
538			//Let's agree how long the CGI may take to factor.
539			$max_cgi_time = 10;
540			//
541			//We need to establish the probability that a number which passes the rounds specified
542			//above is still in fact composite. This values need to be calculated by hand whenever
543			//the value above is changed.
544			$miller_rabin_p_real = "0.99999999999999911182";
545			$miller_rabin_p_percent = "99.999999999999911182";
546			$miller_rabin_residual_real = "0.00000000000000088818";
547			$miller_rabin_residual_percent = "0.000000000000088818";
548			$miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624";
549			//
550	dashley	186	$style = new StdWpStyle;
551	dashley	23	//Assign the current style in force. Also, starts the CPU
552			//usage clock.
553
554			//Do the header unconditionally. The header is always used on this page.
555			do_header($style);
556			//
557	dashley	186	if (isset($_GET['N']))
558			$N = $_GET['N'];
559	dashley	23	//
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	dashley	186	$style->static_page_hrule_std();
577	dashley	23	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	dashley	186	$style->static_page_hrule_std();
585	dashley	23	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	dashley	186	$cgi_command_string = "/hl/cgibin/aux_progs/dtats_cgi_aux_arith_large pfact_18 " . $N . " " . $miller_rabin_nrounds . " " . $max_cgi_time;
604	dashley	23	//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	dashley	186	$style->static_page_hrule_std();
638	dashley	23	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	dashley	186	$style->static_page_hrule_std();
651	dashley	23
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			?>