How is parallel factorization?

Question

The following code fragment calculates simple coefficients of a given number:

public static LinkedList<Long> getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    for (Long factor = Long.valueOf(2); factor <= number / factor; factor++) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {                  
                number /= factor;
            }
        }           
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

It takes 140937ms to calculate simple coefficients 9223372036854775783 (this is the final touch less Long.MAX_VALUE). Is there a way to implement this factorization on concurrency, i.e. using ExecutorService?

Edit:

public static void getPrimeFactors(Long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number) + 1;

    ExecutorService service = Executors.newFixedThreadPool(2);
    LinkedList<Future<LinkedList<Long>>> futures = new LinkedList<Future<LinkedList<Long>>>();
    futures.add(service.submit(new PrimeFactor(3, limit / 2, number)));
    futures.add(service.submit(new PrimeFactor(1 + limit / 2, limit, number)));

    for (Future<LinkedList<Long>> future : futures) {
        try {
            primeFactors.addAll(future.get());
        } catch (InterruptedException e) {
            e.printStackTrace();
        } catch (ExecutionException e) {
            e.printStackTrace();
        }
    }
    service.shutdown();

    if(number>1) {
        primeFactors.add(number);           
    }

    System.out.println(primeFactors);
}

private static class PrimeFactor implements Callable<LinkedList<Long>> {
    private long lowerLimit;
    private long upperLimit;
    private Long number;

    public PrimeFactor(long lowerLimit, long upperLimit, Long number) {
        this.lowerLimit = lowerLimit;
        this.upperLimit = upperLimit;
        this.number = number;
    }

    public LinkedList<Long> call() throws Exception {
        LinkedList<Long> primeFactors = new LinkedList<Long>();
        for (long i = lowerLimit; i < upperLimit; i += 2) {
            if (number % i == 0) {
                primeFactors.add(i);
                while (number % 2 == 0) {
                    number /= i;
                }
            }
        }
        return primeFactors;
    }

}

2nd Edit:

public static LinkedList<Long> getPrimeFactorsByFastGeneralMethod(long number) {
    LinkedList<Long> primeFactors = new LinkedList<Long>();

    if (number % 2 == 0) {
        primeFactors.add(2L);

        while (number % 2 == 0) {
            number /= 2;
        }
    }

    long limit = (long) Math.sqrt(number);

    for (long factor = 3; factor <= limit; factor += 2) {
        if (number % factor == 0) {
            primeFactors.add(factor);
            while (number % factor == 0) {
                number /= factor;
            }
        }
    }

    if (number > 1) {
        primeFactors.add(number);
    }

    return primeFactors;
}

Now a piece of code:

    LinkedList<Long> primeFactors = Factorization.getPrimeFactorsByConcurrentGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

    primeFactors = Factorization.getPrimeFactorsByFastGeneralMethod(600851475143L);
    System.out.println("Result: " + primeFactors.get(primeFactors.size() - 1));

gives the result:

Result: 600851475143
Result: 6857

Note. Class name Factorizationand I changed the method name getPrimeFactorstogetPrimeFactorsByConcurrentGeneralMethod

Answer 1

, . 2, , 2 , 3 2. / ( JIT , ) Sqrt (N) - , p > sqrt (N);)

, , 3 Sqrt (N), . 3-Sqrt (N) K , K - ( , ) . .

, BigIntegers, , - - , , , .

PS: , 2 sqrt (n).

PPS: , , NP, , concurrency.

Answer 2

, , , . - .

(ECM) Prime Factorization. . - . , ,

Answer 3

:

• , .
• Create a shortcut for a “simple” case, for example. d. you iterate over each number between 2 and the number / 2. This is not necessary, since 2 is the only even simple factor. You save half the number of iterations with this shortcut at best.
• You do not need to calculate simple coefficients number, sqrt(number)enough.

• There are More Effective Ways to Integer Factorization

  public static List<Long> getPrimeFactors(long number) {
      List<Long> primeFactors = new ArrayList<Long>();
  
      // Only process natural numbers
      if(number < 1l) {
          return primeFactors;
      }
  
      // The only prime factor of 1 is 1
      if(number == 1l) {
          primeFactors.add(1l);
          return primeFactors;
      }
  
      // Even have the prime factor 2
      if(number % 2l == 0l) {
          primeFactors.add(2l);
  
          while(number % 2l == 0l) {
              number /= 2l;
          }
      }
  
      // Iterate from 3 to sqrt(number) to calculate the remaining prime factors
      for (long factor = 3l; factor < Math.sqrt(number); factor+=2l) {
          if (number % factor == 0) {
              primeFactors.add(factor);
              while (number % factor == 0) {                  
                  number /= factor;
              }
          }           
      }
  
      if (number > 1) {
          primeFactors.add(number);
      }
  
      return primeFactors;
  }