Simple Efficient Modpow

chrislee35 (Chris Lee) — Sun, 14 Sep 2008 02:11:29 GMT

Raise large numbers to large exponents in modulus space.



def modpow(base, power, modulus)

  m=base

  pow = power.to_s(2)

  1.upto(pow.length - 1) do |i|

    m *= m

    m %= modulus

    if pow[i] == "1"[0]

      m *= base

      m %= modulus

    end

  end

  m

end

Modular inverse function

Minimiscience (Guildorn Tanaleth) — Thu, 05 Jul 2007 03:42:06 GMT

This function calculates & returns the inverse of a modulo n, both of which should be positive. If the inverse does not exist, 0 is returned. If you don't know what this means, don't bother.



int modInverse(int a, int n) {

 int i = n, v = 0, d = 1;

 while (a>0) {

  int t = i/a, x = a;

  a = i % x;

  i = x;

  x = d;

  d = v - t*x;

  v = x;

 }

 v %= n;

 if (v<0) v = (v+n)%n;

 return v;

}

DZone Snippets: modulus code

Simple Efficient Modpow

Modular inverse function