pari-2.2.3.alpha released

[Karim BELABAS <Karim.Belabas@math.u-psud.fr>]

Hi pari-dev,

  as promised, here's a snapshot of current sources, called pari-2.2.3.alpha

  ftp://megrez.math.u-bordeaux.fr/pub/pari/pari-alpha.tgz

(CVS tag release-2-2-3). It is an ALPHA release, but nearing beta status.
It contains

* a number of major new features (BPSW primality test, APRCL primality
prover, PSLQ integer relation finder, stable floating point LLL, van Hoeij
factorizer over number fields).

WARNING: isprime(n) guarantees primality ==> SLOW when n is huge. Use
ispseudoprime(n) for a quick (BPSW or strong-RM) test.

* large rewrite of basic number field stuff (LLL-reduced nf.zk, modular
algorithms, partial factorization). General speedup for generic
number field code (40% for `nfields' bench which features trivial examples,
much more for tough problems). Specifics:

  - nfsubfields orders of magnitude faster for tough Galois cases
    (interfaces Allombert's algorithm nfgaloisconj for WSS groups). Try
    {
      nfsubfields(x^32 - 448*x^30 + 84864*x^28 - 9028096*x^26 +
602397952*x^24 - 26625650688*x^22 + 801918722048*x^20 - 16665641517056*x^18 +
239210760462336*x^16 - 2349014746136576*x^14 + 15459151516270592*x^12 -
65892492886671360*x^10 + 172580952324702208*x^8 - 255690851718529024*x^6 +
183876928237731840*x^4 - 44660812492570624*x^2 + 2000989041197056);
    }
    \\ yes, it has _a lot_ of subfields, it's the compositum of the
    \\ Q(sqrt(p)) for p = 2, 3, 5, 7, 11

  - polredabs allows partial factorization (flag 16) and should be impervious
    to precision problems. Try :
    {
      P = x^20 - 20060746*x^19 - 26317708967*x^18 + 1272499722*x^17 -
68388085954*x^16 - 397162072594*x^15 - 588825188791*x^14 +
211790286098*x^13 + 1816277408059*x^12 + 3573979023900*x^11 +
4200711847680*x^10 + 3951202410004*x^9 + 3362073609371*x^8 +
2415036105634*x^7 + 1338063714403*x^6 + 454352699370*x^5 + 86337091498*x^4
- 1546262554*x^3 + 27330619*x^2 + 6622*x + 1;
      polredabs(P, 16); \\ use partial factorisation of poldisc(P)
    }
    Compare in the stable version:

      addprimes(factor(poldisc(P),0)[,1]) \\ same, slightly less legible...
      polredabs(P);

    at \p28, \p60, \p100, \p200 etc. (should be at least ten times slower,
    would enter a near infinite loop at \p28)

  - approximation theorem: primedec, idealtwoelt, idealappr orders of
    magnitude faster for tough fields (large degree, small primes totally split)
    Try:  idealprimedec(nfinit(galoissubcyclo(341,2)), 2)

  - faster bnrstark and quadray
    Try:  allocatemem(80*10^6); quadray(5, 11*y^3 + 17*y^2 + 8*y + 19)
    \\ it's _tough_ (class field of relative degree 69), allow for about
    \\ 4min on a PIII 1GHz, scale accordingly.

  - very fast polsubcyclo/galoissubcyclo (defining pol. for abelian fields)
    and ffinit (same for prime finite fields)

* a large number of (mostly minor) bug fixes

Plus a few other things I might have forgotten.

Have fun,

    Karim.

P.S: The complete CHANGES:

Done for version 2.2.3 (released 10/06/2002):
  Fixed
    1- bnrinit(bnfinit(subst(polsubcyclo(89,8),x,-x)),4) --> SEGV [make sure
    isprincipalfact is used in makecygen, even in case of precision problems]
    2- bnrisprincipal --> warning + "not an element in ..." [missing nf_FORCE]
    3- oo loop in isprincipalfact when increasing bnf precision
    4- stack corruption in ellap (LARGE p)
    5- zeta(s) destroyed the Bernoulli cache when using the functional equation
    6- oo loop in random_relation (called from bnfinit)
    7- fixed lower bound for p in nfsubfields (could get oo loop: pol never
       squarefree mod p)
    8- [Vecsmall([1, 2])][1][2][1] --> SEGV
    9- typo in t_FRAC + t_PADIC  [only numerator of t_FRAC used]
   10- factorback(t,nfinit(x)) --> SEGV
IZ 11- shift(x > 0,, flag!=0) didn't act as the docs said [flag now ignored]
   12- lindep(Vec(x^48)) --> oo loop
   13- could get NaN in max_modulus (polroots) --> havoc later
   14- missing normalizepol() in centermod(t_POL,)
   15- [Follow-up to 2.2.2-F10] even more recent pdftex failed again
   16- not enough GC when printing a huge t_PADIC
   17- factorpadic(x*(x+1),3,10) would corrupt polx --> SEGV later
   18- delayed carry treated improperly in red_montgomery
   19- F() = 0; local(x)  ==> confusing error message
IZ 20- OS/2: make bench didn't work [env wouldn't start shell scripts]
BA 21- sqrtn(Mod(1,7),2,&z)-->z=1 should be -1
HC 22- Standard transcendental functions exp, sin, cos, ^, *, are now orders of
       magnitude faster for t_POL arguments of small degree.
HC 23- fixed a severe bug in p-adic/integer addition (1+3^4+O(3^10)) + 3
       didn't work.
HC 24- Corrected p-adic initell.
   25- ellj / eta (t_SER) truncated result to seriesprecision
   26- possible overflow in u_FpM_gauss (from ZM_inv)
   27- various problems with C++ compilers
   28- polredabs could fail to reduce "obvious" input, e.g x^2 + n*x + n^2
   29- gcd(x,y,1) didn't check its arguments
   30- typo in elltors: could forget a point of order 2
   31- gdivgs(t_RFRAC,x) incorrect (if numerator had denominator)
   32- serreverse(O(x) or x + O(x^2)) --> SEGV
   33- dbltor(0) returned 2^-308, instead of 10^-308
   34- precision problems in thue/thueinit
       setrand(5);tnf=thueinit(x^3 + x^2 - 43690*x - 3529208) --> error in mplog
   35- typo in bnfnarrow ("impossible inverse")
   36- subst(x,x^0,x) --> floating point exception
ISo37- many typos in the documentation
   38- [DOS/Windows]: incorrect conversion between 'double' and t_REAL
   39- polrootspadic(4*x^2-1,2,2) --> impossible inverse: Mod(2, 16).
       [specific to 2, and non-monic equations]
   40- discrepancy between bnfsunit output and docs [ bnfS[5][2] was t_MAT ]
   41- matdet: pivoting strategy incorrectly chosen ("incorrect type in gexpo")
   42- polcompositum output ordering depended on random seed
   43- plotrecthraw(0,[0]) --> SEGV
   44- plothraw([],[]) --> SEGV
IZ 45- ix86 inline assembler compilation problem [divll]
XR 46- forgotten case in Round4 [ nfdisc(x^12-10*x^11-57*x^10+740*x^9+353*x^8-16130*x^7+17749*x^6+100120*x^5-108466*x^4-292200*x^3+128380*x^2+380800*x+133112)
--> impossible inverse: Mod(2, ...) ]
   47- sin(1e-100) ---> 9.999999999999999999735998397 E-101 [ precision loss ]
   48- idealpow(nf,x, n < 0, 1) did not reduce the result
   49- gcd(0, -1) --> -1, content([0, Pi]) --> 3.14, content([0,Pi,Pi]) --> 1
BA 50- compilation problem on OSF (RTLD_GLOBAL undefined)
BA 51- [X-Windows] hi-res plot: window not redrawn properly (BackingStore pb)
   52- problems with tex2mail output (wrong alignment, wrong colors)
   53- contfrac(sin(Pi/4),,2) --> impossible assignment
   54- infinite recursion in gaffect(t_POL, scalar)
   55- content([-1]) was -1 [ should be 1 ]
   56- stack corruption in u_FpV_polint (used by modular bivariate resultant)
   57- polroots() used too high a precision when checking errors a posteriori
       (--> slow)
   58- contfrac(1/x) --> SEGV
   59- typo in sinh(0) --> wrong zero exponent
   60- exp(O(x^-1)) = O(x^(-1))  [ouch...]
   61- dilog(O(x^10)) = O(1)
   62- cosh(O(1)) --> division by 0
   63- sqrt(4*x^2) --> not an integer exponent for non invertible series in gpow
   64- besselj(0,O(1)) [or besseli] --> precision<=0 in gprec.
   65- O(1)' --> O(x^-1)
   66- gcd(O(2^1), O(2^10)) --> O(2^10)
   67- polrootspadic(x^2+8*x+4,2,2) -->  "impossible assignment"  [ [] in
       stable version, which is also wrong: 2 + O(2^2) ]
   68- one could write() an object to a binary file, corrupting it
MW 69- ellap(ellinit([0,0,1,-7077,235516]), 1075060289) --> "zero argument in
       an arithmetic function"
MW 70- ellap(ellinit([0,0,1,-7077,235516]),1135392007) --> SEGV
BA 71- user's manual index truncated if LANG=fr_FR
   72- lex(string1, string2) could return something not in {-1,0,1}
   73- bnfisprincipal(bnf,x, 0) was not instantaneous when bnf.no = 1
   74- no GC in poleval
   75- make clean did not remove libpari-2.2.*

  Changed
BA  1- improved Fp_isom
IZ  2- remove all dependance on __OPTIMIZE__ for inlining [cf 2.0.14 F-24]
    3- implementation of psi()  [very slow + wrong results at low accuracy]
    4- cleaned up forvec() [no more global variables]
    5- improvements in bnrstark (precompute common data)
BA  6- improved ffinit()
    7- rewrote time-critical parts of bnrstark
    8- all 'input filter' code removed from GP. es.c:filtre() now handles the
       full filtering [and has become reentrant]
    9- isprime() now guarantees primality
BA 10- improved polsubcyclo()
BA 11- new interface for galoissubcyclo
HC 12- gamma function for integral/rational arguments
   13- faster factornf / nfgcd
   14- removed readline-specific code from gp.c
   15- allow bnrstark over Q
   16- 'subgroup' argument made optional in bnrL1, bnrstark, rnfkummer
   17- use relative van Hoeij algorithm in nffactor [can handle huge number
       of modular factors]
   18- rewrote factorff() to use new modular functions
   19- rewrote primedec() to use new modular functions
   20- rewrote most *modpr functions
   21- modified diagnostics for integral LLL to match floating point version
   22- INCOMPATIBILITY: polgalois(); changed 3rd component of result so that
       it gives the numbering among all transitive subgroups of S_n [ was ad
       hoc up to 7, then as described above for n >= 8 ]
   23- INCOMPATIBILITY: nf.zk is now T2-LLL-reduced
   24- idealtwoelt was very slow when a small prime with many divisors
       divided the index (use approximation theorem)
   25- content(scalar) = abs(scalar) [when it makes sense]
   26- changed the interface to ispseudoprime and isprime
   27- [internal] element_muli: check input is consistent
   28- rewrote all LLL algorithms (use Householder, not Gram-Schmidt; do not
       use Gram matrix; unified code).
   29- INCOMPATIBILITY: the internal components of nf[5] have changed (MC and
       T2 not needed anymore)
   30- INCOMPATIBILITY: [library] polred & polredabs do not take a 'prec'
       argument anymore
   31- unified nfinit, polred* [use dedicated structs internally]
   32- rnfconductor(..., 1) doesn't need GRH anymore
   33- extracted FpXQ_gener from idealstar
   34- allow more types in gdivround
   35- improved root_bound (first step in factor() over Z[X]) for huge pols.
   36- faster bernfrac / bernvec
   37- INCOMPATIBILITY: removed gentimer() / genmsgtimer(). Use TIMER/msgTIMER
   38- let nfsubfields call galoissubfields (much faster when field is Galois)
   39- Configure (locatelib): don't look for lib*.so.x [ pb on Linux with
       [readline | ncurses]-devel.rpm.

  Added
    1- mplog2() function --> faster mplog()
    2- gcd for Gaussian integers
HC  3- APRCL primality test
    4- (strong) Lucas primality test + Baillie-Pomerance-Selfridge-Wagstaff test
BA  5- Facilities for permutation groups (perm.c).
BA  6- New functions galoissubgroups, galoisubfields.
HC  7- Implemented all Bessel functions J, I, N, K, H1, H2, and Bessel functions
       for power series and polynomials.
HC  8- Implemented PSLQ [preliminary]
GTo 9- Implemented Cipolla's algorithm for sqrt(Mod(x, p))
   10- library functions FpM_ker, FpM_deplin, diviiround, centermodii
   11- library function gerepileall
   12- library functions corepartial, core2partial
   13- library functions affui, itou, stor, itor
   14- library function lllint_ip (in place)
   15- library functions Q_primitive_part, Q_primpart, Q_remove_denom, Q_denom
   16- allow polredabs to use a partial factorisation of disc(nf) [as polred,
       but inconsistent values for flag. Backward compatibility problem here...]
   17- routine ellminimalmodel()
IZ 18- systems/ directory (currently for OS/2 only)
IZ 19- [OS/2:] install() for OS/2 system  (using builtin dlopen)
IZ 20- gnuplot and X11 are now simultaneously supported
-- 
Karim Belabas                    Tel: (+33) (0)1 69 15 57 48
Dép. de Mathematiques, Bat. 425  Fax: (+33) (0)1 69 15 60 19
Université Paris-Sud             Email: Karim.Belabas@math.u-psud.fr
F-91405 Orsay (France)           http://www.math.u-psud.fr/~belabas
--
PARI/GP Home Page: http://www.parigp-home.de/