On 01/07/2010 04:34 PM, Martin Rubey wrote:
Do we really want to declare all integers less than 2 non-prime? Eg.,
prime?(-5) gives false.
I'd say, the following line in the "add" part of the category
IntegerNumberSystem is a bug.
prime? x == prime?(x)$IntegerPrimesPackage(%)
Why?
Just compare the documentation...
In IntegerPrimesPackage we have:
prime?: I -> Boolean
++ \spad{prime?(n)} returns true if n is prime and false if not.
++ The algorithm used is Rabin's probabilistic primality test
++ (reference: Knuth Volume 2 Semi Numerical Algorithms).
++ If \spad{prime? n} returns false, n is proven composite.
++ If \spad{prime? n} returns true, prime? may be in error
++ however, the probability of error is very low.
++ and is zero below 25*10^9 (due to a result of Pomerance et al),
++ below 10^12 and 10^13 due to results of Pinch,
++ and below 341550071728321 due to a result of Jaeschke.
++ Specifically, this implementation does at least 10 pseudo prime
++ tests and so the probability of error is \spad{< 4^(-10)}.
++ The running time of this method is cubic in the length
++ of the input n, that is \spad{O( (log n)^3 )}, for n<10^20.
++ beyond that, the algorithm is quartic, \spad{O( (log n)^4 )}.
++ Two improvements due to Davenport have been incorporated
++ which catches some trivial strong pseudo-primes, such as
++ [Jaeschke, 1991] 1377161253229053 * 413148375987157, which
++ the original algorithm regards as prime
whereas the exported function of Integer should match what is given by
UniqueFactorizationDomain, i.e.:
prime?: % -> Boolean
++ prime?(x) tests if x can never be written as the product
++ of two non-units of the ring,
++ i.e., x is an irreducible element.
So better file a bug report.
Ralf
--
You received this message because you are subscribed to the Google Groups
"FriCAS - computer algebra system" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/fricas-devel?hl=en.
