Android中的素數因子分解

Question

我正在開發一個適用於Android設備的小素數數字應用程序，接近完成，但是我希望能夠幫助我優化分解類。

我仍然有一個或兩個問題與一些大數字（偶數）在一段合理的時間內被分解。我認爲我無法使用Eratosthenes的篩選器來篩選這個特定的項目，因爲我只能在沒有應用程序在我的物理設備（Samsung Galaxy S4 Mini）上崩潰的情況下篩選多達1000萬個篩選器。所以我的算法在下面。我不確定是否可以製作出更好的Pollard Rho算法。

一旦我確定被測試的數字不是素數或不是一個素數平方，我很快就會進行試驗分區達到10000，之後如果這個數字還沒有完全考慮，我使用Pollard Rho方法來減少它的其餘部分。

我希望能夠在2> 2^64範圍內進行因子分解。

這是採取大致15秒256332652145852

一個數的一例這是因式分解爲[2,2，1671053，38348971]。

任何幫助將不勝感激。

try { 
     long num = Long.valueOf(input); 
     if(num == 1) { 
      return "1" + " = " + input; 
     } else if(num < 1) { 
      return "Cannot factor a number less than 1"; 
     } else if(PrimeNumbers.isPrime(num) == true) { 
      return result = num + " is a Prime Number."; 
     } else if(isSquare(num) == true && PrimeNumbers.isPrime((long) Math.sqrt(num)) == true) { 

      return result = (int) Math.sqrt(num) + "<sup><small>" + 2 + "</small></sup>" + " = " + input; 

     } else { 
      factors(num, pFactors); 
      return result = exponentialForm(pFactors, num) + " = " + input; 
     } 
    } catch(NumberFormatException e) { 
     return result = "Unfortunately the number entered is too large"; 
    } 
} 

public static void factors(long n, ArrayList<Long> arr) { 

    long number = trialDiv(n, arr); 
    if(number > 1) { 
     while(true) { 
      long divisor = pollard(number, 1); 
      if(PrimeNumbers.isPrime(divisor) == true) { 
       number /= divisor; 
       arr.add(divisor); 
       if(PrimeNumbers.isPrime(number) == true) { 
        arr.add(number); 
        break; 
       } 
      } 
     } 
    } 
} 

private static long trialDiv(long n, ArrayList<Long> arr) { 

    while(n % 2 == 0) { 
     n /= 2; 
     arr.add((long) 2); 
    } 

    for(long i = 3; i < 10000; i += 2) { 
     if(PrimeNumbers.isPrime(i) == true) { 
      while(n % i == 0) { 
       arr.add(i); 
       n /= i; 
      } 
     } 
    } 
    if(PrimeNumbers.isPrime(n) == true) { 
     arr.add(n); 
     return 1; 
    } 
    return n; 
} 

public static long pollard(long n, long c) { 

    long x = 2; 
    long y = 2; 
    long d = 1; 

    while (d == 1) { 
     x = g(x, n, c); 
     y = g(g(y, n, c), n, c); 
     d = gcd(Math.abs(y - x), n); 
    } 

    if (d == n) { 
     return pollard(n, c + 1); 
    } else { 
     return d; 
    } 
} 

static long g(long x, long n, long c) { 
    long g = (((x * x) + c) % n); 
    return g; 
} 

static long gcd(long a, long b) { 
    if (b == 0) { 
     return a; 
    } else { 
     return gcd(b, a % b); 
    } 
} 

Answer 1

您的pollard功能沒問題，但不是很好。您正在使用Pollard的原始算法，但使用Brent的變體會更好。但這可能不是你慢速表現的來源。

您的審判師職能很慢。檢查每個可能的除數是否非常昂貴，而不是必需的。如果你除以一個複合物，這並不重要;該部門將永遠失敗，但你不會浪費時間檢查素數。更好的方法是輪子分解。