Changes http://wiki.axiom-developer.org/329ErrorInIntegerFactor/diff
--
??changed:
-The title of this error report #329 was "Fuzzy error in factor". As first
reported by anonymous, factoring 12399! produces a composite number as a prime
factor. Subsequently, experimenting with different versions of Axiom exhibits
two "small" composite integers that the factor programs in several open source
versions tested are unable to factor and yet the programs prime? give correct
answers. These two numbers are:
+As first reported by anonymous, factoring 12399! produces a composite number
as a prime factor. Subsequently, experimenting with different versions of Axiom
exhibits some "small" composite integers that the factor programs in several
open source versions tested are unable to factor and yet the programs prime?
give correct answers. Two example numbers are:
??changed:
-Details of original reports follow.
+For the record, 119643463 = (10111)(11833) and 1129864979 = (11027)(11777).
+
+The algorithms for identifying a composite integer and its factors are
probabilistic. The algorithms implemented in Axiom are in the packages PRIMES
and INTFACT (see intfact.spad) where the possibility of failure (that is,
identifying a number as prime when it is composite) is acknowledged. In the
case of primality test, the probabilities of error are given. The program
'prime?' is guaranteed to be correct for integers less than 341550071728321
with an error probability less than 4^(-10) or approximately 1 in a million.
The program 'factor' does not include failure probabilities, but failure
frequency is apparently much higher and failure can happen for even much
smaller numbers.
+
+Thanks to Bill Page for fixing the display problems by adding the following
lines and indenting verbatim paragraphs.
+An alternative that also works is to use html tags involving 'pre' but with no
embedded blank lines.
+
+(Edited) details of original reports follow. Please note that due to the
randomness of the algorithm, the "live" computations may not show the same
behavior as the original writer observed.
??changed:
-The following is a transcript::
+The following is a (shortened) transcript::
??changed:
*
- 268 237 213 206 187 176 171 157 150 140 128 123 121 116
- 47 53 59 61 67 71 73 79 83 89 97 101 103 107
- *
- 114 109 97 94 90 89 83 82 78 76 74 71 69 68
- 109 113 127 131 137 139 149 151 157 163 167 173 179 181
- *
- 64 64 62 62 58 55 54 54 53 51 51 49 48 47
46
- 191 193 197 199 211 223 227 229 233 239 241 251 257 263 269
- *
- 45 44 44 43 42 40 39 39 39 37 36 35 35 35
34
- 271 277 281 283 293 307 311 313 317 331 337 347 349 353 359
- *
- 33 33 32 32 31 31 30 30 29 29 28 28 28 27
27
- 367 373 379 383 389 397 401 409 419 421 431 433 439 443 449
- *
- 27 26 26 26 25 25 25 24 24 24 23 23 22 22
22
- 457 461 463 467 479 487 491 499 503 509 521 523 541 547 557
- *
- 22 21 21 21 21 20 20 20 20 20 20 20 19 19
19
-[235 more lines...]
+ [...]
*
Linux versions were run on the same machine under same OS (Fedora 2). Windows
version (November 30, 2004)was run on a different machine.
++added:
+<br>
+<hr>On 17 Dec 2006 23:04:44 +0100
+ Francois Maltey <[EMAIL PROTECTED]> wrote:
+>I use my own compiled axiom without change for integer
+>and so.
+>I have a random reponse :
+>
+>petoncle:~/Axiom$ axiom -noht
+> AXIOM Computer Algebra System
+> Version: Axiom (September 2006)
+> Timestamp: Saturday October 28, 2006 at 12:18:07
+>-----------------------------------------------------------------------
+>
+>I test :
+>
+>[#factors (117661597+0*i) for i in 1..1000] -- there
+>are 1 and 2 factors
+>reduce (+, [#factors (117661597+0*i) for i in 1..1000])
+> -- around 1650
+>
+>The exact solution is 2000 of course.
+
+<hr>On 17 Dec 2006 19:04:44 -0500
+William Sit <[EMAIL PROTECTED]> wrote:
+
+I confirmed that Francois' example does give random results in the 1660 area.
This suggests that the integer factoring algorithm used involves random number
generators and that the program in this case only has a probability of 0.83
success rate in identifying a composite number. The case for 119643463 is worse:
+
+\begin{axiom}
+reduce (+, [#factors (119643463+0*i) for i in 1..1000])
+reduce (+, [#factors (119643463+0*i) for i in 1..1000])
+\end{axiom}
+
+and only slightly better for 129864979. This is unacceptable. However, the
documentation in both the implementation of factor and prime? (see
intfact.spad, see PRIMES and INTFACT packages) already acknowledged these
possibilities.
+
+
+
+
+
+
+
--
forwarded from http://wiki.axiom-developer.org/[EMAIL PROTECTED]
