1, only the least significant digit is //considered. function miller_rabin_isdigit($Digit) { $Digit = (string)$Digit; //If the string has zero length, this is an error condition and return 0. $Length = strlen($Digit); if ($Length==0) { return(0); } //Obtain the trailing character of the string. $Trailing_char = Substr($Digit, $Length-1, 1); //Do a switch and return an integer based on the character. switch($Trailing_char) { case "9": return 1; break; case "8": return 1; break; case "7": return 1; break; case "6": return 1; break; case "5": return 1; break; case "4": return 1; break; case "3": return 1; break; case "2": return 1; break; case "1": return 1; break; case "0": return 1; break; default: return 0; break; } } // // //Returns TRUE if the passed argument is a simple integer (no error //codes, no commas), or FALSE otherwise. function miller_rabin_issimpleint($Intnum) { $Intnum = (string)$Intnum; //If the string has zero length, this is an error condition and return 0. $Length = strlen($Intnum); if ($Length==0) { return(0); } //If the first digit is "0", this must be the only character in the string, //otherwise there is a leading-zero violation. if (Substr($Intnum, 0, 1)=="0") { if ($Length==1) { return 1; } else { return 0; } } //If the first character is a "-" sign, it may not be the only character, //and it may not precede a "0" (which would again be a leading 0 violation). //If it is a "-", we can exclude "0" and parse as a positive. if (Substr($Intnum, 0, 1)=="-") { if ($Length==1) { return 0; } else { if (Substr($Intnum, 1, 1) == "0") { //This is illegal (a "-" followed by a "0"). return 0; } else { //We can just remove the "-" and parse as a positive. $Intnum = Substr($Intnum, 1, $Length - 1); $Length--; } } } //It is known at this point that the length is at least 1 and the leading //character is not zero. All we need to do at this point is check that each //and every character is a digit. for ($index=0; $index < $Length; $index++) { if (!miller_rabin_isdigit(Substr($Intnum, $index, 1))) return 0; } return 1; } // // //Returns the number of digits in the argument, which must be a valid simple //integer. function miller_rabin_ndigits($Intnum) { $Intnum = (string)$Intnum; if (Substr($Intnum, 0, 1) == "-") { $rv = strlen($Intnum) - 1; } else { $rv = strlen($Intnum); } return($rv); } // // //Given a string, converts the final character to an integer. If the character //is not a digit, returns 0. function miller_rabin_digittoint($Digit) { //echo "Digit is: "; //echo $Digit; //echo "
"; $Digit = (string)$Digit; //echo "Digit is: "; //echo $Digit; //echo "
"; //If the string has zero length, this is an error condition and return 0. $Length = strlen($Digit); //echo "Length is: "; //echo $Length; //echo "
"; 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 "
"; //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 extraneous characters without respect for //whether the commas are in the right place or the integer is syntactically valid. function miller_rabin_decommanate(&$arg) { $temp = ""; $len = strlen($arg); for ($i=0; $i<$len; $i++) { $c = (string)Substr($arg, $i, 1); if (miller_rabin_isdigit($c) || ($c == "-")) $temp = $temp . $c; } $arg = (string)$temp; } //Commanates an integer which is assumed to by syntactically correct. function miller_rabin_commanate(&$arg) { miller_rabin_decommanate($arg); $temp = ""; $len = strlen($arg); for ($i=0; $i<$len; $i++) { $c = (string)Substr($arg, $len - $i - 1, 1); $temp = $c . $temp; if ($i != ($len-1)) { if (Substr($arg, $len-$i-2, 1) != "-") { if (($i % 3) == 2) $temp = "," . $temp; } } } $arg = (string)$temp; } function do_header(&$style, $miller_rabin_nrounds) { $style->static_page_header_title_std("Probable Primality Test (Miller-Rabin)", "Miller-Rabin Probable Primality Test", "This utility uses " . $miller_rabin_nrounds . " applications of the " . "" . "Miller-Rabin test to determine " . "with high probabilistic certainty whether an integer " . "is " . "prime or " . "composite." . "  This utility does not " . "factor composite numbers."); } function do_footer(&$style) { // $style->static_page_hrule_std(); // echo "

This utility is powered by the "; // echo ".  All source code is available "; // echo "here.

\n"; $style->static_page_footer_std(); } function do_form($N_refresh, $Buttontext, $max_digits) { echo "
\n"; echo "\n"; echo "\n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo " \n"; echo "
\n"; echo "

N (" . number_format($max_digits) . "-digit maximum):

\n"; echo "

\n"; echo "
\n"; } function do_err_msg($Err_msg) { echo "

"; echo $Err_msg; echo "

