py_ecc/utils.py
def prime_field_inv(a: int, n: int) -> int:
    """
    Extended euclidean algorithm to find modular inverses for integers
    """
    if a == 0:
        return 0
    lm, hm = 1, 0
    low, high = a % n, n
    while low > 1:
        r = high // low
        nm, new = hm - lm * r, high - low * r
        lm, low, hm, high = nm, new, lm, low
    return lm % n
def prime_field_inv(a: int, n: int) -> int:
    if a == 0:
        return 0
    lm, hm = 1, 0
    low, high = a % n, n
    while low > 1:
        r = high // low
        nm, new = hm - lm * r, high - low * r
        lm, low, hm, high = nm, new, lm, low
    return lm % n
def prime_field_inv ( a : int , n : int ) -> int : if a == 0 : return 0 lm , hm = 1 , 0 low , high = a % n , n while low > 1 : r = high // low nm , new = hm - lm * r , high - low * r lm , low , hm , high = nm , new , lm , low return lm % n
Extended euclidean algorithm to find modular inverses for integers
Extended euclidean algorithm to find modular inverses for integers