Karim BELABAS on Mon, 10 Jun 2002 23:26:56 +0200 (MEST)

 pari-2.2.3.alpha released

```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)

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.
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

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
--