Re: Infinite loop in mat_ideal_two_elt (2.0.20.beta)

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

[Peter Montgomery:]
>         My implementation of the square root stage of the number field sieve
>     factorization algorithm uses the PARI library.  For example, it
>     was used in the August, 1999 factorization of a 512-bit RSA challenge key.
> 
>         Last year an individual whom I'll call Mr. X reported an infinite
>     loop on one data set (but other data sets worked for him).
>     Mr. X sent his data to me -- I could not reproduce the problem.
>     Our configurations were:
[...]
>         I printed the ideals being passed to idealmul and recreated them
>     in GP (see below).  That was not enough to duplicate the problem.
>     I next tried ensuring the random number generator had the
>     corect value before calling idealmul, but that was not enough.
>     Finally I raised the precision to 120 decimal digits
>     (my program calls initalg(polynomial, 15) in 32-bit mode).
>     Now the problem occurs under GP too.
> ? \g4
>    debug = 4
> ? setrand(1);
> ? print("Calling idealmul");
> Calling idealmul
> ? print(idealmul(nf,ideala,idealb));
>  K2 (334) (330) (316) (303) (294) (286) (278) (271) (266) (260) (235) (218) (210) (200) (188) (182) (169) (157) (149) (146) (135) (129) (121) (115) (86) (81) (76) (68) (64) (56) (52) (46) (25) (19) (15) (7) K3 (66)
> Recomputing Gram-Schmidt, kmax = 3
>  (143) (139) (124) (121) (105) (101) (95) (78) (75) (71) (60) (56) (48) (45) (33) (30) (26) (17) (10) (5) (3) K4 (71) (65) (61) (59) (52) (47) (34) (29) (22) (15) (10) (3) (0) K5
>   ***   Warning: increasing prec in lllgramintern; new prec = 34
>   ***   Warning: lllgramintern starting over.

Here was the problem. At this point, the base change matrix corresponding to
the LLL reduction wasn't correctly updated due to a rather subtle bug in the
updating code (didn't track correctly the parameter kmax, which records the
maximal column index reached at this point; supposedly the first kmax-1
vectors form an LLL-reduced basis): in case where there were too many
errors due to precision loss in the early stages of the LLL reduction (the
initial vectors are not LLL-reduced as they should be), followed by a
precision increase, the recovery code led to something which could be very
far away from being reduced in any sense. In extreme cases, like your
example, the base change was not even invertible in GL(2,Z), and changed the
ideal ! The reduction to two-element form had then no chance of success...

Besides the obvious bug (much easier to correct than to spot in the first
place), this exhibits a major problem with floating point operations in PARI:
the number of words used to represent the typical real number decreases quite
fast when terms of equal magnitude are subtracted [which of course occurs
quite frequently in LLL] whereas the actual precision loss is usually much,
much, smaller. For instance, the precision doubling above simply adds many
(meaningless) zeroes at the end of all the original matrix entries, then
retraces the exact same steps: the reduction now suceeds...

At a lower precision (\p28) the initial reduction fails bluntly and the
second try (higher initial precision) has the behaviour

[...]
   ***   Warning: increasing prec in lllgramintern; new prec = 32
   ***   Warning: lllgramintern starting over.
 K2 K3 K4 K5 (52) (50) (43) (40) (36) (33) (21) (17) (15) (9) (7)

where here the initial stages were mostly correct (K1, ..., K5 means that
the first 4 columns were LLL-reduced); as opposed to your

>  K2 K3 (2) K4 (13) (10) (0) K5 (52) (50) (43) (40) (36) (33) (21) (17) (15) (9) (7)

where only the first two ones were reduced, hence some reduction had to
take place *and be taken into account* (which it fails to be since the
updating code incorrectly assumed nothing happened while scanning the first 4
columns).

Thanks for your efforts, and your very nice debugging report !

This (severe) bug is corrected in the CVS repository (patch 1.50 in
bibli1.c), and in 2.0.21 which I'll release shortly.

Cheers,

      Karim.
__
Karim Belabas                    email: Karim.Belabas@math.u-psud.fr
Dep. de Mathematiques, Bat. 425
Universite Paris-Sud             Tel: (00 33) 1 69 15 57 48
F-91405 Orsay (France)           Fax: (00 33) 1 69 15 60 19
--
PARI/GP Home Page: http://www.parigp-home.de/