Re: [PARI] MPQS error message: complement

[Gerhard Niklasch <nikl@mathematik.tu-muenchen.de>]

In response to Philippe Elbaz-Vincent's observations about
MPQS's file descriptor leaks in version 2.0.11:

> Is it possible to avoid simply this problem ?  

Option 1:  point your favourite browser at

	<url:http://pari.home.ml.org/relv/2.0.11.beta/>

(or, if the Monolith WWW redirector isn't working, directly at
<url:http://hasse.mathematik.tu-muenchen.de/ntsw/pari/relv/2.0.11.beta/>),
scroll down to near the end of the page, and fetch and apply the
`MPQS file descriptor leak' patch from 3 August.

Option 2:  this will be fixed anyway (somewhat differently) in version
2.0.12, which I expect will be out soon.

Version 2.0.11 had a bug which meant that almost every invocation of
the MPQS factoring engine failed to close one of the files it had
opened.  On most operating systems, the effect will be that the gp
process runs out of usable file descriptors after a while  (the
maximum available number of f.d.s per process is usually about 64
or 256, depending on operating system and default limit/ulimit
settings;  try `ulimit -a' if you are using a Bourne-like shell or
ksh, or `limit' if you are using csh/tcsh, to find out your settings).


Some background information may be useful at this point, since most
of the documentation of what the LiDIA/PARI MPQS implementation does
can only be found in commentary in the src/modules/mpqs.c file itself
at present.


MPQS, after initializing a number of things, spends most of its
time accumulating relations of the form

	Y^2 congruent X  (mod kN)

where N is the number to be factored, k is a (small) multiplier chosen
so as to get a good distribution of quadratic residues, fixed once and
for all  (depending on N)  for every MPQS run, Y is an integer of ap-
proximate size sqrt(kN), and X is an integer which is either completely
factored over a precomputed `factor base' of small primes, or is the
product of a moderately large number  (a `large prime', although it
isn't always prime)  by a fully-factored-over-the-FB number.  In the
first case, we speak of a `Full Relation', in the second, of a `Large
Prime Relation.'

Two LP Relations containing the same `large prime' can be combined to
produce a Full Relation.  The Full Relations will at the end be used
to compute congruences of the form

	Y^2 congruent X^2 (mod kN)

(spanning the so-called kernel [of a linear map over GF(2)]),  and any
such congruence for which X+Y and X-Y aren't both divisible by N will
produce a non-trivial factor of N.

When N is large, many thousand Full Relations and several ten thousand
LP Relations must be produced before we can hope to have a nontrivial
kernel, so we need to save them on disk rather than holding them in
memory.  (For N as small as 25 or 30 digits, we still use files, but
with any luck these files will never really be written to disk -- the
factorization will be completed before any buffers are written out,
provided you're under a Unix-like OS.)

Up to six temporary files will be used side by side.  Under Unix-like
systems, they have names like

	/var/tmp/LPTMP.500.7267

where the directory is governed by environment variables and built-
in defaults, the first number is the numerical user id, and the second
number is the PID of the gp process  (this avoids clashes when several
users are running gp processes on the same machine).  Under DOS, the
names are simpler.  The first name component is one of

	FNEW: new Full Relations, being appended as they are found.
	FREL: sorted Full Relations with duplicates eliminated.

	LPNEW: new LP Relations, being appended as they are found.
	LPREL: sorted LP Relations with duplicates eliminated and
	    combinable relations combined.

	LPTMP: temporary files used whilst merging FNEW into FREL
	    or LPNEW into LPREL  (after sorting the new files in
	    place).

	COMB: groups of combinable LP Relations found whilst merging
	    LPNEW into LPREL;  they will be processed into Full
	    Relations for appending to FNEW shortly afterwards.

If you turn on a very high level of debugging diagnostics, say

gp > \g6

(or equivalently by calling the gp function

gp > default(debug,6)

), MPQS will flood you with a vast amount of progress information,
statistics, and news about files being opened, closed, renamed,
removed, etc.  (Level 7 is even more verbose, level 5 is probably
the largest widely useful level, but doesn't yet show file access
information.)

These files are plain ordinary readable text files, albeit with poten-
tially very long lines  (100 or 200 characters per line).  During a
lengthy MPQS factorization, you can inspect e.g. the FREL and LPREL
files, or monitor FNEW/LPNEW with tail -f .  (Note however that output
to these files is buffered and thus happens in bursts, and that merging
works by writing a new LPTMP file and renaming that to FREL or LPREL,
as the case may be.  Also, depending on your operating system, the tail -f
command may run into problems when FNEW and LPNEW are truncated to zero
length after each sorting/merging phase.)

Hope this answers a few questions,
Gerhard