Pollard's Rho

DLPやECDLPを解く手法。乱択アルゴリズム

[** Pollard's for ECDLP]

def pollard_rho(P, Q, G, order):
    """
      Q = xP
      G: generator
  """
    a, b, x = 0, 0, (1, 0)
    A, B, X = a, b, x

    def walk(a, b, x):
        if x[0] % 3 == 0:
            return (a*2) % order, (b*2) % order, multiply(x, 2)
        elif x[0] % 3 == 1:
            return a, (b + 1) % order, add_points(x, Q)
        else:
            return (a + 1) % order, b, add_points(x, P)

    while True:
        a, b, x = walk(a, b, x)
        A, B, X = walk(A, B, X)
        A, B, X = walk(A, B, X)

        if x == X and not is_identity(x):
            return (a - A) * inverse_mod((B - b), order) % order