def shortgcd2(f, g):
    """Original shortgcd2 algorithm from [BY19].

    Invariant: f should be odd.
    See paper: https://eprint.iacr.org/2019/266
    """
    delta = 1
    assert f & 1
    m = 4 + 3 * max(f.bit_length(), g.bit_length())
    for _ in range(m):
        if delta > 0 and g & 1:
            delta, f, g = -delta, g, -f
        delta, g = 1 + delta, (g + (g & 1) * f) // 2
    return abs(f)