Wrong modular characteristic polynomial

[gilvillard]

In relation with linbox-team/linbox#305.

The matrix A attached has characteristic polynomial x^35. The largest invariant factor of A over Q (and modulo most primes) is s1=x^13. There are 5 non-trivial invariant factors.

I get (macOS 13.4.1, Apple M2 Pro, clang-1403.0.22.14.1):
example/charpoly 37 issue_sage_35846_matrix.sms
(6)*X^27 + (7)*X^28 + (6)*X^30 + (-8)*X^31 + (-13)*X^32 + (-13)*X^33 + X^35

p=37 >= 35 (or a greater prime) leads to a call to RandomKrylovPrecond, where the bug may seem to be located.
Using a block of two vectors, RandomKrylovPrecond pushes a wrong first dense factor of degree 5.

Among other things I suspect two lines in ffpack_frobenius.inl:

• L138: the elimination is done on N (35) rows, while the Krylov matrix has noc*degree (60) rows. The computed rank is 18=13+5, which is correct. This could give a first invariant of degree 13 and I would say that the 5 is not relevant.
• L201: the smallest degree is chosen, here 5, which is wrong.

I dont't think it's a problem of randomization, here the first degree 13 could probably deduced and pushed instead.

issue_sage_35846_matrix.sms.zip

[ClementPernet]

test-charpoly fails on this branch (running the ArithProgPRecond method). I need to look into further details to see what did I break.