\n"; } //Main script begins here. // // //Let's agree on a maximum for number of digits in the number to test. It is known that //Apache won't process URL's larger than 1024, so let's be conservative and say 500 //digits. $max_digits = 500; // //Let's agree on a number of rounds for the Miller-Rabin test. This influences the //probabilities. $miller_rabin_nrounds = 25; // //We need to establish the probability that a number which passes the rounds specified //above is still in fact composite. This values need to be calculated by hand whenever //the value above is changed. $miller_rabin_p_real = "0.99999999999999911182"; $miller_rabin_p_percent = "99.999999999999911182"; $miller_rabin_residual_real = "0.00000000000000088818"; $miller_rabin_residual_percent = "0.000000000000088818"; $miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624"; // $style = new 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, $miller_rabin_nrounds); // if (isset($_GET['N'])) $N = $_GET['N']; // //If N was supplied, decommanate it and be sure it is a string. if (isset($N)) miller_rabin_decommanate($N); // //There are a few cases to break into here, and this affects the overall layout of the page. //The header and footer are fixed, but the "guts" will change. if (!isset($N)) { //In this case, we are probably visiting the form for the first time, and have not done a submit. //Just display the form itself. do_form("", "Is This Prime?", $max_digits); } elseif (!miller_rabin_issimpleint($N)) { do_err_msg("N is a malformed integer.  Choose a new value for N and try again."); $style->static_page_hrule_std(); miller_rabin_commanate($N); do_form($N, "Is This Prime?", $max_digits); } elseif ($N == "1") { do_err_msg("It is not a valid question to ask if 1 is prime.  It is agreed " . "in number theory (largely to minimize exception cases in proofs and results) " . "that 1 is neither prime nor composite.  " . "Choose a new value for N and try again."); $style->static_page_hrule_std(); miller_rabin_commanate($N); do_form($N, "Is This Prime?", $max_digits); } elseif (strlen($N) > $max_digits) { do_err_msg("N is too long (a " . number_format($max_digits) . "-digit maximum is " . "in effect).  Choose a shorter value and try again."); $style->static_page_hrule_std(); miller_rabin_commanate($N); do_form($N, "Is This Prime?", $max_digits); } else { //N seems to be a valid integer. // //If N is negative, make it positive. if (Substr($N, 0, 1)=="-") $N = Substr($N, 1, strlen($N)-1); //If N is "0", make it "2". if ($N=="0") $N = (string)"2"; //We can now run the external program to do the calculation. $cgi_command_string = "/hl/cgibin/aux_progs/dtats_cgi_aux_arith_large gmp_prob_prime " . $N . " " . $miller_rabin_nrounds; //echo "CGI command string is : " . $cgi_command_string . "
\n"; exec($cgi_command_string, $cgi_result); $cgi_result_nelem = count($cgi_result); //echo "Result is : " . $cgi_result_nelem . "
\n"; //for ($i=0; $i<$cgi_result_nelem; $i++) //{ // echo $cgi_result[$i] . "
\n"; //} //We need to perform some sanity checks on the CGI output to be sure it //is what we want. If it seems wrong, we need to generate an error message //and not try to display the output. $cgi_output_is_sane = 1; if ($cgi_result_nelem == 0) $cgi_output_is_sane = 0; if ($cgi_result_nelem > 0) { if ($cgi_result_nelem != 5) $cgi_output_is_sane = 0; if ($cgi_result[0] != "S") $cgi_output_is_sane = 0; if (($cgi_result[3] != "0") && ($cgi_result[3] != "1") && ($cgi_result[3] != "2")) $cgi_output_is_sane = 0; if ($cgi_result[4] != "S") $cgi_output_is_sane = 0; } if (!$cgi_output_is_sane) { do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.  Please advise the webmaster."); $style->static_page_hrule_std(); miller_rabin_commanate($N); do_form($N, "Is This Prime", $max_digits); } else { miller_rabin_commanate($cgi_result[1]); if ($cgi_result[3] == 0) { echo "

The integer "; echo $cgi_result[1]; echo " is definitely (with 100% certainty) composite.  Note, however, that although "; echo "it was relatively computationally inexpensive to determine that this integer is composite, "; echo "factoring it may be computationally much more expensive.

\n"; } elseif ($cgi_result[3] == 1) { echo "

Based on " . $miller_rabin_nrounds . " applications of "; echo "the Miller-Rabin test, the integer "; echo $cgi_result[1]; echo " is probably (with " . $miller_rabin_p_percent . "% certainty) "; echo "prime.  (This means that there is no more than 1 chance in "; echo $miller_rabin_residual_lt_reciprocal . " that this integer is "; echo "composite.)

\n"; } else { echo "

The integer "; echo $cgi_result[1]; echo " is prime (with 100% certainty).  This means that the "; echo "GMP"; echo " library routine was able to attempt trial division with divisors "; echo "up to floor(sqrt(N)).

\n"; } $style->static_page_hrule_std(); ?>

Notes on the algorithm:

static_page_hrule_std(); miller_rabin_commanate($N); do_form($N, "Is This Prime?", $max_digits); } } //Now do the footer unconditionally. The footer is always used on this web page. do_footer($style); ?>