Platform-dependent LLL reduction (qflll)

mancha <[email protected]>
Newsgroups gmane.comp.mathematics.pari.devel
Message-ID <[email protected]>
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));
lmpx.com only provides a reader for public news (NNTP) servers. It is not affiliated with the servers or forums shown here and is not responsible for the content of articles, which is written by their respective authors.