(I only read the very first function from the implementation, so I apologise for the overly-specific comment in advance.) Simple and fast ways of calculating m

(I only read the very first function from the implementation, so I apologise for the overly-specific comment in advance.) Simple and fast ways of calculating modular inverses are: - Bézout's identity. That is, inverting p mod q can be done by adapting the Euclidean GCD algorithm to produce numbers x and y such that xp + yq = gcd(p, q). The adaptation is usually called the Extended Euclidean Algorithm, and it is simple: For the base case of the Euclidean algorithm, where p divides q, we can take x = 1 and y = 0. For the other cases, we can use recursion: if we have x', y' satisfying x' * p + y' * (q%p) = gcd(p, q%p) = gcd(p, q), then summing and subtracting y' * p * (q/p) (integer division here) allows q to reappear in the equation by some rearranging, since q = (q/p) * p + (q%p). This allows us to find x, y in terms of x', y'. Since p is prime in this particular case, gcd(p, q) = 1 for all relevant values of q and thus y is the modular inverse of q: xp + yq = 1 (mod p) implies yq = 1 (mod p). Perhaps it's relevant to mention that this method works even for non-prime p, just as long as gcd(p, q) = 1. - Fermat's little theorem. That is, the inverse of q (mod p) is q^(p-2) (mod p), since q^(p-2) * q = q^(p-1) = 1 (mod p) by Fermat's little theorem. You can compute q^(p-2) (mod p) in logarithmic time by doing binary exponentiation: a^b is 1 if b is zero; it equals (a^(b/2))^2 if b is even, and it equals a * (a^(b/2))^2 if b is odd (integer division again!).