Re: adding Proof option to factor()

["Karim Belabas" <Karim.Belabas@math.u-bordeaux1.fr>]

* John Cremona [2007-09-07 11:18]:
> The factor() function for integers (i.e. factorint()) does not provide
> factors which are proved to be prime, unless they are are < 10^15,
> accoriding to the manual.  The manual recommends using isprime() in
> circumstances where proven primes are required.
> 
> Could we add another flag to the function which defaults to 0 but if
> set does the proving step too?  I use pari's factor() in mwrank and am
> not happy that I cannot guarantee results because of this, and it
> would be a lot easier to just add af lag to the call I make to
> factor().

I don't like complicating the user interface for something which is easy to
implement externally, usually in a more flexible way. There's already an
optional argument to factor, and having two flags is very error-prone
[ consider factor(n,1), factor(n,,1), factor(n,100000,1),
factor(n,1,10000), etc. ]

In interactive use, under GP, we have isprime( F[,1] )

In library mode, what's wrong with a trivial wrapper like

  // assumes x a t_INT
  GEN
  factorproven(GEN x)
  {
    GEN F = factorint(x, 0);
    long i, l;
    if (lg(F) == 1) return F; // x = 1
    F = gel(F,1); l = lg(F);
    for (i = 1; i < l; i++)
    {
      GEN p = gel(F,i);
      if (signe(p) > 0 && !isprime(p))
        pari_err(talker, "factor: Found composite pseudoprime %Z", p);
    }
    return F;
  }

??  [ Untested ! Can be simplified if one assumes further that x > 1. ]

This way you get a chance to handle errors the way you want (e.g. using
mwrank's own exception handling), print diagnostics, time subroutines, etc.

So I guess the answer is no. It would be quite a different story if the
functionnality was hard to implement, e.g. a flag to say : try to factor
for xxx seconds then stop. ( But then again a general mechanism to set
an alarm and abort a command after some fixed amout of time would be
preferable. )

Cheers,

    K.B.
-- 
Karim Belabas                  Tel: (+33) (0)5 40 00 26 17
Universite Bordeaux 1          Fax: (+33) (0)5 40 00 69 50
351, cours de la Liberation    http://www.math.u-bordeaux.fr/~belabas/
F-33405 Talence (France)       http://pari.math.u-bordeaux.fr/  [PARI/GP]