Incorrect assumptions about polynomial in is_HCP()

[GiacomoPope]

Steps To Reproduce

The current code has the following snippet:

        p = next_prime(p)
        n += 1
        fp = f.change_ring(GF(p))
        # Compute X^p-X mod fp
        z = fp.parent().gen()
        r = pow(z, p, fp) - z
        d = r.gcd(fp).degree()  # number of roots mod p
        if d == 0:
            continue
        if not fp.is_squarefree():
            continue
        if d < h and d not in h2list:
            return zero
        jp = fp.any_root(degree=1, assume_squarefree=True, assume_distinct_deg=True)

The problem is, fp.any_root() is called with assume_distinct_deg True. In this case, the polynomial is expected to be the product of irreducible polynomials of degree degree (in this case linear polynomials).

However, this is a typo. The polynomial is not of this form. The correct polynomial to use is the polynomial

r = pow(z, p, fp) - z
r = r.gcd(fp)

As a result of this, tests such as:

from sage.schemes.elliptic_curves.cm import is_HCP
set_random_seed(297388353221545796156853787333338705098)
is_HCP(hilbert_class_polynomial(-55))

Currently error.

This was introduced in the PR #37170 because in the refactoring assume_distinct_deg worked as intended where as the older function seemed to simply always find roots the slow way regardless of how the function was called.

Expected Behavior

The function should work

Actual Behavior

The function does not work

Additional Information

This has been fixed in #37443. The only thing needed to do was to use the polynomial r, as intended, instead of the polynomial fp. This oversight lived in the code until recently purely because any_root() behaved weirdly before.

Environment

- **Sage Version**: SageMath version 10.3.beta8, Release Date: 2024-02-13

Checklist

• I have searched the existing issues for a bug report that matches the one I want to file, without success.
• I have read the documentation and troubleshoot guide