factorization of Cunningham numbers - applications

[sagetrac-ylchapuy]

Following #7239, use the factorization of Cunningham numbers to speed up polynomial primitivity testing and other finite field stuff (for small characteristic).

Depends on #12133

CC: @jpflori @rwst

Component: factorization

Author: Yann Laigle-Chapuy, David Roe, Ralf Stephan

Branch/Commit: public/cunninghamtables @ b0cb524

Reviewer: John Cremona, R. Andrew Ohana

Issue created by migration from https://trac.sagemath.org/ticket/7240

[sagetrac-ylchapuy]

Author: Yann Laigle-Chapuy

[JohnCremona]

comment:4

The patch applies fine to 4.3.rc0 after installing the optional spkg at #7239 and the patch there, and tests pass. Good doctests included.

BUT in both places where _cunningham_prime_factors() is called, a run-time error will be raised if the optional database is not installed. If the database is really going to be optional then these calls must be wrapped with try/except, otherwise people who have not installed the optional package will find lots of their code fails.

Hence: needs work.

[JohnCremona]

Reviewer: John Cremona

[sagetrac-ylchapuy]

comment:5

In fact if the patch from #7239 is applied, but the database not installed, _factor_cunningham will just be the usual factor, with the first time it's called a warning (not an error) saying:

"You might consider installing the optional package for factoring Cunningham numbers with the following command: sage -i cunningham_tables-1.0"

Moreover this warning will only be seen if the characteristic is p \in {2,3,5,7,11} and p^k > 2^100. I thought it was nice to tell the user that there exists an optional package useful for them, but I can remove it if necessary.

[JohnCremona]

comment:6

OK, that is more reasonable. But why don't we (you!) put a case to sage-devel for including this spkg as standard? It's only another 492837 bytes, and the cremona database is 78M.

[sagetrac-ylchapuy]

comment:7

This ticket is marked as "needs work", but what should be done exactly?

[JohnCremona]

comment:8

I set it to "needs work" but then agreed that it was good (but did not change the label). On the other hand, there has been discussion on sage-devel in favour of including this as standard anyway.

So I suggest that we give this a positive review. This will take two steps....