Author lschoe
Recipients lschoe, mark.dickinson, pablogsal, rhettinger, skrah, steven.daprano, tim.peters
Date 2019-02-20.17:55:19
SpamBayes Score -1.0
Marked as misclassified Yes
Message-id <1550685319.72.0.0544943617576.issue36027@roundup.psfhosted.org>
In-reply-to
Content
In pure Python this seems to be the better option to compute inverses:

def modinv(a, m):  # assuming m > 0
    b = m
    s, s1 = 1, 0
    while b:
        a, (q, b) = b, divmod(a, b)
        s, s1 = s1, s - q * s1
    if a != 1:
        raise ValueError('inverse does not exist')
    return s if s >= 0 else s + m

Binary xgcd algorithms coded in pure Python run much slower.
History
Date User Action Args
2019-02-20 17:55:19lschoesetrecipients: + lschoe, tim.peters, rhettinger, mark.dickinson, steven.daprano, skrah, pablogsal
2019-02-20 17:55:19lschoesetmessageid: <1550685319.72.0.0544943617576.issue36027@roundup.psfhosted.org>
2019-02-20 17:55:19lschoelinkissue36027 messages
2019-02-20 17:55:19lschoecreate