/[dtapublic]/projs/dtats/trunk/projs/2018/20180707_cgi_web_tools/active/num_theory/miller_rabin/index.php
ViewVC logotype

Contents of /projs/dtats/trunk/projs/2018/20180707_cgi_web_tools/active/num_theory/miller_rabin/index.php

Parent Directory Parent Directory | Revision Log Revision Log


Revision 189 - (show annotations) (download)
Sat Jul 14 00:27:21 2018 UTC (6 years, 4 months ago) by dashley
File size: 16525 byte(s)
Move Miller-Rabin test to active pages.
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 miller_rabin_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 miller_rabin_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 (!miller_rabin_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 miller_rabin_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 miller_rabin_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 miller_rabin_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 (miller_rabin_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 miller_rabin_commanate(&$arg)
262 {
263 miller_rabin_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, $miller_rabin_nrounds)
289 {
290 $style->header_title("Probable Primality Test (Miller-Rabin)",
291 "Miller-Rabin Probable Primality Test",
292 "This utility uses " . $miller_rabin_nrounds . " applications of the " .
293 "<a href=\"http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html\">" .
294 "Miller-Rabin test</a> to determine " .
295 "with high probabilistic certainty whether an integer " .
296 "is " .
297 "<a href=\"http://mathworld.wolfram.com/PrimeNumber.html\">prime</a> or " .
298 "<a href=\"http://mathworld.wolfram.com/CompositeNumber.html\">composite</a>." .
299 "&nbsp; This utility does <i>not</i> " .
300 "factor composite numbers.");
301 }
302
303 function do_footer(&$style)
304 {
305 $style->hrule_std();
306 echo "<p align=\"center\">This utility is powered by the ";
307 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 ";
308 echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n";
309 $style->footer_std();
310 }
311
312 function do_form($N_refresh, $Buttontext, $max_digits)
313 {
314 echo "<form method=get action=\"miller_rabin.php\" width=\"100%\">\n";
315 echo "<table align=\"center\">\n";
316 echo "<tr>\n";
317 echo " <td width=\"10%\">\n";
318 echo " <p align=\"right\"><b>N</b> (" . number_format($max_digits) . "-digit maximum):</td>\n";
319 echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" ";
320 if (strlen($N_refresh))
321 {
322 echo "value=\"" . $N_refresh . "\" ";
323 }
324 echo "name=\"N\" size=\"50\"></p></td>\n";
325 echo " </tr>\n";
326 echo " <tr>\n";
327 echo " <td width=\"20%\" colspan=\"2\">\n";
328 echo " <p align=\"center\"><input type=\"submit\" value=\"";
329 echo $Buttontext;
330 echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n";
331 echo " </tr>\n";
332 echo "</table>\n";
333 echo "</form>\n";
334 }
335
336 function do_err_msg($Err_msg)
337 {
338 echo "<p align=\"center\"><b><font color=\"#FF0000\">";
339 echo $Err_msg;
340 echo "</font></b></p>\n";
341 }
342
343
344 //Main script begins here.
345 //
346 //
347 //Let's agree on a maximum for number of digits in the number to test. It is known that
348 //Apache won't process URL's larger than 1024, so let's be conservative and say 500
349 //digits.
350 $max_digits = 500;
351 //
352 //Let's agree on a number of rounds for the Miller-Rabin test. This influences the
353 //probabilities.
354 $miller_rabin_nrounds = 25;
355 //
356 //We need to establish the probability that a number which passes the rounds specified
357 //above is still in fact composite. This values need to be calculated by hand whenever
358 //the value above is changed.
359 $miller_rabin_p_real = "0.99999999999999911182";
360 $miller_rabin_p_percent = "99.999999999999911182";
361 $miller_rabin_residual_real = "0.00000000000000088818";
362 $miller_rabin_residual_percent = "0.000000000000088818";
363 $miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624";
364 //
365 $style = new Stdnwpstyle;
366 //Assign the current style in force. Also, starts the CPU
367 //usage clock.
368
369 //Do the header unconditionally. The header is always used on this page.
370 do_header($style, $miller_rabin_nrounds);
371 //
372 //
373 //If N was supplied, decommanate it and be sure it is a string.
374 if (isset($N))
375 miller_rabin_decommanate($N);
376 //
377 //There are a few cases to break into here, and this affects the overall layout of the page.
378 //The header and footer are fixed, but the "guts" will change.
379 if (!isset($N))
380 {
381 //In this case, we are probably visiting the form for the first time, and have not done a submit.
382 //Just display the form itself.
383 do_form("", "Is This Prime?", $max_digits);
384 }
385 elseif (!miller_rabin_issimpleint($N))
386 {
387 do_err_msg("N is a malformed integer. &nbsp;Choose a new value for N and try again.");
388 $style->hrule_std();
389 miller_rabin_commanate($N);
390 do_form($N, "Is This Prime?", $max_digits);
391 }
392 elseif ($N == "1")
393 {
394 do_err_msg("It is not a valid question to ask if 1 is prime.&nbsp; It is agreed " .
395 "in number theory (largely to minimize exception cases in proofs and results) " .
396 "that 1 is neither prime nor composite.&nbsp; " .
397 "Choose a new value for N and try again.");
398 $style->hrule_std();
399 miller_rabin_commanate($N);
400 do_form($N, "Is This Prime?", $max_digits);
401 }
402 elseif (strlen($N) > $max_digits)
403 {
404 do_err_msg("N is too long (a " . number_format($max_digits) . "-digit maximum is " .
405 "in effect).&nbsp; Choose a shorter value and try again.");
406 $style->hrule_std();
407 miller_rabin_commanate($N);
408 do_form($N, "Is This Prime?", $max_digits);
409 }
410 else
411 {
412 //N seems to be a valid integer.
413 //
414 //If N is negative, make it positive.
415 if (Substr($N, 0, 1)=="-")
416 $N = Substr($N, 1, strlen($N)-1);
417
418 //If N is "0", make it "2".
419 if ($N=="0")
420 $N = (string)"2";
421
422 //We can now run the external program to do the calculation.
423 $cgi_command_string = "./arith_large_cgi gmp_prob_prime " . $N . " " . $miller_rabin_nrounds;
424
425 //echo "CGI command string is : " . $cgi_command_string . "<br>\n";
426
427 exec($cgi_command_string, $cgi_result);
428 $cgi_result_nelem = count($cgi_result);
429
430 //echo "Result is : " . $cgi_result_nelem . "<br>\n";
431
432 //for ($i=0; $i<$cgi_result_nelem; $i++)
433 //{
434 // echo $cgi_result[$i] . "<br>\n";
435 //}
436
437 //We need to perform some sanity checks on the CGI output to be sure it
438 //is what we want. If it seems wrong, we need to generate an error message
439 //and not try to display the output.
440 $cgi_output_is_sane = 1;
441 if ($cgi_result_nelem == 0)
442 $cgi_output_is_sane = 0;
443 if ($cgi_result_nelem > 0)
444 {
445 if ($cgi_result_nelem != 5)
446 $cgi_output_is_sane = 0;
447 if ($cgi_result[0] != "S")
448 $cgi_output_is_sane = 0;
449 if (($cgi_result[3] != "0") && ($cgi_result[3] != "1") && ($cgi_result[3] != "2"))
450 $cgi_output_is_sane = 0;
451 if ($cgi_result[4] != "S")
452 $cgi_output_is_sane = 0;
453 }
454
455 if (!$cgi_output_is_sane)
456 {
457 do_err_msg("An unspecified error occurred when interacting with the CGI-BIN program.&nbsp; Please advise the webmaster.");
458 $style->hrule_std();
459 miller_rabin_commanate($N);
460 do_form($N, "Is This Prime", $max_digits);
461 }
462 else
463 {
464 miller_rabin_commanate($cgi_result[1]);
465
466 if ($cgi_result[3] == 0)
467 {
468 echo "<p align=\"center\"><font size=\"4\">The integer ";
469 echo $cgi_result[1];
470 echo " is definitely (with 100% certainty) composite.&nbsp; Note, however, that although ";
471 echo "it was relatively computationally inexpensive to determine that this integer is composite, ";
472 echo "factoring it may be computationally <i>much</i> more expensive.</font></p>\n";
473 }
474 elseif ($cgi_result[3] == 1)
475 {
476 echo "<p align=\"center\"><font size=\"4\">Based on " . $miller_rabin_nrounds . " applications of ";
477 echo "the Miller-Rabin test, the integer ";
478 echo $cgi_result[1];
479 echo " is probably (with " . $miller_rabin_p_percent . "% certainty) ";
480 echo "prime.&nbsp; (This means that there is no more than 1 chance in ";
481 echo $miller_rabin_residual_lt_reciprocal . " that this integer is ";
482 echo "composite.)</font></p>\n";
483 }
484 else
485 {
486 echo "<p align=\"center\"><font size=\"4\">The integer ";
487 echo $cgi_result[1];
488 echo " is prime (with 100% certainty).&nbsp; This means that the ";
489 echo "GMP";
490 echo " library routine was able to attempt trial division with divisors ";
491 echo "up to <i>floor</i>(<i>sqrt</i>(N)).</font></p>\n";
492 }
493
494 $style->hrule_std();
495 ?>
496 <p align="left"><b>Notes on the algorithm:</b>
497 <ul>
498 <li>It is agreed in number theory that
499 <a href="http://www.mth.uct.ac.za/~digest/faq/prime.html">'1' is neither prime nor
500 composite</a>.&nbsp; This definition
501 is largely <a href="http://dictionary.reference.com/search?q=arbitrary">arbitrary</a>,
502 and there is some discussion in Usenet newsgroups
503 such as <i>sci.math</i> from time to time about this topic.&nbsp; It substantially shortens
504 and neatens many results and proofs to define '1' in this way.&nbsp; For this reason,
505 this utility refuses to <a href="http://dictionary.reference.com/search?q=opine">opine</a> on '1'.
506 </li>
507 <li>The <a href="http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html">Miller-Rabin
508 test</a> and other
509 <a href="http://mathworld.wolfram.com/StrongPseudoprime.html">strong pseudoprime</a> tests
510 are part of the backbone of popular
511 <a href="http://mathworld.wolfram.com/Public-KeyCryptography.html">public-key cryptography</a>,
512 specifically
513 <a href="http://mathworld.wolfram.com/RSAEncryption.html">RSA public-key cryptography</a>,
514 which relies on the fact that it is much easier to create a large composite number with
515 large prime components than to factor it.
516 </li>
517 <li>This utility uses the <i>mpz_prob_prime_p()</i> function from
518 the <a href="http://www.swox.com/gmp">GMP</a>
519 to make its primality assessment.&nbsp; This function has not been proofread
520 to verify how it selects bases and applies the Miller-Rabin test.&nbsp; It is assumed
521 that the standard upper bound of 0.25^N can be applied where N is the <i>reps</i>
522 parameter to the function (in the case of this utility, <i>reps</i> is
523 <?php echo " " . $miller_rabin_nrounds ; ?>).
524 </li>
525 <li>This web site also contains a <a href="pfact18digit.php">factorization
526 utility</a> which will factor integers subject to size and CPU time constraints.
527 </ul>
528 <?php
529 $style->hrule_std();
530
531 miller_rabin_commanate($N);
532 do_form($N, "Is This Prime?", $max_digits);
533 }
534 }
535
536 //Now do the footer unconditionally. The footer is always used on this web page.
537 do_footer($style);
538 ?>

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25