Assorted Algorithms

The Extended Euclid Algorithm

The extended Euclid algorithm takes two numbers n and m and computes a triple (d,x,y) where d = gcd(n,m) and n*x + m*y = d.

Suppose that gcd(n,m) = 1. To compute the inverse of n modulo m, run the extended Euclid algorithm, obtaining numbers x and y such that n*x + m*y = 1. Taking this equation mod m, we see that n*x = 1 (mod m). So x is the inverse of n modulo m.

Here is the algorithm.

    Euclid(n,m)
      if m = 0 then return (n,1,0)
      else 
        (d',x',y') = Euclid(m, n mod m)
        q          = floor(n/m)
        (d,x,y)    = (d', y', x' - q*y')
        return (d,x,y)
      end if

Testing whether a number is prime

The following is a randomized algorithm to test whether a number n is composite. When it says that n is composite, it is always correct. When it says that n is prime, there is a small probability (at most 1/2^k) of error. You choose k to be large enough that the error probability is acceptably small. To test whether a number is prime, we define a function witness(w,n). The idea is that witness(w,n) is true if w is a "witness" to the compositeness of n. If witness(w,n) is true, then n is surely composite. It can be shown that, if n is composite, then at least (n-1)/2 of the numbers 1,2,3,...,n-1 are witnesses to the compositeness of n. So the algorithm to test whether n is prime or composite goes like this. Function random(a,b) is presumed to produce a random number in the range a,a+1,...,b, with each number equally likely.

   test-for-prime(n,k)
     if n is even then 
       return COMPOSITE
     end if
     for i = 1,2,...,k
       w = random(1,n-1)
       if witness(w,n) then 
         return COMPOSITE
       end if
     end for
     return PRIME

The witness function is as follows. It is mainly based on Fermat's Little Theorem, that x^(p-1) = 1 (mod p) whenever p is prime and x != 0 (mod p).

    witness(w,n)
      let (b[k], b[k-1], ..., b[1], b[0]) be the binary representation
        of n-1, where b[0] is the least significant bit.
      d = 1
      for i = k downto 0 do
        x = d
        d = (d*d) mod n
        if d = 1 and x != 1 and x != n-1 then 
          return true
        end if
        if b[i] = 1 then
          d = (d*w) mod n
        end if
      end for
      if d = 1
        then return false
        else return true
      endif