Karim BELABAS on Thu, 14 Sep 2000 11:03:58 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
Re: Infinite loop in mat_ideal_two_elt (2.0.20.beta) |
[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/