Function poly_find_roots

src/minisketch/tests/pyminisketch.py:260–310

Find the roots of poly if fully factorizable with unique roots, [] otherwise.

(poly, gf)

    return out

def poly_find_roots(poly, gf):
    """Find the roots of poly if fully factorizable with unique roots, [] otherwise."""
    assert len(poly) > 0
    # If the polynomial is constant (and nonzero), it has no roots.
    if len(poly) == 1:
        return []
    # Make the polynomial monic (which doesn't change its roots).
    poly = poly_monic(poly, gf)
    # If the polynomial is of the form x+a, return a.
    if len(poly) == 2:
        return [poly[0]]
    # Otherwise, first test that poly can be completely factored into unique roots. The polynomial
    # x^(2^fieldsize)-x has every field element once as root. Thus we want to know that that is a
    # multiple of poly. Compute x^(field_size) mod poly, which needs to equal x if that is the case
    # (unless poly has degree <= 1, but that case is handled above).
    if poly_frobeniusmod(poly, gf) != [0, 1]:
        return []

    def rec_split(poly, randv):
        """Recursively split poly using the Berlekamp trace algorithm."""
        # See https://hal.archives-ouvertes.fr/hal-00626997/document.
        assert len(poly) > 1 and poly[-1] == 1 # Require a monic poly.
        # If poly is of the form x+a, its root is a.
        if len(poly) == 2:
            return [poly[0]]
        # Try consecutive randomization factors randv, until one is found that factors poly.
        while True:
            # Compute the trace of (randv*x) mod poly. This is a polynomial that maps half of the
            # domain to 0, and the other half to 1. Which half that is is controlled by randv.
            # By taking it modulo poly, we only add a multiple of poly. Thus the result has at least
            # the shared roots of the trace polynomial and poly still, but may have others.
            trace = poly_tracemod(poly, randv, gf)
            # Using the set {2^i*a for i=0..fieldsize-1} gives optimally independent randv values
            # (no more than fieldsize are ever needed).
            randv = gf.mul2(randv)
            # Now take the GCD of this trace polynomial with poly. The result is a polynomial
            # that only has the shared roots of the trace polynomial and poly as roots.
            gcd = poly_gcd(trace, poly, gf)
            # If the result has a degree higher than 1, and lower than that of poly, we found a
            # useful factorization.
            if len(gcd) != len(poly) and len(gcd) > 1:
                break
            # Otherwise, continue with another randv.
        # Find the actual factors: the monic version of the GCD above, and poly divided by it.
        factor1 = poly_monic(gcd, gf)
        factor2, _ = poly_divmod(poly, gcd, gf)
        # Recurse.
        return rec_split(factor1, randv) + rec_split(factor2, randv)

    # Invoke the recursive splitting with a random initial factor, and sort the results.
    return sorted(rec_split(poly, random.randrange(1, 1 << gf.field_size)))

class TestPolyFindRoots(unittest.TestCase):
    """Test class for poly_find_roots."""