Platform-dependent LLL reduction (qflll)

[mancha <mancha1@zoho.com>]

Hi.

While helping someone with their knapsack-crypto project on freenode's
##math channel, we discovered that LLL-reduced bases generated by 32-bit
and 64-bit versions of PARI/GP 2.13.1 don't always match. Is this
expected/anticipated behavior?

The following script I wrote reproduces the orders of magnitude of the
original knapsack problem and reveals the platform-dependency. On
32-bit, the digest is 8f6de8a7c06c89e3c9b79507fd5eeaf9 and on 64-bit
it's f49406d5c4066234f605530751db8a32 (n.b. it's not just matter of
permuted columns, the bases are different). Both versions of PARI/GP
were built against GMP 6.2.1.

Cheers.

PS Enjoy the Easter Egg

----

md5(obj) = extern(Str("echo '"obj"' | md5sum | cut -b-32 | sed 's/.*/\"&\"/'"));
p = 1427247692705959881058285969449495136382746771; \\ nextprime(2^150);
m = matid(145);
m[,145] = vector(145, i, -1/2)~;
m[145,] = concat(concat(31, vector(143, i, 31*(p+2)*2^(i-1) % p)), -622361547716882217686429076590832002202451766);
l = m*qflll(m);
print(md5(l));