# Science Friction (1)

Mersenne numbers, when they are primes, are routinely used to feed MonteCarlo random number generation. They have the form: $M_n := 2^{n}-1, \hspace{0.5cm} n \in \mathbb{N}$.

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 {
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);
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 $n \in \{101,103,\ldots,199,201\}$, uses them as Mersenne exponent as $M_n := 2^n-1$ and prints prime factors. Check for example that for $n=107$ the Mersenne number is infact a Mersenne prime.

Categories: Computing