Opened 11 years ago

Closed 6 years ago

#7602 closed defect (fixed)

bug in fpLLL

Reported by: malb Owned by: was
Priority: critical Milestone: sage-duplicate/invalid/wontfix
Component: linear algebra Keywords:
Cc: Merged in:
Authors: Reviewers: Martin Albrecht, André Apitzsch, Peter Bruin
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by AlexGhitza)

AndyNovo? wrote on http://groups.google.com/group/sage-devel/browse_thread/thread/12cbd8a649a3d655/:

We've been working on factoring polynomials in FLINT very intensively the last couple months.  So we've been making floating point LLL in FLINT.  During the process I just discovered what I thought was my bug but is actually a bug in fpLLL which means it's a bug in SAGE too.

Here's a simple lattice which triggers the bug on my 32 bit machine.
(It's the zero rows which are not handled cleanly causing it to size
reduce in very odd ways...)  For a 64 bit machine I have a much larger example which breaks it.

[[0 0 0 0 0]
[0 0 0 0 0]
[1 0 0 0 11]
[0 1 0 0 47]
[0 0 1 0 3748]]

To test the bug in SAGE just run the following code:

matrix([[0,0,0,0,0],[0,0,0,0,0],[1,0,0,0,11],[0,1,0,0,47],
[0,0,1,0,3748]]).LLL()

(This was on SAGE 4-1-1 the August 14th version.)

Change History (11)

comment:1 Changed 11 years ago by malb

AndyNovo? on [sage-devel]:

OK found the bug. There is a program called get_Shift which gets confused by zero vectors. In any call to Babai if you just add a line setting n = the number of columns of B (I'm not sure his notation in the C++ version) then it works again.

comment:2 Changed 9 years ago by AlexGhitza

  • Description modified (diff)

comment:3 Changed 9 years ago by roed

  • Report Upstream changed from Reported upstream. Little or no feedback. to Reported upstream. No feedback yet.

comment:4 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-5.11 to sage-5.12

comment:5 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:6 Changed 7 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:7 Changed 7 years ago by malb

I can't reproduce/test due to lack of 32-bit machine, anyone still got one?

comment:8 Changed 6 years ago by vbraun_spam

  • Milestone changed from sage-6.3 to sage-6.4

comment:9 Changed 6 years ago by aapitzsch

  • Milestone changed from sage-6.4 to sage-duplicate/invalid/wontfix
  • Status changed from new to needs_review

The example that should fail on 64bit OS mentioned in the thread works for me.

comment:10 Changed 6 years ago by pbruin

  • Report Upstream changed from Reported upstream. No feedback yet. to N/A
  • Reviewers set to Martin Albrecht, André Apitzsch, Peter Bruin
  • Status changed from needs_review to positive_review

The example in the ticket description also works fine on 32-bit ARM, so I think we can safely assume that this has been fixed.

comment:11 Changed 6 years ago by vbraun

  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.