Mersenne numbers, when they are primes, are routinely used to feed MonteCarlo random number generation. They have the form:
.Since not all of them are prime, we can use prime factorization of a sequence of big Mersenne numbers to benchmark our CPU.
The ingredients are fairly minimalistic:
all we need is a Linux bash shell (with the wonderful bench calculator bc), the java compiler (Linux: javac) and the java virtual machine (Linux: java). To factorize we could use for example the Pollard Rho method in this implementation.
import java.math.BigInteger; import java.security.SecureRandom; class PollardRho { private final static BigInteger ZERO = new BigInteger("0"); private final static BigInteger ONE = new BigInteger("1"); private final static BigInteger TWO = new BigInteger("2"); private final static SecureRandom random = new SecureRandom(); public static BigInteger rho(BigInteger N) { BigInteger divisor; BigInteger c = new BigInteger(N.bitLength(), random); BigInteger x = new BigInteger(N.bitLength(), random); BigInteger xx = x; // check divisibility by 2 if (N.mod(TWO).compareTo(ZERO) == 0) return TWO; do { x = x.multiply(x).mod(N).add(c).mod(N); xx = xx.multiply(xx).mod(N).add(c).mod(N); xx = xx.multiply(xx).mod(N).add(c).mod(N); divisor = x.subtract(xx).gcd(N); } while((divisor.compareTo(ONE)) == 0); return divisor; } public static void factor(BigInteger N) { if (N.compareTo(ONE) == 0) return; if (N.isProbablePrime(20)) { System.out.println(N); return; } BigInteger divisor = rho(N); factor(divisor); factor(N.divide(divisor)); } public static void main(String[] args) { BigInteger N = new BigInteger(args[0]); factor(N); } }
If processor time has to be accurately recorded, just add the “time” command in front of the java runtime, like this:
for n in `seq 101 2 201`; \ do echo "[Factoring Mersenne `echo 2^$n-1`]" ; \ time java PollardRho `echo 2^$n -1 |bc` ; \ done
The code snippet above loops all the odd numbers 
