Modular Multiplicative Inverse Function in Python

Explanation of Modular Inverse for RSA in Python

You are using Extended Euclidean algorithm to find d when:

d⋅e ≡ 1 (mod λ(n));

where in your case e = 17 and λ(n) = phi.

Modular multiplicative inverse function for big (negative) numbers

Adding the line while a < BigInt::zero() { a += p } right underneath the definition of a, m, x, and inv should do the trick, using the fact that a % m == a + m % m.

Modular Inverse Built-In, C++

No there is no built-in function in C++ (to answer your question :) ).

modular multiplicative inverse of an number for calculating nCr % 10000007 (combination)

Here is the Fermat's Little theorem implementation for multiplicative inverse.
I tested it and it works.

   static long modInverse(long a, long m)
   {
         return power(a, m - 2, m);
   }

   // To compute x^y under modulo m
   static long power(long x, long y, long m)
   {
      if (y == 0)
         return 1;

      long p = power(x, y / 2, m) % m;
      p = (p * p) % m;

      if (y % 2 == 0)
         return p;
      else
         return (x * p) % m;
   } 

I'm working on nCr mod M, you don't need that array to find it.

Find the following implementation of nCr mod m, please check it with your values, remember m should be a prime for this method.

   static long nCr_mod_m(long n, long r, long m)
   {
      if(n-r < r) r = (n-r);    //  since nCr = nC(n-r)

      long top_part = n, bottom_part=1;

      for(long i=1; i<r; i++)
         top_part = (top_part*(n-i)) % m;

      for(long i=2; i<=r; i++)
         bottom_part = (bottom_part * modInverse(i, m))%m;

      return (top_part*bottom_part)%m;

   }

A Pure Python way to calculate the multiplicative inverse in gf(2^8) using Python 3

Here is how I'd do it:

def gf_degree(a) :
  res = 0
  a >>= 1
  while (a != 0) :
    a >>= 1;
    res += 1;
  return res

def gf_invert(a, mod=0x1B) :
  v = mod
  g1 = 1
  g2 = 0
  j = gf_degree(a) - 8

  while (a != 1) :
    if (j < 0) :
      a, v = v, a
      g1, g2 = g2, g1
      j = -j

    a ^= v << j
    g1 ^= g2 << j

    a %= 256  # Emulating 8-bit overflow
    g1 %= 256 # Emulating 8-bit overflow

    j = gf_degree(a) - gf_degree(v)

  return g1

The function gf_degree calculates the degree of the polynomial, and gf_invert, naturally, inverts any element of GF(2^8), except 0, of course.
The implementation of gf_invert follows a "text-book" algorithm on finding the multiplicative inverse of elements of a finite field.

Example

print(gf_invert(5))   # 82
print(gf_invert(1))   #  1
print(gf_invert(255)) # 28

Here is a live demo.

As mentioned in the comments you could also have used a logarithmic approach, or simply use brute force (trying every combination of multiplication).

How do I find modular multiplicative inverse of number without using division for fpga?

I recommend the binary euclidean algorithm

it replaces division with arithmetic shifts, comparisons, and subtraction

An extended binary GCD, analogous to the extended Euclidean algorithm, is given by Knuth along with pointers to other versions.

I've found a Python implementation of the binary extended Euclidean algorithm here:

def strip_powers_of_two(c, p, q, gamma, delta):
    c = c / 2
    if (p % 2 == 0) and (q % 2 == 0):
        p, q = p//2, q//2
    else:
        p, q = (p + delta)//2, (q - gamma)//2
    return c, p, q

def ext_bin_gcd(a,b):
    u, v, s, t, r = 1, 0, 0, 1, 0
    while (a % 2 == 0) and (b % 2 == 0):
        a, b, r = a//2, b//2, r+1
    alpha, beta = a, b
    while (a % 2 == 0):
        a, u, v = strip_powers_of_two(a, u, v, alpha, beta)
    while a != b:
        if (b % 2 == 0):
            b, s, t = strip_powers_of_two(b, s, t, alpha, beta)
        elif b < a:
            a, b, u, v, s, t = b, a, s, t, u, v
        else:
            b, s, t = b - a, s - u, t - v
    return (2 ** r) * a, s, t

---

Related Topics