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:
-There are display problems for this page, apparently independent of the format
type chosen. It seems to be due to some extra LF/CR inserted by the system.
Even manually eliminating some does not help. Please use Edit to view until
display problems are fixed.
-
-Details of original reports follow.
+<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.
+
+Previous display problems are minimized by removing blank lines and also using
html tags involving 'pre' instead of LaTeX tags involving 'verbatim'. The
output from 'factor factorial 12399' still is not fully displayed.
+
+(Edited) details of original reports follow.
??changed:
-The following is a transcript:
-
-\begin{verbatim}
+<br>
+The following is a transcript (shortened):
+
+<pre>
AXIOM Computer Algebra System
--removed:
-----------------------------------------------------------------------------
-
-(1) -> factor factorial 10
- Loading j:/OpenAxiom/axiom014/mnt/windows/algebra/COMBINAT.o for
- package IntegerCombinatoricFunctions
- Loading j:/OpenAxiom/axiom014/mnt/windows/algebra/UPMP.o for package
- UnivariatePolynomialMultiplicationPackage
- Loading j:/OpenAxiom/axiom014/mnt/windows/algebra/INTFACT.o for
- package IntegerFactorizationPackage
-
- 8 4 2
- (1) 2 3 5 7
- Type: Factored Integer
(2) -> factor factorial 12399
--removed:
(2) -> factor factorial 12399
- Loading j:/OpenAxiom/axiom014/mnt/windows/algebra/LMDICT.o for
- domain ListMultiDictionary
- Loading j:/OpenAxiom/axiom014/mnt/windows/algebra/DIOPS-.o for
- domain DictionaryOperations&
- Loading j:/OpenAxiom/axiom014/mnt/windows/algebra/BGAGG-.o for
- domain BagAggregate&
- Loading j:/OpenAxiom/axiom014/mnt/windows/algebra/IROOT.o for
- package IntegerRoots
-
(2)
??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
-[238 more lines...]
+ [...]
*
??changed:
Type: Factored Integer
-\end{verbatim}
+</pre>
+
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]
