better isprime cross-over test

[Bill Allombert <allomber@math.u-bordeaux.fr>]

Hello PARI-dev,

isprime include a mechanism to choose between the p-1 test and APRCL
test. However it does not take into account the fact that the p-1 test 
only need p-1 to be factored up to sqrt(p-1).

This patch changes this, which should make the p-1 test used far more
often.

One example where it make a difference: isprime(2^127-1) 

Cheers,
Bill.

Index: pari/src/basemath/arith1.c
===================================================================
--- pari.orig/src/basemath/arith1.c	2005-08-30 16:18:31.000000000 +0200
+++ pari/src/basemath/arith1.c	2005-09-02 11:25:26.000000000 +0200
@@ -1973,12 +1973,14 @@
 {
   pari_sp av = avma;
   long l, res;
-  GEN F, p;
+  GEN F, p, e;
 
   if (BSW_isprime_small(x)) return 1;
-  F = (GEN)auxdecomp(subis(x,1), 0)[1];
-  l = lg(F); p = gel(F,l-1);
-  if (BSW_psp(p))
+  F = auxdecomp(subis(x,1), 0);
+  l = lg(gel(F,1))-1; p = gcoeff(F,l,1); e = gcoeff(F,l,2); F=gel(F,1);
+  if (cmpii(powgi(p, shifti(e,1)), x)<0)
+    res = isprimeSelfridge(mkvec2(x,vecslice(F,1,l-1))); /* half-smooth */
+  else if (BSW_psp(p))
     res = isprimeSelfridge(mkvec2(x,F)); /* smooth */
   else
     res = isprimeAPRCL(x);