// PFMersenne.java
// Andrew Davison, ad@coe.psu.ac.th, April 2023

/* Find the prime factors of the composite Mersenne number
   2^251 - 1 using JML's TDiv and PollardRho
   factoring classes. 

   According to https://www.mersenne.ca/exponent/251
   the factors are:
        593, S4217, 
        178239287214663289511, 
        61676882198695257591367,
        12070396178249893039969681

   Use a thread to monitor factoring progress, and report results
   without waiting for the algorithm to finish.

   Note: run.bat sets Java's max heap space to -Xmx4G.

   See:
     https://en.wikipedia.org/wiki/Mersenne_prime
*/

import java.math.*;
import java.util.*;
import java.util.concurrent.*;

import de.tilman_neumann.jml.factor.tdiv.TDiv;
import de.tilman_neumann.jml.factor.pollardRho.PollardRho;

import de.tilman_neumann.util.SortedMultiset;
import de.tilman_neumann.util.SortedMultiset_BottomUp;



public class PFMersenne
{
  private static SortedMultiset<BigInteger> factors;
  private static int reportCount = 0;


  public static void main(String[] args)
  {
    System.out.println("Find the prime factors of 2^251 - 1:");
    BigInteger mersenne251 = 
              BigInteger.valueOf(2).pow(251).subtract(BigInteger.ONE);

    // uncomment one of these...
    // TDiv factAlg = new TDiv();
    PollardRho factAlg = new PollardRho();

    factors = new SortedMultiset_BottomUp<>();
          // sorting smallest elements first


    Runnable reporter = new Runnable() {
      public void run() 
      { 
        int count = factors.totalCount();
        if (count > reportCount) {
          System.out.println("Factors found so far: " + factors.toList());
          reportCount = count;
        }
      }
    };
    Executors.newScheduledThreadPool(1).   // 10 secs between checks
         scheduleWithFixedDelay(reporter, 0, 10, TimeUnit.SECONDS);


    // System.out.println("Single: " + factAlg.findSingleFactor(mersenne251));
         // find a single factor -- a fast alternative to factor()

    // factAlg.setTestLimit(10000000);  // argument must be an int
       // only works for TDiv, but limiting the search lets
       // factor() return the first two factors 503 and 54217 instantly

    factAlg.factor(mersenne251, factors);
             // runs out of heap space when running TDiv algorithm;
             // PollardRho algorithm doesn't terminate either, but doesn't crash

    System.out.println(factors.toList());
  } /* main */


}  // end of PFMersenne class