java - 用于素数和因式分解的 Java API

Question

我正在寻找用于快速素性测试和大数分解的 Java API。任何指针都会对我很有帮助。

更新

我找到的资源是：

• BigInteger - 没有分解
• Primes - 处理整数
• LargeInteger - 没有分解

我期待使用Elliptic Curve Factorization或Quadratic Sieve的 API 。

另一个资源：使用椭圆曲线方法进行分解。

限制：10000 位数字。

Answer 1

我建议Commons Math。你可以在这里找到lib API 。对您来说有趣的课程是Primes。

Answer 2

我使用了用 Java 实现的 Eratosthenes 算法的筛子

public static ArrayList<Integer> primeNumbers(int end) {
		// generate array of number from 2 to end
		// generate flag array of same size
		// this numbers are inclusive
		int eff = 0;
		ArrayList<Integer> factors = new ArrayList<Integer>();
		if (end < 2) {
			return factors;
		}
		if (end == 2) {
			factors.add(2);
			return factors;
		}
		int numbers[] = new int[end - 1];
		boolean flags[] = new boolean[end - 1];
		int count = 2;
		// lets reset all numbers
		for (int i = 0; i < end - 1; i++) {
			numbers[i] = count;
			flags[i] = true;
			count++;
		}
		for (int i = 0; i < end - 1; i++) {
			if (flags[i]) {
				factors.add(numbers[i]);
				int loop = 2;
				for (long j = numbers[i] * loop; j <= end; j = numbers[i]
						* loop, loop++) {
					flags[(int) (j - 2)] = false;
					eff++;
				}
			}
		}
		// System.out.println(eff);
		return factors;
	}

这将为您提供低于给定数字的所有素数，即 listOfPrime {2,3,5,7} = primeNumbers(10); 我们可以使用相同的数组来检查整除性

public static ArrayList < Integer > getPrimeFactors(int n) {
  ArrayList < Integer > primeNumbers = primeNumbers((n / 2) + 1);
  ArrayList < Integer > removal = new ArrayList < Integer > ();
  for (int i = 0; i < primeNumbers.size(); i++) {
    if (n % primeNumbers.get(i) != 0) {
      removal.add(primeNumbers.get(i));
    }
  }
  primeNumbers.removeAll(removal);
  return primeNumbers;
}