Currently the charpoly and minpoly over ZZ use early terminated Chinese Remainder, with a fixed number of stabilization checks. This is a heuristic algorithm and has caused user test-cases to fail ( see
https://trac.sagemath.org/ticket/21579 and https://trac.sagemath.org/ticket/15535)
In the previous release, we made the decision to leave the heuristic variant as a default, claiming we would adress the problem.
We therefore patched LinBox in sage, and other packagers had to also patch the library. See https://trac.sagemath.org/ticket/24214#comment:17
and following comments
We still did not address the problem, and I suggest the following changes implemented in this PR:
switch between Heuristic (EarlyTermination CRA) or Deterministic (FullCRA) in the charpoly and minpoly with IntegerTag.
ideally the switch should be controlled by a parameter of the method. Unfortunately, we did not rework the structure of the methods so far, so let's keep it for a next step.
for the moment, the switch is done by a macro __LINBOX_HEURISTIC_CRA which the user may define if she wants to use early terminated CRA.
in the deterministic case, the charpoly-hadamard bound had bugs and was harcoded within the algorihtm. I wrote it in the recent solutions/hadamard-bound.h based on the existing FastHadamardBound function. This fixes #191 .
Currently the charpoly and minpoly over ZZ use early terminated Chinese Remainder, with a fixed number of stabilization checks. This is a heuristic algorithm and has caused user test-cases to fail ( see https://trac.sagemath.org/ticket/21579 and https://trac.sagemath.org/ticket/15535) In the previous release, we made the decision to leave the heuristic variant as a default, claiming we would adress the problem. We therefore patched LinBox in sage, and other packagers had to also patch the library. See https://trac.sagemath.org/ticket/24214#comment:17 and following comments We still did not address the problem, and I suggest the following changes implemented in this PR:
__LINBOX_HEURISTIC_CRAwhich the user may define if she wants to use early terminated CRA.solutions/hadamard-bound.hbased on the existingFastHadamardBoundfunction. This fixes #191 .