Find the inverse of BigInt @x in a field of (prime) order @p.

def inverse(x, p, errorOnFail=False):
    """
    Find the inverse of BigInt @x in a field of (prime) order @p.
    """
    # Check types
    assertType(x, BigInt)

    # There are a number of ways in RELIC to compute this inverse, but
    # for simplicity, we'll use the extended GCD algorithm because it 
    # involves less type conversions. On the initial development platform
    # Lehmer's algorithm was the most performant: we call it directly.
    gcd = BigInt()
    inv = BigInt()

    # bn_gcd_ext(c, d, e, a, b) computes: c = a*d + b*e
    # We take x=a. b=p, and expect: c = 1 = gcd(x,p), d = 1/x, and e is unused.
    librelic.bn_gcd_ext_lehme(byref(gcd), byref(inv), None, byref(x), byref(p))

    # Check that GCD == 1 
    if gcd != 1:
        if errorOnFail:
            raise Exception("Cannot find an inverse. gcd(x,p) == {}, but we need gcd(x,p) == 1 to find an inverse.".
                format(long(gcd)))
        else:
            return None

    return inv