def _fastdivmod(dividend, divisor):
        '''Fast polynomial division by using Extended Synthetic Division (aka Horner's method). Also works with non-monic polynomials.
        A nearly exact same code is explained greatly here: http://research.swtch.com/field and you can also check the Wikipedia article and the Khan Academy video.'''
        # Note: for RS encoding, you should supply divisor = mprime (not m, you need the padded message)
        msg_out = list(dividend) # Copy the dividend
        normalizer = divisor[0] # precomputing for performance
        for i in _range(len(dividend)-(len(divisor)-1)):
            msg_out[i] /= normalizer # for general polynomial division (when polynomials are non-monic), the usual way of using synthetic division is to divide the divisor g(x) with its leading coefficient (call it a). In this implementation, this means:we need to compute: coef = msg_out[i] / gen[0]. For more infos, see http://en.wikipedia.org/wiki/Synthetic_division
            coef = msg_out[i] # precaching
            if coef != 0: # log(0) is undefined, so we need to avoid that case explicitly (and it's also a good optimization)
                for j in _range(1, len(divisor)): # in synthetic division, we always skip the first coefficient of the divisior, because it's only used to normalize the dividend coefficient
                    if divisor[j] != 0: # log(0) is undefined so we need to avoid that case
                        msg_out[i + j] += -divisor[j] * coef

        # The resulting msg_out contains both the quotient and the remainder, the remainder being the size of the divisor (the remainder has necessarily the same degree as the divisor -- not length but degree == length-1 -- since it's what we couldn't divide from the dividend), so we compute the index where this separation is, and return the quotient and remainder.
        separator = -(len(divisor)-1)
        return Polynomial(msg_out[:separator]), Polynomial(msg_out[separator:])
Fast polynomial division by using Extended Synthetic Division (aka Horner's method). Also works with non-monic polynomials.
        A nearly exact same code is explained greatly here: http://research.swtch.com/field and you can also check the Wikipedia article and the Khan Academy video.