Web Services and the Search for Really Big Prime Numbers
Pages: 1, 2, 3, 4, 5

Informing the Client

The observer pattern is used here as a callback to the FactorFactory object to tell it that the Factor object created to factorize a particular Mersenne number is now finished. To achieve this, FactorFactory implements the observer interface while the Factor object implements the subject interface.

Example 2. Implementing the observer interface.

/**
 * This object is used to factorize a Mersenne number. There are 
 * potentially many of these created in memory at run time.
 * @testcase test.TestFactor
 * @author Eoin Lane
 * @version 1.0
 */
public class Factor implements IFactor, Subject {
    /**
     * Constructor
     * @param MersenneNumber a number of the form (2^k-1)
     */
    public Factor(MersenneNumber MersenneNumber) {
        strategy = new LLFactorer();
        this.MersenneNumber = MersenneNumber;
    }

    /** factorize this object */
    public void factorize() {
        factors = this.strategy.factorize(this.MersenneNumber);
        this.inform();
    }

    public MersenneNumber getMersenneNumber() {
        return this.MersenneNumber;
    }

    /**
     * Register an observer with this object.
     * @param observer an observer
     */
    public void attach(Observer observer) {
        observersVector.addElement(observer);
    }

    /**
     * detach an observer from this object.
     * @param observer an observer
     */
    public void detach(Observer observer) {
        observersVector.removeElement(observer);
    }

    /** Inform all the observers of an event */
    public void inform() {
        java.util.Enumeration enumeration = observers();
        Collection bag = this.getFactors();
        while (enumeration.hasMoreElements()) {
            ((Observer)enumeration.nextElement()).update(this);
        }
    }

    public Enumeration observers() {
        return ((java.util.Vector) observersVector.clone()).elements();
    }

    public Collection getFactors() {
        return factors;
    }

    /*# private FactorFactory _factorFactory; */

    // The (2^k-1) object
    private MersenneNumber MersenneNumber;
    // The factors returned by the factorisation method
    private Collection factors;
    // The strategy to be used to factorize this object
    private IFactorer strategy = null;
   
    /** @associates <{Observer}> */
    private Vector observersVector = new java.util.Vector();
}

Making the Calculation

A strategy pattern is used to implement the factorization. The strategy pattern allows an algorithmic change of the implementation at runtime, depending on the choice of strategies (i.e., a different algorithm may be used, depending on the size of the number to be factored). Example 3 gives the code for LLFactorer, a simple algometric implementation of the IFactor interface.

Example 3. LLFactorer

import java.util.Collection;
import primes.PrimeNumber;
import java.lang.Math;
import perfectNumbers.MersenneNumber;

/**
 * A simple concrete implementation of the strategy IFactorer interface
 * @testcase test.TestLLFactorer
 * @author Eoin Lane
 * @version 1.0
 */
public class LLFactorer implements IFactorer {
    public Collection factorize(Number number) {
        return new java.util.ArrayList(null);
    }

    // We can check a potential factor n of Mp by seeing if 2^p (mod n) =1
    public Collection factorize(MersenneNumber MersenneNumber) {
        System.out.println("Got Mersenne number for processsing");
        // A Collection bag to collect the factors
        Collection bag = new java.util.ArrayList();
        double maxNumberOfIteration = 
                Math.pow((double)2, (double)(MersenneNumber.getK()));
        double siveNumberOfIteration = sive(maxNumberOfIteration);
        for (long i = 1; i < siveNumberOfIteration; i++) {
            if ((factorize(MersenneNumber.getK(), (long)i) == 0)) {
                bag.add(new Long(i));
                System.out.println(i + "\t" + factorize(MersenneNumber.getK(), i));
            }
        }
        return bag;
    }

    //a simple algorithm for checking for find a^b (mod c)
    public static double factorize(double b, double c) {
        double a = 2;
        double res = 1;
        double d;
        while (b > 0) {
            d = b % 2;
            if (d == 1) {
                res = a * res;
                if (res > c) res = res % c;
            }
            a = a * a;
            if (a > c)
                a = a % c;
            b = (b - d) / 2;
        }
        return res;
    }

    // A simple sive to cut down the number of potential factors
    public static double sive(double a) {
        return (a + 1) / 2;
    }
}

The Factor object calls the public Collection factorize(MersenneNumber MersenneNumber) method defined in the Factorer interface to do the factorization. The LLFactorer object (shown above) implements this method by first calling the public static long sive(long a) method to cut down on the potential factor. This is a very simple method that just cuts the number of factors in half. For instance, for checking 2⁴-1 = 15, only factors up to half of that number need to be checked.

We then iterate through the potential factors and individually check them using the factorized algorithm found in the public static double factorize(double b, double c) method. Most of the material for the above strategy code can be found at the Mersenne FAQ.

Pages: 1, 2, 3, 4, 5

Next Page