Re: proposal to bring ifactor into src/, was: Factoring large integers

2006/2/2, Robert Dodier <robert.dodier at gmail.com>:
> On 2/1/06, Raymond Toy <raymond.toy at ericsson.com> wrote:
>
> > That's not a bad idea.  Or just replace factor with ifactor?
>
> That is OK by me --- Andrej, do you want to work on that?
>
> The Maxima function "factor" does more than just factoring
> integers, so it is necessary to identify which Lisp function
> actually does the integer factoring. I don't know which one it is.

I can look into moving ifacor to src/. I wouldn't mind having
different functions for factoring polynomials and factoring integers.
Maple has them (factor(14) -> 14, ifactor(14) -> (2) (7)) and
Mathematica also has Factor and FactorInteger functions, but I don't
know what Factor does for integer arguments. Entering '? factor' into
maxima will also show that ifactor exists so users can find it.

> I am aware that the Miller-Rabin test is a probabilistic test
> so there is a nonzero chance that a number reported to be
> prime might not be. However, if I'm not mistaken the
> probability of a spurious answer is much lower than that
> of a bug in the existing factor code, so I am willing to live
> with it. Of course, we should advertise the methods used
> in the help text for factor.

Both isprime in Maple and PrimeQ in Mathematica are probabilistic tests.

The probability that n passes one Miller-Rabin test and is not prime
is 1/4. We run 25 tests. If n passes all 25 tests, we run one Lucas
test. So chance that n passes all tests and is not prime is much
smaller that (1/4)^25.

HTH,
Andrej