c++ntl

How can you check if a polynomial is invertible with NTL?


I've searched for hours and have not found an answer. I am working with polynomials modulo another polynomial (so ZZ_pE objects). When I use the method inv(ZZ_pE poly), the result is either the inverse (if it exists), or the following error message:

ZZ_p: division by non-invertible element
Abort trap: 6

I tried using a try/catch:

    while(1)
    {
    random(f);
    f = 2*f + 1;    
        try{
            inv(fi, f);
            break;
        }
        catch(...) {
            // f not invertible
            // Do nothing
        }
    }

but the error message still stops the program. As far as I know there is no isInvertible or similar method. How can I check if a polynomial is invertible?


Solution

  • Checking if a polynomial is invertible in ZZ_pE highly depends on your choice of p and polynomial you use for the modulo. In NTL p don't have to be prime, so ZZ_p does not need to be a field and the polynomial does not need to be irreducable, so ZZ_pE can be anything.

    Your solution don't work because NTL throws errors instead of exceptions by default. But you can change this if you compile NTL using the option NTL_EXCEPTIONS=on.
    See http://www.shoup.net/ntl/doc/tour-unix.html for more details.