CVP Proved worse than CVP Fast?

18 views
Skip to first unread message

Martin R. Albrecht

unread,
Apr 2, 2019, 10:55:31 AM4/2/19
to Fplll-Devel
Hi all,

At https://github.com/fplll/fpylll/pull/137 the following behaviour was observed:

: from fpylll import *
: FPLLL.set_random_seed(6)
: A = LLL.reduction(IntegerMatrix.random(40, "uniform", bits=10))
: t = list(IntegerMatrix.random(40, "uniform", bits=10)[0])

: fast = CVP.closest_vector(A, t, method="fast")
: proved = CVP.closest_vector(A, t, "proved")

: sum((fast[i]-t[i])**2 for i in range(40)) < sum((proved[i]-t[i])**2 for i in range(40))

True

In other words, CVP method “fast” produces closer vectors than “proved”, which doesn’t seem to make sense.

Any ideas?

Cheers,
Martin

--

_pgp: https://keybase.io/martinralbrecht
_www: https://martinralbrecht.wordpress.com
_jab: martinr...@jabber.ccc.de
_otr: 47F43D1A 5D68C36F 468BAEBA 640E8856 D7951CCF

Reply all
Reply to author
Forward
0 new messages