Skip to content

Instantly share code, notes, and snippets.

@peteroupc
Last active November 4, 2016 09:55
Show Gist options
  • Save peteroupc/ece043344377f7f53a7f to your computer and use it in GitHub Desktop.
Save peteroupc/ece043344377f7f53a7f to your computer and use it in GitHub Desktop.
Ruby function for checking primality (prime number status) of 31-bit integers
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment