| Peter-Lawrence . Montgomery on Wed, 26 Jul 2000 22:03:28 +0200 (MET DST) |
[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]
| Infinite loop in mat_ideal_two_elt (2.0.20.beta) |
/*
Subject: Infinite loop in hard case of mat_ideal_two_elt
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:
Mr. X Me
circa 2.0.14.beta 2.0.11.beta
Pentium II MIPS (Origin 2000)
Linux Irix
BITS_IN_LONG=32 BITS_IN_LONG=64
We had slightly different versions of the application program.
Remote debugging is hard. Mr. X and I didn't explore further
until I visited his site recently.
By now my site had some Pentium II's.
Both of us tried upgrading to 2.0.20.beta on x86 under Linux.
Although I was using the latest version of the square root
application code and he had an old version,
both of us experienced the loop.
After getting it to fail once, I was able to duplicate the problem
other configurations (all 2.0.20.beta, BITS_IN_LONG = 32, no readline):
X86, Linux, gcc compiler, fully optimized
X86, Linux, gcc compiler, -O -g
Ultrasparc, Solaris, gcc compiler, fully optimized
MIPS, Irix, cc -o32, debug
I used kill -FPE to get Linux and Solaris core dumps.
The Linux -O -g dumps included line numbers.
The active procedures beneath my code include:
idealmul base4.c:1128
idealmat_mul base4.c:1075
idealmulh base4.c:1040
ideal_two_elt base4.c:545
mat_ideal_two_elt base4.c:522
check_elt base4.c:399
resultantducos polarit2.c:2170 (another trace called ugcd
from base4.c:400)
nextSousResultant polarit2.c:2137
gdivexact polarit2.c:1756 (three other traces without
line numbers show gmul here)
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.
Peter Montgomery
pmontgom@cwi.nl
July, 2000
GP/PARI CALCULATOR Version 2.0.20 (beta)
i686 running linux (ix86 kernel) 32-bit version
(readline disabled, extended help available)
Copyright (C) 1989-1999 by
C. Batut, K. Belabas, D. Bernardi, H. Cohen and M. Olivier.
Type ? for help, \q to quit.
Type ?12 for how to get moral (and possibly technical) support.
realprecision = 28 significant digits
seriesprecision = 16 significant terms
format = g0.28
parisize = 4000000, primelimit = 500000
log = 1 (on)
--------------- Log file ---------------
? \p120
realprecision = 125 significant digits (120 digits displayed)
? c5=11936294370;f0=c5*X^5-6168233576541*X^4+6293294957460559*X^3+4375521307057465327*X^2-8897919288763135233364*X+4026848305778799186287589;f1=subst(f0,X,XM/c5)*c5^4;print(f1);gen1a=10432793266243773739480111080779667187769979140885328108261080878689095106976522733911552241;gen2a=(XM^2+193676325895837749*XM+23604104703722894380364125437628545740014730842226734841732693839946762843354071442242939856959252260)/c5;gen1b=34128204375950380576217544959126424803298996283817317466105944608;gen2b=(XM^3-68787153471*XM^2+775223998789456075860*XM+517807548762347769649269944710702500137222085436268735652653158537030037069993021700)/c5^2;
XM^5 - 6168233576541*XM^4 + 75118621169485859888752830*XM^3 + 623402937669192832701819495537397386300*XM^2 - 15132024096864622113675992300017027277853208697892000*XM + 81741641097940981784868141251267769766343576918410578720070290000
? print("gen1a and gen1b factorizations");
gen1a and gen1b factorizations
? print(factor(gen1a,0));
[8779, 1; 8831, 1; 8837, 1; 8849, 1; 8867, 4; 8941, 1; 9007, 1; 9011, 1; 9029, 1; 9109, 1; 9127, 1; 9133, 1; 9161, 4; 9239, 1; 9371, 1; 9463, 1; 9697, 1]
? print(factor(gen2a,0));
*** partial factorization is not meaningful here.
? addprimes(38290736339);
? addprimes(24915118806437);
? addprimes(2294193479450857);
? addprimes(12089840445049223);
? print("Table of added primes has:");
Table of added primes has:
? print(addprimes(2789526180465632379891999182608171472949868632948292802246126209485981002773839692198315259197));
[38290736339, 24915118806437, 2294193479450857, 12089840445049223, 2789526180465632379891999182608171472949868632948292802246126209485981002773839692198315259197]
? print("Factorization of discriminant of f1");
Factorization of discriminant of f1
? print(factor(poldisc(f1)),0);
[2, 12; 3, 26; 5, 15; 7, 12; 11, 12; 13, 12; 47, 12; 379, 1; 2819, 12; 4957, 1; 38290736339, 1; 24915118806437, 1; 2780005685283889, 1; 2789526180465632379891999182608171472949868632948292802246126209485981002773839692198315259197, 1]0
? nf=nfinit(f1,0);
? ideala=idealadd(nf,idealprincipal(nf,gen1a),idealprincipal(nf,gen2a));
? print("ideala=");print(ideala);
ideala=
[10432793266243773739480111080779667187769979140885328108261080878689095106976522733911552241, 6623641984368003890108645649099893264960420240944321632470299305693680734861238602365833525, 1977506918985518818129158240391866754875846015368229800261929518746173720860913339073669298, 8029341679473258762267756313998743030517119063055547436734846509805080927544097277554435778, 4678809458486733542117199766393190687707857839000768107440154214333777091499896327069373210; 0, 79576141, 48677501, 58605905, 75953247; 0, 0, 1, 0, 0; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1]
? idealb=idealadd(nf,idealprincipal(nf,gen1b),idealprincipal(nf,gen2b));
? print("idealb=");print(idealb);
idealb=
[34128204375950380576217544959126424803298996283817317466105944608, 17812391950559535511467325825772578364946426642140034468398643522, 15499504638297376731569058963252510248074287822381643200150993633, 19133876287291957369348664215587262749192070209160980470315074626, 6865606331470572602363442136757690994354744364378511944096761163; 0, 38, 20, 35, 11; 0, 0, 7, 1, 4; 0, 0, 0, 1, 0; 0, 0, 0, 0, 1]
? \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.
K2 K3 (2) K4 (13) (10) (0) K5 (52) (50) (43) (40) (36) (33) (21) (17) (15) (9) (7)
ideal_two_elt, hard case: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 (continues indefinitely)
? \q
Good bye!
*/
\\ ---------------------------- Program
\l
\p120
{
c5 = 11936294370;
f0 = c5*X^5 - 6168233576541*X^4 + 6293294957460559*X^3
+ 4375521307057465327*X^2 - 8897919288763135233364*X
+ 4026848305778799186287589;
\\ Problem does not occur if we make change of variable below
\\ XM = Y + 1233646715308;
f1 = subst(f0, X, XM/c5)*c5^4;
print(f1);
\\ (gen1a, gen2a) generate ideala. (gen1b, gen2b) generate ideal2.
gen1a = 10432793266243773739480111080779667187769979140885328108261080878689095106976522733911552241;
gen2a = (XM^2 + 193676325895837749*XM + 23604104703722894380364125437628545740014730842226734841732693839946762843354071442242939856959252260)/c5;
gen1b = 34128204375950380576217544959126424803298996283817317466105944608;
gen2b = (XM^3 - 68787153471*XM^2 + 775223998789456075860*XM
+ 517807548762347769649269944710702500137222085436268735652653158537030037069993021700)/c5^2;
}
print("gen1a and gen1b factorizations");
print(factor(gen1a, 0)); \\ Several primes near 9000
print(factor(gen2a, 0));
\\ Give some factors of discriminant
addprimes(38290736339);
addprimes(24915118806437);
addprimes(2294193479450857);
addprimes(12089840445049223);
print("Table of added primes has:");
print(addprimes(2789526180465632379891999182608171472949868632948292802246126209485981002773839692198315259197)); \\ Last entry not prime
print("Factorization of discriminant of f1");
print(factor(poldisc(f1)), 0); \\ Factor discriminant using added primes
nf = nfinit(f1, 0); \\ Initialize a number field
ideala = idealadd(nf, idealprincipal(nf, gen1a), idealprincipal(nf, gen2a));
print("ideala="); print(ideala);
idealb = idealadd(nf, idealprincipal(nf, gen1b), idealprincipal(nf, gen2b));
print("idealb="); print(idealb);
\g4 \\ To watch ++c counter at base4.c:514 (mat_ideal_two_elt)
setrand(1); \\ For mymyrand in mat_ideal_two_elt
print("Calling idealmul");
print(idealmul(nf, ideala, idealb)); \\ Apparent infinite loop with \p120
\q