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

Annotation 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 165 - (hide annotations) (download)
Sat Jul 7 22:49:13 2018 UTC (6 years, 5 months ago) by dashley
Original Path: projs/dtats/trunk/projs/2018/20180707_cgi_web_tools/to_be_filed/sf_phpcgibin/miller_rabin.php
File size: 16525 byte(s)
Reorganize.
1 dashley 23 <?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