Re: What's the difference of fplll and NTL' BKZ(LLL) function.

[Martin R. Albrecht]

Hi Levi,

I see no reason to use NTL’s BKZ or FPLLL’s in any situation, but I might be missing something (?)

It looks like you need to use fp type MPRF and set a higher precision to make the FPLLL implementation work?

Cheers,
Martin

On Wed, Apr 19 2023, levi ackerman wrote:
> Dear Martin,
>
> Hi, I recently used fplll heavily. This is totally a wonderful work. And
> big thanks for bringing this work to community.
>
> I faced some problems in using fplll recently. Fplll has better performance
> in doing BKZ reduction than NTL. Like when I do a BKZ reduction in
> dimension 200 lattice. My computer (i7-10510U CPU) cost about 300s use
> fplll while cost about 9000s use NTL!
>
> This is a big difference! But somehow fplll can't run BKZ in higher
> dimension even if I set fp = 'ld' in BKZ. The error
>
>> terminate called after throwing an instance of 'std::runtime_error'
>> what(): infinite loop in babai
>>
> will occur. But NTL can run although with its lower performance.
>
> Hence the question in title comes to my mind. When should we use fplll and
> when should we use NTL? Is there any situation fplll can return a result
> but NTL can't？Or generally, does fplll always has better performence than
> NTL? Are there some situation that NTL has better performance than fplll?
>
> Is ther any paper/blog dicuss these differences?
>
> All the best.
>
> Levi


--

_pgp: https://keybase.io/martinralbrecht
_www: https://malb.io
_prn: he/him or they/them

[Martin R. Albrecht]

Hi Levi,

Both FPLLL and NTL implement both LLL and BKZ (with enumeration as the SVP oracle). IIRC NTL doesn’t implement the faster L2 variant of LLL but FPLLL does, NTL definitely does not implement the faster BKZ variants that FPLLL does.

See e.g. here for a tutorial:

https://www.icms.org.uk/sites/default/files/downloads/Masrtin%202%20%28worksheet%29.pdf

Cheers,
Martin

On Wed, Apr 19 2023, levi ackerman wrote:
> Dear Martin,
>

> Thanks for you reply.
>
> I'm confused about "no reason to use NTL’s BKZ or FPLLL’s in any
> situation".
>
> Why the conlcusion? What if we want do basis reduction? If there is no
> reason to use, why the function exists...
> Do you mean we should use LLL more? Or is there any higher interface we
> should use?
>
> Also thanks for the suggestion in higher precision methods.
>
> All the best.
>
> Levi.
>
> Martin R. Albrecht <martinr...@googlemail.com> 于2023年4月19日周三 15:42写
> 道：