Function rec_split

src/minisketch/tests/pyminisketch.py:278–307

Recursively split poly using the Berlekamp trace algorithm.

(poly, randv)

        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)))