keeganryan / flatter

Fast lattice reduction
GNU Lesser General Public License v3.0
170 stars 18 forks source link

MPFR assertion failed #14

Closed NaIrW closed 8 months ago

NaIrW commented 8 months ago

I am using fllatter to reduce a 72-dimensional square lattice, the largest element of which is 11980 bits, but I encountered

round_prec.c:60: MPFR assertion failed: ((prec) >= 1 && (prec) <= ((mpfr_prec_t) ((((mpfr_uprec_t) -1) >> 1) - 256)))

flatter exited so quickly, so I think an overflow occurred during the initialization phase.

keeganryan commented 8 months ago

There might be an issue with how the precision is computed, and there are a couple places where precision might be set. Do you have a short script that generates the lattice you're trying to reduce? Is the basis triangular or not? Does a longer stack trace print along with the error?

NaIrW commented 8 months ago

Hi, the only other hint is that the ’core dumped‘. Then, I tried the verbose mode and it said that the determinant of my matrix was not calculated because it is not triangular. My matrix could have been triangular, but there was an error in the order of the rows. So I do this below:

new = matrix(dim, dim)
for i in range(dim):
    for j in range(dim):
        if orig[i, dim - j] != 0:
            new[dim - j] = orig[i]
            break

After organizing my matrix, the problem was solved. :) Finally, thx, Flatter is nearly 30 times faster than FPLLL

keeganryan commented 8 months ago

Great, glad to hear it!

What I suspect happened is due to how flatter estimates necessary precision for non-triangular bases. The precision depends on the log-condition number, which can be quite large in the worst case, but is manageable for most applications. In this case, the log-condition number was probably larger than estimated, the early floating-point operations became unstable, and predictions for future precision overflowed.

This is not ideal behavior, though, and flatter should handle these cases more gracefully. Short term, flatter should detect when this has happened and either increase the estimate of log-condition number or report an error. Long term, algorithms should be developed to work around the pessimistic bound from the condition number.

If any other users run into this same error, there are two potential fixes:

  1. Reorganize your lattice basis so that the basis is upper- or lower-triangular.
  2. Manually increase the -logcond command-line argument until it works. A good first guess is the bit-length of entries, but in the worst case it can be dimension * bit-length.