1 |
<?php |
2 |
require_once("style/std/stdwpstyle.inc"); |
3 |
//---------------------------------------------------------------------------------------------------- |
4 |
//Copyright (c) 2003, 2018 David T. Ashley. |
5 |
// |
6 |
//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 |
// |
13 |
//The above copyright notice and this permission notice shall be included in all |
14 |
//copies or substantial portions of the Software. |
15 |
// |
16 |
//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 |
//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 |
$style->static_page_header_title_std("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)", |
289 |
"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 |
// $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 |
} |
302 |
|
303 |
function do_form($N_refresh, $Buttontext) |
304 |
{ |
305 |
echo "<form method=get action=\"index.php\" width=\"100%\">\n"; |
306 |
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 |
$style->static_page_hrule_std(); |
456 |
|
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 |
$style->static_page_hrule_std(); |
528 |
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 |
$style = new StdWpStyle; |
551 |
//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 |
if (isset($_GET['N'])) |
558 |
$N = $_GET['N']; |
559 |
// |
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 |
$style->static_page_hrule_std(); |
577 |
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 |
$style->static_page_hrule_std(); |
585 |
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 |
$cgi_command_string = "/hl/cgibin/aux_progs/dtats_cgi_aux_arith_large pfact_18 " . $N . " " . $miller_rabin_nrounds . " " . $max_cgi_time; |
604 |
//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 |
$style->static_page_hrule_std(); |
638 |
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 |
$style->static_page_hrule_std(); |
651 |
|
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 |
?> |