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 crap without respect for
//whether the commas are in the right place or the integer is syntactically valid.
function miller_rabin_decommanate(&$arg)
{
$temp = "";
$len = strlen($arg);
for ($i=0; $i<$len; $i++)
{
$c = (string)Substr($arg, $i, 1);
if (miller_rabin_isdigit($c) || ($c == "-"))
$temp = $temp . $c;
}
$arg = (string)$temp;
}
//Commanates an integer which is assumed to by syntactically correct.
function miller_rabin_commanate(&$arg)
{
miller_rabin_decommanate($arg);
$temp = "";
$len = strlen($arg);
for ($i=0; $i<$len; $i++)
{
$c = (string)Substr($arg, $len - $i - 1, 1);
$temp = $c . $temp;
if ($i != ($len-1))
{
if (Substr($arg, $len-$i-2, 1) != "-")
{
if (($i % 3) == 2)
$temp = "," . $temp;
}
}
}
$arg = (string)$temp;
}
function do_header(&$style, $miller_rabin_nrounds)
{
$style->header_title("Probable Primality Test (Miller-Rabin)",
"Miller-Rabin Probable Primality Test",
"This utility uses " . $miller_rabin_nrounds . " applications of the " .
"" .
"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->hrule_std();
echo "This utility is powered by the ";
echo "![](\"../genimages/gmplogo1.png\")
. All source code is available ";
echo "here.
\n";
$style->footer_std();
}
function do_form($N_refresh, $Buttontext, $max_digits)
{
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 Stdnwpstyle;
//Assign the current style in force. Also, starts the CPU
//usage clock.
//Do the header unconditionally. The header is always used on this page.
do_header($style, $miller_rabin_nrounds);
//
//
//If N was supplied, decommanate it and be sure it is a string.
if (isset($N))
miller_rabin_decommanate($N);
//
//There are a few cases to break into here, and this affects the overall layout of the page.
//The header and footer are fixed, but the "guts" will change.
if (!isset($N))
{
//In this case, we are probably visiting the form for the first time, and have not done a submit.
//Just display the form itself.
do_form("", "Is This Prime?", $max_digits);
}
elseif (!miller_rabin_issimpleint($N))
{
do_err_msg("N is a malformed integer. Choose a new value for N and try again.");
$style->hrule_std();
miller_rabin_commanate($N);
do_form($N, "Is This Prime?", $max_digits);
}
elseif ($N == "1")
{
do_err_msg("It is not a valid question to ask if 1 is prime. 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->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->hrule_std();
miller_rabin_commanate($N);
do_form($N, "Is This Prime?", $max_digits);
}
else
{
//N seems to be a valid integer.
//
//If N is negative, make it positive.
if (Substr($N, 0, 1)=="-")
$N = Substr($N, 1, strlen($N)-1);
//If N is "0", make it "2".
if ($N=="0")
$N = (string)"2";
//We can now run the external program to do the calculation.
$cgi_command_string = "./arith_large_cgi gmp_prob_prime " . $N . " " . $miller_rabin_nrounds;
//echo "CGI command string is : " . $cgi_command_string . "
\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->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->hrule_std();
?>
Notes on the algorithm:
- It is agreed in number theory that
'1' is neither prime nor
composite. This definition
is largely arbitrary,
and there is some discussion in Usenet newsgroups
such as sci.math from time to time about this topic. It substantially shortens
and neatens many results and proofs to define '1' in this way. For this reason,
this utility refuses to opine on '1'.
- The Miller-Rabin
test and other
strong pseudoprime tests
are part of the backbone of popular
public-key cryptography,
specifically
RSA public-key cryptography,
which relies on the fact that it is much easier to create a large composite number with
large prime components than to factor it.
- This utility uses the mpz_prob_prime_p() function from
the GMP
to make its primality assessment. This function has not been proofread
to verify how it selects bases and applies the Miller-Rabin test. It is assumed
that the standard upper bound of 0.25^N can be applied where N is the reps
parameter to the function (in the case of this utility, reps is
).
- This web site also contains a factorization
utility which will factor integers subject to size and CPU time constraints.
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);
?>