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 pfact18_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 pfact18_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 (!pfact18_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 pfact18_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 pfact18_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 pfact18_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 (pfact18_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 pfact18_commanate(&$arg) |
262 |
|
|
{ |
263 |
|
|
pfact18_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) |
289 |
|
|
{ |
290 |
|
|
$style->header_title("[Attempted] Prime Factorization Of An Integer (18 Or Fewer Digits)", |
291 |
|
|
"Prime Factorization Of An Integer (18 Or Fewer Digits)", |
292 |
|
|
"This utility attempts to factor an integer of 18 or fewer digits into its " . |
293 |
|
|
"prime components."); |
294 |
|
|
} |
295 |
|
|
|
296 |
|
|
function do_footer(&$style) |
297 |
|
|
{ |
298 |
|
|
$style->hrule_std(); |
299 |
|
|
echo "<p align=\"center\">This utility is powered by the "; |
300 |
|
|
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 "; |
301 |
|
|
echo "<a href=\"../howtos/nth_web_gmp_src_code_dist/obtain_all_source.htm\">here</a>.</p>\n"; |
302 |
|
|
$style->footer_std(); |
303 |
|
|
} |
304 |
|
|
|
305 |
|
|
function do_form($N_refresh, $Buttontext) |
306 |
|
|
{ |
307 |
|
|
echo "<form method=get action=\"pfact18digit.php\" width=\"100%\">\n"; |
308 |
|
|
echo "<table align=\"center\">\n"; |
309 |
|
|
echo "<tr>\n"; |
310 |
|
|
echo " <td width=\"10%\">\n"; |
311 |
|
|
echo " <p align=\"right\"><b>N</b> (18-digit maximum):</td>\n"; |
312 |
|
|
echo " <td width=\"18%\"><p align=\"left\"><input type=\"text\" "; |
313 |
|
|
if (strlen($N_refresh)) |
314 |
|
|
{ |
315 |
|
|
echo "value=\"" . $N_refresh . "\" "; |
316 |
|
|
} |
317 |
|
|
echo "name=\"N\" size=\"50\"></p></td>\n"; |
318 |
|
|
echo " </tr>\n"; |
319 |
|
|
echo " <tr>\n"; |
320 |
|
|
echo " <td width=\"20%\" colspan=\"2\">\n"; |
321 |
|
|
echo " <p align=\"center\"><input type=\"submit\" value=\""; |
322 |
|
|
echo $Buttontext; |
323 |
|
|
echo "\" name=\"B1\" style=\"margin-top: 12\"></td>\n"; |
324 |
|
|
echo " </tr>\n"; |
325 |
|
|
echo "</table>\n"; |
326 |
|
|
echo "</form>\n"; |
327 |
|
|
} |
328 |
|
|
|
329 |
|
|
function do_err_msg($Err_msg) |
330 |
|
|
{ |
331 |
|
|
echo "<p align=\"center\"><b><font color=\"#FF0000\">"; |
332 |
|
|
echo $Err_msg; |
333 |
|
|
echo "</font></b></p>\n"; |
334 |
|
|
} |
335 |
|
|
|
336 |
|
|
//Prints algorithm notes with no extraneous HTML (no horizontal lines, etc.) |
337 |
|
|
// |
338 |
|
|
function pfact18_algorithm_notes($cgi_max) |
339 |
|
|
{ |
340 |
|
|
?> |
341 |
|
|
<p><b><u>Algorithm Notes:</u></b></p> |
342 |
|
|
<ul> |
343 |
|
|
<li>This web page uses trial division combined with the |
344 |
|
|
<a href="http://mathworld.wolfram.com/EratosthenesSieve.html">Sieve of Eratosthenes</a> |
345 |
|
|
with a sieve of 2,310 = 2 * 3 * 5 * 7 * 11 elements. The |
346 |
|
|
sieve is automatically generated, automatically compacted into a |
347 |
|
|
difference table containing 480 elements, and packaged as a C-language source |
348 |
|
|
file containing a 480-element lookup table of |
349 |
|
|
integers. The algorithm checks divisibility by increasing trial divisors, |
350 |
|
|
but it does so with all multiples of 2, 3, 5, 7, and 11 omitted (this is the |
351 |
|
|
role of the Sieve of Eratosthenes).</li> |
352 |
|
|
<li>Although this web page does factor effectively, |
353 |
|
|
it is strictly "parlor amusement" grade, and will answer questions |
354 |
|
|
such as <i>Is the year I was born a prime number?</i> or <i>Is my street address |
355 |
|
|
prime?</i>, but is inadequate for serious factoring. Because this CGI-BIN |
356 |
|
|
application runs on a shared server, it protects itself by only allowing |
357 |
|
|
<?php echo " " . $cgi_max . " "; ?>seconds to elapse while factoring. The busier |
358 |
|
|
the server is, the less actual CPU time is represented by |
359 |
|
|
<?php echo " " . $cgi_max . " "; ?>seconds of elapsed time. This means that |
360 |
|
|
factoring operations may be less successful when the server is busy.</li> |
361 |
|
|
<li>This utility uses the <a href="http://www.swox.com/gmp">GMP library</a> |
362 |
|
|
for arithmetic. The limit of 18-digit integers is in place so that |
363 |
|
|
machine-native integers can be used for the trial divisor (it is more |
364 |
|
|
efficient that way, and the GMP provides special function calls |
365 |
|
|
for small divisors). Since the trial divisor need only attain |
366 |
|
|
the square root of the number to be factored, any trial divisor for |
367 |
|
|
an 18-digit integer will fit in one machine-native integer.</li> |
368 |
|
|
</ul> |
369 |
|
|
<?php |
370 |
|
|
} |
371 |
|
|
|
372 |
|
|
function pfact18_print_tabular_results(&$style, |
373 |
|
|
$cgi_result, |
374 |
|
|
$cgi_result_nelem, |
375 |
|
|
$mr_nrounds, |
376 |
|
|
$mr_pcntprime, |
377 |
|
|
$mr_recip, |
378 |
|
|
$cgi_max) |
379 |
|
|
{ |
380 |
|
|
//Add commas to the number to factor, the number of Miller-Rabin rounds, and |
381 |
|
|
//the timeout. |
382 |
|
|
pfact18_commanate($cgi_result[1]); |
383 |
|
|
pfact18_commanate($cgi_result[2]); |
384 |
|
|
pfact18_commanate($cgi_result[3]); |
385 |
|
|
|
386 |
|
|
//Add commas to each prime factor and its multiplicity. |
387 |
|
|
$nfactors = ($cgi_result_nelem - 6)/3; |
388 |
|
|
|
389 |
|
|
for ($i=0; $i<$nfactors; $i++) |
390 |
|
|
{ |
391 |
|
|
pfact18_commanate($cgi_result[$i * 3 + 5]); |
392 |
|
|
pfact18_commanate($cgi_result[$i * 3 + 6]); |
393 |
|
|
} |
394 |
|
|
|
395 |
|
|
//echo "<br>" . $cgi_result_nelem . "<br>"; |
396 |
|
|
|
397 |
|
|
//Announce the overall result. |
398 |
|
|
$print_table = 0; |
399 |
|
|
echo "<p align=\"center\"><font size=\"4\">"; |
400 |
|
|
if (($cgi_result[$cgi_result_nelem - 5] == "P") && ($cgi_result_nelem == 9) && ($cgi_result[$cgi_result_nelem - 3] == "1")) |
401 |
|
|
{ |
402 |
|
|
echo "The integer " . $cgi_result[1] . " is prime (with 100% certainty)."; |
403 |
|
|
} |
404 |
|
|
elseif (($cgi_result[$cgi_result_nelem - 5] == "p") && ($cgi_result_nelem == 9)) |
405 |
|
|
{ |
406 |
|
|
echo "Based on " . $mr_nrounds . " applications of the Miller-Rabin test, the integer "; |
407 |
|
|
echo $cgi_result[1] . " is probably (with " . $mr_pcntprime . "% probability) "; |
408 |
|
|
echo "prime. (This means that there is no more than 1 chance "; |
409 |
|
|
echo "in " . $mr_recip . " that this integer is composite.)"; |
410 |
|
|
} |
411 |
|
|
elseif (($cgi_result[$cgi_result_nelem - 5] == "C") && ($cgi_result_nelem == 9)) |
412 |
|
|
{ |
413 |
|
|
echo "The integer " . $cgi_result[1] . " has been verified by the Miller-Rabin test "; |
414 |
|
|
echo "to be composite. However, "; |
415 |
|
|
echo "due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), "; |
416 |
|
|
echo "it was not possible to make any progress in factoring "; |
417 |
|
|
echo "this integer. Please try again when the server is less active "; |
418 |
|
|
echo "or try another factoring resource."; |
419 |
|
|
} |
420 |
|
|
elseif ($cgi_result[$cgi_result_nelem - 5] == "P") |
421 |
|
|
{ |
422 |
|
|
echo "The composite integer " ; |
423 |
|
|
echo $cgi_result[1] . " was successfully factored into its prime components with "; |
424 |
|
|
echo "100% certainty. Its prime factors and their multiplicities are listed "; |
425 |
|
|
echo "in the table below."; |
426 |
|
|
$print_table = 1; |
427 |
|
|
} |
428 |
|
|
elseif ($cgi_result[$cgi_result_nelem - 5] == "p") |
429 |
|
|
{ |
430 |
|
|
echo "The composite integer " ; |
431 |
|
|
echo $cgi_result[1] . " was successfully factored into its prime components, "; |
432 |
|
|
echo "and these prime components and their multiplicities are listed in the "; |
433 |
|
|
echo "table below. "; |
434 |
|
|
echo "The last component listed in the table was judged to be prime based on "; |
435 |
|
|
echo $mr_nrounds . " applications of the Miller-Rabin test, meaning that it is "; |
436 |
|
|
echo $mr_pcntprime . "% probable "; |
437 |
|
|
echo "that this last component is prime (i.e. that there is no more than 1 chance "; |
438 |
|
|
echo "in " . $mr_recip . " that it is composite)."; |
439 |
|
|
$print_table = 1; |
440 |
|
|
} |
441 |
|
|
elseif ($cgi_result[$cgi_result_nelem - 5] == "C") |
442 |
|
|
{ |
443 |
|
|
echo "Due to server CPU time restrictions (" . $cgi_max . " seconds of elapsed time), "; |
444 |
|
|
echo "the integer "; |
445 |
|
|
echo $cgi_result[1] . " could only be partially factored. In the results below, note that "; |
446 |
|
|
echo "the last component "; |
447 |
|
|
echo "listed bears the category code <i>C</i> (for <u>c</u>omposite). Please "; |
448 |
|
|
echo " try again when the server is less active "; |
449 |
|
|
echo "or try another factoring resource."; |
450 |
|
|
$print_table = 1; |
451 |
|
|
} |
452 |
|
|
echo "</p></font>"; |
453 |
|
|
|
454 |
|
|
//Print the table if demanded. |
455 |
|
|
if ($print_table) |
456 |
|
|
{ |
457 |
|
|
$style->hrule_std(); |
458 |
|
|
|
459 |
|
|
//Assign the table column widths. They are centralized here for easy change. |
460 |
|
|
$width[0] = 10; |
461 |
|
|
$width[1] = 10; |
462 |
|
|
$width[2] = 10; |
463 |
|
|
$width[3] = 10; |
464 |
|
|
|
465 |
|
|
echo "<p><table align=\"center\" border=\"1\" width=\"90%\">\n"; |
466 |
|
|
|
467 |
|
|
for ($i=0; $i <= ($cgi_result_nelem/3 - 2); $i++) |
468 |
|
|
{ |
469 |
|
|
//Factor number. |
470 |
|
|
echo "<tr>\n"; |
471 |
|
|
|
472 |
|
|
echo " <td width=\"" . $width[0] . "%\">\n"; |
473 |
|
|
if ($i==0) |
474 |
|
|
{ |
475 |
|
|
echo " <p align=\"center\"><b>Factor<br>Number</b></p>\n"; |
476 |
|
|
} |
477 |
|
|
else |
478 |
|
|
{ |
479 |
|
|
echo " <p align=\"center\">" . $i . "</p>\n"; |
480 |
|
|
} |
481 |
|
|
echo " </td>\n"; |
482 |
|
|
|
483 |
|
|
//Prime Factor |
484 |
|
|
echo " <td width=\"" . $width[1] . "%\">\n"; |
485 |
|
|
if ($i==0) |
486 |
|
|
{ |
487 |
|
|
echo " <p align=\"center\"><b>Component<br>Factor</b></p>\n"; |
488 |
|
|
} |
489 |
|
|
else |
490 |
|
|
{ |
491 |
|
|
echo " <p align=\"center\">" . $cgi_result[$i * 3 + 2] . "</p>\n"; |
492 |
|
|
} |
493 |
|
|
echo " </td>\n"; |
494 |
|
|
|
495 |
|
|
//Multiplicity. |
496 |
|
|
echo " <td width=\"" . $width[2] . "%\">\n"; |
497 |
|
|
if ($i==0) |
498 |
|
|
{ |
499 |
|
|
echo " <p align=\"center\"><b>Multiplicity</b></p>\n"; |
500 |
|
|
} |
501 |
|
|
else |
502 |
|
|
{ |
503 |
|
|
echo " <p align=\"center\">" . $cgi_result[$i * 3 + 3] . "</p>\n"; |
504 |
|
|
} |
505 |
|
|
echo " </td>\n"; |
506 |
|
|
|
507 |
|
|
//Category code. |
508 |
|
|
echo " <td width=\"" . $width[3] . "%\">\n"; |
509 |
|
|
if ($i==0) |
510 |
|
|
{ |
511 |
|
|
echo " <p align=\"center\"><b>Category<br>Code</b></p>\n"; |
512 |
|
|
} |
513 |
|
|
else |
514 |
|
|
{ |
515 |
|
|
echo " <p align=\"center\">" . $cgi_result[$i * 3 + 1] . "</p>\n"; |
516 |
|
|
} |
517 |
|
|
echo " </td>\n"; |
518 |
|
|
|
519 |
|
|
|
520 |
|
|
echo "</tr>\n"; |
521 |
|
|
} |
522 |
|
|
|
523 |
|
|
echo "</table></p>\n"; |
524 |
|
|
echo "<p align=\"center\"><b>Table legend:</b> <b>P</b>=prime with absolute certainty, "; |
525 |
|
|
echo "<b>p</b>=prime established by Miller-Rabin test with "; |
526 |
|
|
echo $mr_pcntprime . "% certainty, and <b>C</b>=composite established by Miller-Rabin test "; |
527 |
|
|
echo "with absolute certainty, but not factorable in the time allowed.</p>\n"; |
528 |
|
|
|
529 |
|
|
$style->hrule_std(); |
530 |
|
|
pfact18_algorithm_notes($cgi_max); |
531 |
|
|
} |
532 |
|
|
} |
533 |
|
|
// |
534 |
|
|
//Main script begins here. |
535 |
|
|
// |
536 |
|
|
//Let's agree on a number of rounds for the Miller-Rabin test. This influences the |
537 |
|
|
//probabilities. |
538 |
|
|
$miller_rabin_nrounds = 25; |
539 |
|
|
// |
540 |
|
|
//Let's agree how long the CGI may take to factor. |
541 |
|
|
$max_cgi_time = 10; |
542 |
|
|
// |
543 |
|
|
//We need to establish the probability that a number which passes the rounds specified |
544 |
|
|
//above is still in fact composite. This values need to be calculated by hand whenever |
545 |
|
|
//the value above is changed. |
546 |
|
|
$miller_rabin_p_real = "0.99999999999999911182"; |
547 |
|
|
$miller_rabin_p_percent = "99.999999999999911182"; |
548 |
|
|
$miller_rabin_residual_real = "0.00000000000000088818"; |
549 |
|
|
$miller_rabin_residual_percent = "0.000000000000088818"; |
550 |
|
|
$miller_rabin_residual_lt_reciprocal = "1,125,899,906,842,624"; |
551 |
|
|
// |
552 |
|
|
$style = new Stdnwpstyle; |
553 |
|
|
//Assign the current style in force. Also, starts the CPU |
554 |
|
|
//usage clock. |
555 |
|
|
|
556 |
|
|
//Do the header unconditionally. The header is always used on this page. |
557 |
|
|
do_header($style); |
558 |
|
|
// |
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->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->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 = "./arith_large_cgi 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->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->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 |
|
|
?> |