Java中巨大BigIntegers的更快的素因子分解

Question

因此我正在處理Java代碼。我已經完成了它的工作，但是分配的重點是將其分解爲大數字（超過30位數字）。它是這樣做的，但是它可能需要15分鐘才能完成，這是不好的。我的教授向我保證，我使用的算法適用於最高2^70的數字，並且應該在大約五分鐘內完成。我一直在想辦法做到這一點（增加2而不是1等），但我似乎無法弄清楚如何在不跳過某些因素的情況下更快地移動它。有任何想法嗎？我也認爲橢圓曲線方法會更好，但他告訴我現在不處理這個問題。

這裏是我的代碼（PS，該開方是我自己的功能，但我相信這是工作）：

Answer 1

當你把你的monster的一個主要因素，你也應該調整top相應。實際上，外部循環將始終以原始數字的平方根運行，以1或2爲增量，對於30位數的數字，其大小爲10^15個數量級......這是值得懷疑的你只用了15分鐘就完成了！

如果你的怪物號碼有非常大的素數因素（比如說它本身就是一個素數），那麼在任何情況下你都可以忘記好的表現。

請注意，您的示例代碼執行錯誤的增量：如果原始數字不是偶數那麼jump將始終保持爲two，這意味着您只調查偶數因素，因此將找不到任何數字。

Answer 2

不知道你爲什麼要返回一個字符串！

這適用於我。需要注意的是它比較i，每次圍繞n/i和n = n/i：

// Memoization of factors. 
static Map<BigInteger, List<BigInteger>> factors = new HashMap<>(); 
private static final BigInteger TWO = BigInteger.ONE.add(BigInteger.ONE); 

public static List<BigInteger> factors(BigInteger n, boolean duplicates) { 
    // Have we done this one before? 
    List<BigInteger> f = factors.get(n); 
    if (f == null) { 
    // Start empty. 
    f = new ArrayList<>(); 
    // Check for duplicates. 
    BigInteger last = BigInteger.ZERO; 
    // Limit the range as far as possible. 
    for (BigInteger i = TWO; i.compareTo(n.divide(i)) <= 0; i = i.add(BigInteger.ONE)) { 
     // Can have multiple copies of the same factor. 
     while (n.mod(i).equals(BigInteger.ZERO)) { 
     if (duplicates || !i.equals(last)) { 
      f.add(i); 
      last = i; 
     } 
     // Remove that factor. 
     n = n.divide(i); 
     } 
    } 
    if (n.compareTo(BigInteger.ONE) > 0) { 
     // Could be a residue. 
     if (duplicates || n != last) { 
     f.add(n); 
     } 
    } 
    // Memoize. 
    factors.put(n, f); 
    } 
    return f; 
} 

Answer 3

這裏是我的版本整數分解由審判庭：

public static LinkedList tdFactors(BigInteger n) 
{ 
    BigInteger two = BigInteger.valueOf(2); 
    LinkedList fs = new LinkedList(); 

    if (n.compareTo(two) < 0) 
    { 
     throw new IllegalArgumentException("must be greater than one"); 
    } 

    while (n.mod(two).equals(BigInteger.ZERO)) 
    { 
     fs.add(two); 
     n = n.divide(two); 
    } 

    if (n.compareTo(BigInteger.ONE) > 0) 
    { 
     BigInteger f = BigInteger.valueOf(3); 
     while (f.multiply(f).compareTo(n) <= 0) 
     { 
      if (n.mod(f).equals(BigInteger.ZERO)) 
      { 
       fs.add(f); 
       n = n.divide(f); 
      } 
      else 
      { 
       f = f.add(two); 
      } 
     } 
     fs.add(n); 
    } 

    return fs; 
} 

此代碼是在essay在我的博客，解釋還有Pollard的rho算法的解釋，它可能更適合於分解大整數。

順便說一下，30位數字不是一個特別大的因子分解問題。超過幾秒鐘的時間太長。