If I understand correctly bnfcertify should either
"return 1 if the bnf structure is correct and likely eventually run out of memory otherwise"
I think, I have an example where the bnf structure is correct, but bnfcertify will never be able to certify. But I might also be missing something.
(Note: the field in the following example contains the 4th roots of unity)
bnf=bnfinit(x^8 - 4*x^5 - x^4 + 4*x^3 + 1,1)
bnfcertify(bnf);
will (on Version 2.12.0 (development 23767-ee30173)) take about an hour to run through 150Gb of ram trying to "primecertify" the prime p=2. (As a note, if you add garbage collection to the primecertify loop it only consumes 3Gb in about 5h... which is
not really much of a win.).
My understanding of how primecertify works is a bit vague, but from what I can tell in this example it is quickly verifying that the non-torsion units are correct, but it cannot seem to verify the torsion.
I don't entirely understand why it is failing, though it might be because of an error in the lines from primecertify:
g = pgener_Fl_local(q, L);
(void)u_lvalrem((q-1) / p, p, &m);
gg = utoipos( Fl_powu(g, m, q) ); /* order p in (Z/q)^* */
og = mkmat2(mkcol(utoi(p)), mkcol(gen_1)); /* order of g */
I don't think gg actually ever has order 2, this might break something later.
Changing the code above to:
g = pgener_Fl_local(q, L);
uint xx = u_lvalrem((q-1) / p, p, &m);
gg = utoipos( Fl_powu(g, m, q) ); /* order p in (Z/q)^* */
og = mkmat2(mkcol(utoi(p)), mkcol(utoi(xx+1))); /* order of g */
Seems to correct things, which is to say results in getting a return value of 1... which is what I want, but someone who knows the code better than I should check if this is actually correct.
Best,
Andrew