Changes http://wiki.axiom-developer.org/329FuzzyErrorInFactor/diff
--
++added:
+ Summary:
+
+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:
+
+\begin{axiom}
+factor 119643463
+prime? 119643463
+factor 129864979
+prime? 129864979
+\end{axiom}
+
+<br>
+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.
+
+Please be aware that due to the randomness of the algorithms, the "live"
computation may result in outputs different from those observed by the original
authors.
+
+Thanks to Bill Page for fixing the display problems, which is apparently due
to use of LaTeX tags involving 'verbatim'. Using html tags involving 'pre'
without embedded blank lines also seem to work.
+
+
+\begin{axiom}
+)set output tex off
+)set output algebra on
+)set message autoload off
+\end{axiom}
+
+<hr>
+
+I type
+
+\begin{axiom}
+factor factorial 12399 -- or 12345 or ....
+\end{axiom}
+
+Sometimes I get a perhaps right result sometimes I get a wrong result.
+
+This time the last factor I get is $124028873 = 10399 \times 11927$.
+The other factors seem right.
+
+From wyscc Sun Dec 17 12:11:40 -0600 2006
+From: wyscc
+Date: Sun, 17 Dec 2006 12:11:40 -0600
+Subject: Windows version seems correct.
+Message-ID: <[EMAIL PROTECTED]>
+
+<br>
+The following is a (shortened) transcript:
+<pre>
+ AXIOM Computer Algebra System
+ Version of Tuesday November 30, 2004 at 21:11:14
+ -----------------------------------------------------------------------------
+ Issue )copyright to view copyright notices.
+ Issue )summary for a summary of useful system commands.
+ Issue )quit to leave AXIOM and return to shell.
+ -----------------------------------------------------------------------------
+ (2) -> factor factorial 12399
+ 12391 6196 3095 2065 1238 1031 773 687 563 441 411 344 309 294
+ 2 3 5 7 11 13 17 19 23 29 31 37 41 43
+ *
+ [...]
+ *
+ 12227 12239 12241 12251 12253 12263 12269 12277 12281 12289 12301 12323
+ *
+ 12329 12343 12347 12373 12377 12379 12391
+ Type: Factored Integer
+</pre>
+
+But in the Linux version (patch 50; September 2006), the last factor was
+$119970353 = 10253 \times 11701$ (and both primes were missing from the list,
which according to the Windows version has 1479 distinct prime factors).
+
+In the Linux version (Axiom 3.9, September 2005), the last factor was
$123643253 = 10243 \times 12071$.
+In the Linux version (Axiom 3.0 Beta, February 2005), there were TWO
incomplete factors: 119643463, 129864979 (both were not factorable using
'factor' in this version (that is at least consistent!) AND the Windows version
(this is inconsistent), whereas $119643463 = 10111 \times 11833$ and $129864979
= 11027 \times 11777$ (these primes were listed in the Windows version for
factor factorial 12399). More inconsistencies: prime? reports both of these as
'false' (correct answer). So it appears that the factorization program and the
primality check program are independent.
+
+\begin{axiom}
+factor 119643463
+prime? 119643463
+factor 129864979
+prime? 129864979
+\end{axiom}
+
+
+In the Linux version (October 25, 2004), the last factor was $117661597 =
10651 \times 11047$. This version displays many more messages about loading
domains.
+
+
+Linux versions were run on the same machine under same OS (Fedora 2). Windows
version (November 30, 2004)was run on a different machine.
+<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]
