Ruby function for checking primality (prime number status) of 31-bit integers

isprime.rb

#!/usr/bin/ruby
def modPow(x,pow,mod)
      r = 1;
      v = x;
      while (pow != 0)
        if ((pow & 1) != 0)
          r = (r*v)%mod;
        end
        pow >>= 1;
        if (pow != 0)
          v = (v*v)%mod;
        end
      end
      return r;
end

def isPrime(n)
      # assumes number is less than 2^31
      if (n < 2)
        return false;
      end
      if (n == 2)
        return true;
      end
      if (n % 2 == 0)
        return false;
      end
      # Use a deterministic Rabin-Miller test
      d = n - 1;
      shift = 0;
      while ((d & 1) == 0)
        d >>= 1;
        shift+=1;
      end
      mp = 0;
      #For all integers less than 2^31 it's enough
      #to check the strong pseudoprime
      # bases 2, 7, and 61
      if (n > 2)
        mp = modPow(2, d, n);
        if mp!=1 && mp+1 != n
          found=false
          for i in 1...shift
            mp2 = modPow(2, d<<i, n);
            if mp2 + 1 == n
              found=true;break
            end
          end
          return false if !found
        end
      end
      if (n > 7)
        mp = modPow(7, d, n);
        if mp!=1 && mp+1!=n
          found=false
          for i in 1...shift
            mp2 = modPow(7, d<<i, n);
            if mp2 + 1 == n
              found=true;break
            end
          end
          return false if !found
        end
      end
      if (n > 61)
        mp = modPow(61, d, n);
        if mp!=1 && mp+1!=n
          found=false
          for i in 1...shift
            mp2 = modPow(61, d<<i, n);
            if mp2 + 1 == n
              found=true;break
            end
          end
          return false if !found
        end
      end
      return true;
end

def nextPrime(p)
  return 2 if p<2
  return 3 if p==2
  p+=1
  p+=1 if p%2==0
  while true
    if isPrime(p)
      return p
    end
    p+=2
  end
end

# Generate a random 31-bit prime number

def randomPrime()
  while true
    p=rand(0x7FFFFFFF)|1
    if p>0x10000000 && isPrime(p)
      return p
    end
  end
end